Re: [問題] 請問關於articulation point

[f54512 (這不是柏良 這不是柏良)]

※ 引述《electgpro (Ray(甫))》之銘言：
: PDF裡面第35頁
: 他說的L(i)的定義我看不太懂
: 可不可以請助教or強者同學用中文解釋一下
: 謝謝^^
L(i)的意思是

從vertex i出發經過0個或多個tree edges再經過0個或1個backward edge

可到達的最小的Depth First Number

(tree edges只能是downward)

以vertex 11 (DFN = 4)為例

從vertex 11出發 經過2個tree edges到達vertex 9

再從backward edges到達vertex 3 (DFN = 3)

由於限定最多只能走一條backward edge所以不能再往回走到vertex 1

因此L(11) = 3

希望這樣能幫助你理解^^

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.135.94.1
推 electgpro:thx