作者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