1. Select a graph with the fewest vertices from {G : G has vertex connectivity one and edge
connectivety two}. Explain your answer.
2. Suppose that E' is an edge subset of Km,n , where m < n .
Let Km,n - E' represent the graph that is obtaind by removing E' from Km,n
Please determine min {|E'|: Km,n - E' has no complete matching}
想問一下這兩題怎麼解~?(題目本身就看不太懂了)
謝謝
2 則留言:
1. 題目是希望你找出一個具有最少點數的 G 滿足有cut point但沒有bridge的圖的限制; 因為 G 要不具 bridge, 所以他所有的邊一定要屬於某個 G 中的cycle, 又因為 G 要有 cut point, 則不難驗證 G 中至少會存在一點 v 分屬於兩個不具共同邊的cycle之中(否則不管去掉哪一點都仍會是 connected), 此 v 即為 cut point, 我畫出來的結果是一個具有 5 個點, 長得像蝴蝶結的圖
2. 他要問的是最少要去掉多少個 Km,n 中的邊才有可能使去掉這些邊數後的圖不具有 complete matching, 我想這答案應該是 n; 首先假設 Km,n 的點集為 V1∪V2為Km,n點集的分割 (|V1|=m, |V2|=n), 因為任取一個 v 屬於 V1, 把它的邊通通砍掉, 也就是去掉 n 個與v相連的邊, 則可以保證此圖不具 complete matching, 至於為什麼 n 會是最小, 我想你可以利用 p8-33 的 Hall's Marriage Theorem 對 n 做歸納假設試著證看看
謝謝，這樣懂了~~
張貼留言