[理工] [離散]生成樹

作者: darren0831 (達)   2016-09-01 17:59:48
大家好,手機排版請見諒;問題如連結圖中所示
http://imgur.com/Za3CrRt
此題要證明一個無向連通圖的任意一個切集X與
環路C必包含偶數個共同邊;我想請教的是圖中證明
的部分"這兩個子集的誘導子圖未必形成連通圖"
這兩子集V1、V2的點原來都是G的點且是全部的點;G原是
連通圖,那麼兩子集的誘導子圖應該也會是原G的圖吧?
另外有人看得懂這證明嗎?先謝謝各位的幫忙~!
作者: darren0831 (達)   2016-09-01 18:05:00
啊 還是他說的是兩個集合分別不一定是連同圖但兩集合間一定有偶數個邊
作者: w181496 (Kaibro)   2016-09-01 19:29:00
他應該是說去掉X的邊後兩個集合的誘導子圖不連通所以從某集合出發到另一集合的環路會再通過X回到原集合所以不會出現奇數條邊的情形 如果有講錯還請指正
作者: darren0831 (達)   2016-09-01 19:56:00
對 我也是這樣想一進一出的感覺

Links booklink

Contact Us: admin [ a t ] ucptt.com