從斯基納的書中，這不是硬漢，而僅僅是我的面試準備。匹配和完美數學
鑑於這個問題，
無向圖G =（V，E）的匹配是一組邊其中沒有兩個具有共同的頂點的。完美匹配是所有頂點匹配的匹配。 （a）構造一個具有2n個頂點和n^2個邊的圖G，使得G具有一個指數數量的完美匹配。 （b）構造具有2n個頂點和n^2個邊的圖G，使得G具有恰好一個唯一的完美匹配。
我只是不知道如何開始。對於a，我選擇了n = 3，所以我現在知道我有6個頂點和9個邊，並試圖連接它們，但我不知道它是否完美匹配。
對於b）：我們在（n，n）頂點上建立類似於完全二部圖的東西。調用分區A =（1,2,3，...，n）和B =（n + 1，n + 2，n + 3，... 2n）。
成爲一個集團。
對於B中的每個頂點n + i，爲A中的每個頂點j添加一個邊（n + i，j），其中j爲< = i。例如，頂點n + 1僅入射到邊緣（n + 1,1）;頂點n + 2入射到（n + 2,1）和（n + 2,2）;頂點n + 3入射到（n + 3,1）（n + 3,2）（n + 3,3）。
這迫使獨特的完美匹配是{e in E |對於[1; n]}中的某個i，e =（n + i，i）（試圖證明這是爲了練習歸納）。由於A是n個頂點上的一個團，所以它有n^2/2 - n/2個邊。在A和B之間運行的邊的總數爲sum from 1 to n，這是n^2/2 + n/2，所以我們一起得到
n^2/2 - n/2 + n^2/2 + n/2 = n^2邊緣。
大概該曲線圖將幫助您爲（A）：
V = {1,2，A，B}
E = {（1，A），（1，B），（ 2，A），（2，b）}
2 * 2個頂點
2^2個邊緣
沒有無向圖可以有n^2條邊;當你寫n2時你的意思是n^2？一個派系有（n^2-n）/ 2個邊緣。這一定是在談論多圖。 （a）中完美配對的數量應該是指數型的？ – 2013-04-20 17:28:59
@ G.Bach我的意思是N^2，它表示構建一個具有2n條邊和n^2條邊的圖 – user2302617 2013-04-20 17:32:28
它必須談論非簡單圖，然後可能是多圖，因爲即使是一個完整的帶有自我的有向圖循環只有n^2條邊。 – 2013-04-20 17:34:49