Re: [公告] HW2
看板DiscreteMath作者roger00 (Stage Column(?))時間17年前 (2008/11/01 21:53)推噓2(2推 0噓 4→)留言6則, 2人參與討論串3/3 (看更多)
※ 引述《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
推
11/01 22:29, , 1F
11/01 22:29, 1F
→
11/01 22:29, , 2F
11/01 22:29, 2F
推
11/02 23:11, , 3F
11/02 23:11, 3F
→
11/02 23:13, , 4F
11/02 23:13, 4F
→
11/02 23:14, , 5F
11/02 23:14, 5F
→
11/02 23:14, , 6F
11/02 23:14, 6F
討論串 (同標題文章)