[圖論] Articulation Points

看板Math作者 (無法顯示)時間14年前 (2011/07/25 09:44), 編輯推噓2(2推 0噓 13→)
留言15則, 3人參與, 最新討論串1/1
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
推
07/25 10:42, , 1F
唔 L(i)就是你與你的子節點們透過back edge(虛線邊)
07/25 10:42, 1F
→
07/25 10:43, , 2F
能走到的節點的DFN最小事多小
07/25 10:43, 2F
→
07/25 10:44, , 3F
呃「你」就是編號為i的nodeXD
07/25 10:44, 3F
→
07/25 10:46, , 4F
所以可以看到11可以透過11—10—9…3走到3(DFN=3)
07/25 10:46, 4F
→
07/25 10:46, , 5F
，L(11)就是3
07/25 10:46, 5F
→
07/25 10:49, , 6F
然後仔細想想會發現 當子節點的DFN都不比自己大的話
07/25 10:49, 6F
→
07/25 10:49, , 7F
自己就是割點(也就是Y) 沒記錯的話(汗
07/25 10:49, 7F
→
07/25 10:59, , 8F
關於back edge，連結的說法是往下走後，只再走0或1條
07/25 10:59, 8F
→
07/25 11:00, , 9F
back edge(也就是可以選擇不走or只走一條)所走到的
07/25 11:00, 9F
→
07/25 11:00, , 10F
node
07/25 11:00, 10F
推
07/25 11:59, , 11F
推
07/25 11:59, 11F
→
07/25 20:21, , 12F
sor 可以再請問找Y的例子嗎..我好像不是很懂@@
07/25 20:21, 12F
→
07/25 20:32, , 13F
話說 好像不是子節點的DFN都不比自己大的話才是割點
07/25 20:32, 13F
→
07/25 20:33, , 14F
只要有任一個tree-edge連到的子節點的DFN>=自己 那你
07/25 20:33, 14F
→
07/25 20:33, , 15F
就會是割點 因為拔掉會造成該子節點路斷掉
07/25 20:33, 15F
‣ 更多 mqazz1 的文章
文章代碼(AID): #1EBCfWXA (Math)