Research Space for Linear Algebra & Discrete Mathematics
借題問一下，vertex connective 為2的話=代表拿掉2個點才能使圖不連通=每個點degree至少2=biconnected這樣觀念有錯嗎?edge connective 為2的話=代表拿掉2個邊才能使圖不連通?=degree>=2?=biconnected如果只就定義來看，我可以區分這兩個，但同個圖我找的例子vertex connective 幾乎都等於 edge connective觀念有錯幫忙導正一下謝謝
我的想法大致上是這樣: 是給定一個圖G=(V,E), Ke(G)為edge connectivity, 則至少存在一個set of edges X, 使得 E-X 會將 G 分為兩個components C1,C2, 考慮所有的 e 屬於 X, 若逐步將 G 中的每一個 e 的左右兩端點, 取C1,C2中點數較多的那一邊的端點刪掉, 最後所剩下的那個graph必為disconnected, 而因為最多只會刪到 Ke(G) 個點來使得 G 為 disconnected, 所以 Kv(G)<=Ke(G)Tse: 你上面列的觀念大部分都沒問題, 但其中要注意的是, edge connectivity為 2 和biconnected並不是等價的, biconnected的定義是跟著點走的, 它是定義成不含articulation points, 所以我們才會將edge和vertex的connectivity各自分別定義; 有不少圖的vertex connectivity小於edge connectivity, 譬如想像一下一個有5個點的圖, 把他畫成蝴蝶結的樣子, 那個圖就是反例
考慮所有的 e 屬於 X, 若逐步將 G 中的每一個 e 的左右兩端點, 取C1,C2中點數較多的那一邊的端點刪掉請問助教這句話的作法取C1,C2中點數較多的那一邊的端點刪掉是什麼意思?不太懂點數多的意思麻煩助教了
謝謝~這樣大概了解
就是若 G-X 會形成兩個components C1, C2, 對每一個 e=(a,b)∈X, 不失一般性令 a∈C1, b∈C2, 若 |C1|>=|C2| 則刪 a (i.e., C1=C1-a), 否則刪 b (C2=C2-b), 這樣到最後被刪掉的這些點所形成的集合就會是切集
張貼留言
6 則留言:
借題問一下，
vertex connective 為2的話
=代表拿掉2個點才能使圖不連通
=每個點degree至少2
=biconnected
這樣觀念有錯嗎?
edge connective 為2的話
=代表拿掉2個邊才能使圖不連通
?=degree>=2
?=biconnected
如果只就定義來看，我可以區分這兩個，但同個圖我找的例子vertex connective 幾乎都等於 edge connective
觀念有錯幫忙導正一下
謝謝
我的想法大致上是這樣: 是給定一個圖G=(V,E), Ke(G)為edge connectivity, 則至少存在一個set of edges X, 使得 E-X 會將 G 分為兩個components C1,C2, 考慮所有的 e 屬於 X, 若逐步將 G 中的每一個 e 的左右兩端點, 取C1,C2中點數較多的那一邊的端點刪掉, 最後所剩下的那個graph必為disconnected, 而因為最多只會刪到 Ke(G) 個點來使得 G 為 disconnected, 所以 Kv(G)<=Ke(G)
Tse: 你上面列的觀念大部分都沒問題, 但其中要注意的是, edge connectivity為 2 和biconnected並不是等價的, biconnected的定義是跟著點走的, 它是定義成不含articulation points, 所以我們才會將edge和vertex的connectivity各自分別定義; 有不少圖的vertex connectivity小於edge connectivity, 譬如想像一下一個有5個點的圖, 把他畫成蝴蝶結的樣子, 那個圖就是反例
考慮所有的 e 屬於 X, 若逐步將 G 中的每一個 e 的左右兩端點, 取C1,C2中點數較多的那一邊的端點刪掉
請問助教這句話的作法
取C1,C2中點數較多的那一邊的端點刪掉
是什麼意思?
不太懂點數多的意思
麻煩助教了
謝謝~這樣大概了解
就是若 G-X 會形成兩個components C1, C2, 對每一個 e=(a,b)∈X, 不失一般性令 a∈C1, b∈C2, 若 |C1|>=|C2| 則刪 a (i.e., C1=C1-a), 否則刪 b (C2=C2-b), 這樣到最後被刪掉的這些點所形成的集合就會是切集
張貼留言