[理工] [離散]-圖論

[polomoss (小澤)]

1.edge connectivity

2.vertex connectivity

3.minimal domain set



問一下這三個的意思?



--
     ◤    ◥  答      ◤    ◥  拉      ◤    ◥  米      ◤    ◥  哆
   Σ ◆  ◆   蚊    Σ ◆  ◆   肥    Σ ◆  ◆   開    Σ ◆  ◆   啦
        ︵     吸         ︵     兒         ︵     喇         ︵     太
    ◣++++++◢        ◣++++++◢        ◣++++++◢ 雞     ◣++++++◢ 裸
◥▇▆@ ≡ @▆▇◤     Ψ ≡ Ψ          ▄ ≡ ▄  囉  ▄▄▄ ≡ ▄▄▄
        ▅                ▅          ▄/   ▅   \▄          ▅  ＡΓＶＩＳＳ

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.136.82.109
推 FRAXIS:1. 要拿掉幾條邊 才會使得圖不連通
→ FRAXIS:2 要拿掉幾個頂點 才會使得圖不連通
→ FRAXIS:3. 選擇一個頂點最小子集 使得其他頂點都有邊與此子集相連
The connectivity or vertex connectivity κ(G) is the size of a smallest
vertex cut. A graph is called k-connected or k-vertex-connected if its vertex
connectivity is k or greater.

拿掉k個點才使圖不連通 = 每個點的degree至少k (這樣有錯嗎?)

如果對的話，一個圖的vertex connectivity = edge connectivity ??
※ 編輯: polomoss        來自: 220.136.82.109       (02/21 20:16)
→ FRAXIS:我不懂這跟degree有啥關聯..
→ polomoss:例如:vertex connectivity=2，代表每個點degree至少2
→ polomoss:則G就是biconnected，因為至少拿掉2個才使圖不連通
推 FRAXIS:我的意思是說 跟degree應該沒什麼關聯..
推 ie925155:隨便舉例都是反例 你想隨便一條path他的connectivity =1
→ ie925155:但path卻只有頭尾的degree為1  所以你的想法不能成立
推 FRAXIS:樓上你舉的例子 degree至少1 而且連通度也是1
→ FRAXIS:似乎沒辦法反證原Po的猜測