Jambatan dan Titik Artikulasi

Sesetengah bahagian graf tidak berarah adalah kritikal: buangnya dan graf akan terpisah. Mencarinya mendedahkan pautan yang lemah.

Jambatan ialah sisi yang apabila dibuang, meningkatkan bilangan komponen bersambung. Jambatan itu merupakan satu-satunya laluan antara dua rantau.

Titik artikulasi ialah nod yang apabila dibuang, menyebabkan graf terputus. Rangkaian perlu berwaspada terhadap titik kegagalan tunggal ini.

Kedua-duanya menggunakan satu DFS, dengan menjejaki masa penemuan dan nilai low, sama seperti Tarjan tetapi pada graf tidak berarah.

low sesebuah nod ialah ID penemuan paling awal yang boleh dicapai daripada subpokok DFS-nya, mungkin melalui satu sisi belakang ke atas.

Apabila DFS memasuki nod, tetapkan disc dan low kepada pemasa semasa, kemudian teruskan ke jirannya.

Selepas melakukan rekursi ke anak v, jika low[v] > disc[u], tiada sisi belakang yang melangkaui u, maka sisi u-v ialah jambatan.

u bukan akar ialah titik artikulasi apabila seorang anak v memenuhi low[v] >= disc[u]: subpokok v tidak dapat memintas u.

Akar DFS ialah titik artikulasi hanya jika mempunyai dua atau lebih anak dalam pokok DFS, jadi bilangkan anak-anaknya.

Apabila mengemas kini low daripada sisi belakang, jangan berpatah balik melalui sisi kepada induk anda, atau anda akan tersalah menilai jambatan.

Satu DFS sahaja dapat menemukan semua jambatan dan titik artikulasi dalam O(V + E). Tiada penerokaan tambahan diperlukan.

Satu DFS dengan disc dan low menemukan semuanya: low[v] > disc[u] menandakan jambatan, manakala low[v] >= disc[u] menandakan titik artikulasi. 🌉