2010-02-22

[離散]Graph

Let Kv(G)and Ke(G) represent the vertex connectivity and edge connectivity,
respectively, of a graph G.

show Kv(G)<= Ke(G)


沒看過證連通性的問題

請問助教要如何證明

謝謝
於

6 則留言:

  1. Chesley2010年2月22日 上午9:51

    借題問一下，

    vertex connective 為2的話
    =代表拿掉2個點才能使圖不連通
    =每個點degree至少2
    =biconnected

    這樣觀念有錯嗎?

    edge connective 為2的話
    =代表拿掉2個邊才能使圖不連通
    ?=degree>=2
    ?=biconnected

    如果只就定義來看，我可以區分這兩個，但同個圖我找的例子vertex connective 幾乎都等於 edge connective

    觀念有錯幫忙導正一下
    謝謝

    回覆刪除
  2. 匿名2010年2月22日 晚上10:43

    作者已經移除這則留言。

    回覆刪除
  3. 線代離散助教(wynne)2010年2月23日 凌晨1:54

    我的想法大致上是這樣: 是給定一個圖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個點的圖, 把他畫成蝴蝶結的樣子, 那個圖就是反例

    回覆刪除
  4. glay_luncy2010年2月23日 凌晨3:47

    考慮所有的 e 屬於 X, 若逐步將 G 中的每一個 e 的左右兩端點, 取C1,C2中點數較多的那一邊的端點刪掉

    請問助教這句話的作法
    取C1,C2中點數較多的那一邊的端點刪掉
    是什麼意思?
    不太懂點數多的意思
    麻煩助教了

    回覆刪除
  5. Chesley2010年2月23日 上午9:44

    謝謝~這樣大概了解

    回覆刪除
  6. 線代離散助教(wynne)2010年2月24日 凌晨12:12

    就是若 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), 這樣到最後被刪掉的這些點所形成的集合就會是切集

    回覆刪除