Re: [公告] HW2

[roger00 (Stage Column(?))]

※ 引述《anfranion (安弗尼恩)》之銘言：
: 那個啊，作業二的第八題
: 解答上寫 Trivial
: 那如果考試我也可以這樣寫嗎囧
有點冗長 參考看看吧

    T = G (V,E) , 對於所有 v 屬於 V

    deg(v) > 1  < = >  v 是 articulation point of T

    pf.  (=>): 令 T -{v} = G(V',E')

               |V'| = |V| - 1

               ∵ deg(v) > 1

               |E'| < |E| - 1  (v的deg.大於一,拿掉v必刪掉一個以上的邊)

                    = (|V| - 1 ) - 1  (在T中滿足 |E| = |V| - 1 )

                    = |V'| - 1

              = >  T -{v} : disconnected  (邊的個數少於最低需求)

              = >  v是 articulation point of T

         (<=):  首先,對於 V 中任一點 v

                deg(v) ≧ 1    since T is connected

                再來證明若 v 是 articulation point of T ,則 deg(v) ≠ 1

                (證明 ~q -> ~p ) 假設  deg(v) = 1,

                = >  T - {v} : connected

                = >  v 不是 articulation point  得證.

                since  deg(v) ≧ 1  且 若 v 是 T 中的關節點,則 deg(v) ≠ 1

                = > deg(v) > 1

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.112.7.59
推 anfranion:感謝  可是我不懂為什麼degree > 1的話就是articulation
→ anfranion:point
推 hi08060204:tree的性質吧
→ hi08060204:a -> b點的path 是唯一的
→ hi08060204:所以如果取掉不是最邊邊的點(deg=1)  就會disconnected
→ hi08060204:不算是證明的想法orz