p6-35
==========================================================
【定理2】
假設G=(V,E)為一個簡單無向圖，若G中每個點的度數至少2，則G包含一個環路。
證明：
假設P為G的一條maximal path，令P : v1-v2-.......-vk，其中k大於等於3
則與v1相鄰的點皆在P中…
..................
=========================================================
我看不懂標藍底的這個敘述，為什麼與v1相鄰的點都會在P中呢？請大家幫忙囉。
3 則留言:
因為如果 v1 還有與其它某個不在 P 中的點相鄰, 假設該點為 x, 則 x-v1-v2-...-vk 為一 path 包含 P 中的所有點且長度大於 P, 則矛盾 P 為 maximal
嗯…謝謝你的解釋
所以說這個只敘述只適用於v1和vk，因為他們是這個maximal path的起點和終點，如果是v2，v3...就不一定保證所有與其相鄰的點都在p中。
這麼說對嗎？？？
應該沒錯
張貼留言