推 cakeboy:謝謝,我來研究一下 01/07 16:34
獻醜了，以下是我最後一題的想法
其實這跟另一個證明有點類似，方法是一樣的，只是敘述不同
這邊為了方便，我用 n 取代|V|，HC/HP表示hamiltonian cycle/path
他用的是反證法，為了要證明所有符合"最小degree點的degree >= n/2"這個條件
的graph都具有HC，因此他找了一個最大的nonhamiltonain graph，叫做 G
並證明 G 不符合那個條件因此矛盾得證。
那麼可以在G中加入一條邊(u, v)讓G獲得一條HC，代表 u 跟 v 之間
已經存在一條HP，示意圖如下:
o－o－........－o－o
(u=)V1 V2 Vn-1 Vn(=v)
因為(u, v)是我們假設加入的邊，因此可以確定原圖G中並不存在(V1, Vn)這個邊所造
成的cycle
考慮V1與Vn所連到的所有點的集合，假設V1有連到中間一點Vi，且Vn同時有連到點Vi-1
的話，會變這樣:
－－－
／ ＼
／ ＼Vi Vn-1
o－o－....－o－o－....－o－o
V1 V2 Vi-1＼ ／ Vn
＼ ／
－－－
明顯的我們可以在這圖中看到一個HC，但是一開始假設的G中不能有HC的存在，因此
這種情況不能發生，也就是說Vn不能連到所有跟V1相連的點的左邊相鄰的點(好饒舌)
題目中給的S = {vi | (u, vi+1)屬於E, 1≦i≦n-1}就是與V1相連的點的左邊那一點
的集合，而 T 自然就是與Vn相連的點，所以不能有任何一點同時存在於這兩個集合
之中，否則會產生上面的情況，第二小題|S交集T| = 0即得證。
接著假設V1總共連到 k 個點，也就是|S| = k時，Vn最多只能連到n-k-1個點(不能連到
自己)，所以|T| < n-k
那麼|S|+|T| < k + n - k = n，再加上S與T交集為空集合的條件
得到|S聯集T| < n，故第一小題得證。
有錯請指正
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.247.97