[理工] [离散]生成树

楼主: 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