作者mqazz1 (無法顯示)
看板Math
標題[圖論] Articulation Points
時間Mon Jul 25 09:43:58 2011
1.
http://ppt.cc/WI6Q
2.
http://ppt.cc/RRnY
3.
http://ppt.cc/-b4x
請問第三頁的L(i)是什麼意思?
還有那個Y是怎麼找出來的?
謝謝
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.228.24.124
1F：推 duckingod :唔 L(i)就是你與你的子節點們透過back edge(虛線邊) 07/25 10:42
2F：→ duckingod :能走到的節點的DFN最小事多小 07/25 10:43
3F：→ duckingod :呃「你」就是編號為i的nodeXD 07/25 10:44
4F：→ duckingod :所以可以看到11可以透過11—10—9…3走到3(DFN=3) 07/25 10:46
5F：→ duckingod :，L(11)就是3 07/25 10:46
6F：→ duckingod :然後仔細想想會發現 當子節點的DFN都不比自己大的話 07/25 10:49
7F：→ duckingod :自己就是割點(也就是Y) 沒記錯的話(汗 07/25 10:49
8F：→ duckingod :關於back edge，連結的說法是往下走後，只再走0或1條 07/25 10:59
9F：→ duckingod :back edge(也就是可以選擇不走or只走一條)所走到的 07/25 11:00
10F：→ duckingod :node 07/25 11:00
11F：推 suhorng :推 07/25 11:59
12F：→ mqazz1 :sor 可以再請問找Y的例子嗎..我好像不是很懂@@ 07/25 20:21
13F：→ suhorng :話說 好像不是子節點的DFN都不比自己大的話才是割點 07/25 20:32
14F：→ suhorng :只要有任一個tree-edge連到的子節點的DFN>=自己 那你 07/25 20:33
15F：→ suhorng :就會是割點 因為拔掉會造成該子節點路斷掉 07/25 20:33