用完備匹配解決邏輯判斷問題

摘 要:有些邏輯判斷問題的條件往往給得很多，看上去錯綜復(fù)雜。本文利用圖論中圖的知識，將所給條件轉(zhuǎn)化成圖，利用完備匹配將頭緒紛繁的事物關(guān)系理清，從而給出邏輯判斷問題的答案。

關(guān)鍵詞:圖完備匹配邏輯判斷

中圖分類號:TP182文獻(xiàn)標(biāo)識碼:A文章編號:1674-098X(2011)02(c)-0230-01

1 提出問題

邏輯判斷題是開發(fā)智力題的重要題型，經(jīng)常被父母、師長拿來考學(xué)生。若不得其法，有些邏輯判斷題很難應(yīng)付。比如一道“多才多藝的姐妹”的題目是這樣的:

一個加拿大外交官的4個女兒艾倫、雷妮、謝莉、特萊莎，都是音樂家，每個人演奏一種不同的樂器(這4種樂器分別是單簧管、笛子、鋼琴和小提琴)，每個人都講一種不同的語言(法語、德語、西班牙語、意大利語)。①演奏單簧管的女兒不講法語或德語;②講西班牙語的女兒特別喜歡她的樂器，因為她不必把它帶去上音樂課;③謝莉不講德語或西班牙語，不演奏單簧管;④艾倫不是那個講德語的女兒，她也不演奏單簧管;⑤特萊莎不吹笛子，不演奏單簧管。根據(jù)上面的句子，你能說出4個人分別演奏哪一種樂器，講什么語言嗎？

這個問題看起來頭緒紛繁，條件錯綜復(fù)雜。若用圖來表示這些關(guān)系，就會把頭緒理清，再利用完備匹配就可以得到問題的答案。

2 基本概念

定義1［1，2］:稱數(shù)學(xué)結(jié)構(gòu)為一個圖，其中是非空集合，是從集合到的一個映射，則稱是一個以為頂點集合，以為邊集合的圖，中的元素稱為圖的頂點，中的元素稱為的邊，稱為的關(guān)聯(lián)函數(shù)。

定義2［3］:設(shè)和是的頂點集，使且的每一條邊的一個端點在中，另一個端點在中，則稱為二部圖。

定義3［1，2］:是圖的邊子集，且中任二邊在中不相鄰，則稱是中的一個匹配;中的每條邊的兩個端點稱為在中相配;中每邊的端點稱為被許配;中每個頂點皆被許配時，稱為的一個完備匹配。

3 解決問題

題目敘述的是4個人物以及她們所演奏的樂器、所講的語言。因此可以得到兩個二部圖。其頂點集X=｛A，L，X，T｝分別代表艾倫、雷妮、謝莉、特萊莎四個人物，Y=｛單簧管，笛子，鋼琴，小提琴｝為四種樂器，Z=｛法語，德語，西班牙語，意大利語｝為四種語言。若某人有可能演奏某種樂器或講某種語言就在它們之間連線，構(gòu)成邊集。

如圖1所示，由條件③，謝莉可能講法語和意大利語，可能演奏笛子、鋼琴和小提琴;由條件④，艾倫可能講法語、西班牙語和意大利語，可能演奏笛子、鋼琴和小提琴;由條件⑤，特萊莎可能演奏鋼琴和小提琴，可能講四種語言中的任何一種，則分別在它們之間連線得到邊。而條件中沒有提到的雷妮則可能講四種語言中的任何一種，可能演奏四種樂器中的任何一種，故應(yīng)在她與所有的語言和樂器之間連線得到邊。這樣就完成了第一步，利用條件③、④、⑤，將其復(fù)雜關(guān)系表示成了兩個二部圖。

由題意在X與Y、X與Z之間存在完備匹配。下面就進(jìn)行第二步，利用條件①和條件②，找到這兩個完備匹配。由圖可知演奏單簧管的只能是雷妮，故選定此邊，將其加粗，同時將雷妮與其它樂器間的邊改為虛線。由條件①，演奏單簧管的女兒不講法語或德語，故將雷妮與法語和德語間的邊也改為虛線。現(xiàn)在講德語的只能是特萊莎，選定此邊，加粗，并將特萊莎與其它語言間的邊改為虛線。現(xiàn)由條件②，講西班牙語的女兒應(yīng)演奏鋼琴，而可能講西班牙語的有艾倫和雷妮，但雷妮已確定為演奏單簧管，所以一定是艾倫演奏鋼琴，且講西班牙語。因此將艾倫與鋼琴和西班牙語之間的邊加粗，而將艾倫與其它樂器和語言間的邊改為虛線。現(xiàn)在演奏笛子和講法語的都只能是謝莉，將相應(yīng)邊加粗，而把與謝莉相連的其它邊改為虛線。最后，只能是特萊莎演奏小提琴，雷妮講意大利語了，將相應(yīng)邊加粗。這樣我們便得到了兩個完備匹配，而本題也有了答案，即圖2。

4 小結(jié)

由此可見，完備匹配對解決此類邏輯判斷問題可以達(dá)到事半功倍的效果。只要掌握了方法，就可以輕松應(yīng)付邏輯判斷問題。

參考文獻(xiàn)

[1]王樹禾.圖論[M].科學(xué)出版社，2004.

[2]王朝瑞.圖論[M].北京理工大學(xué)出版社，2001.

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文