Köprüler ve Eklem Noktaları

Yönsüz bir grafiğin bazı bölümleri kritiktir: onları kaldırdığınızda grafik parçalanır. Bunları bulmak, zayıf bağlantıları ortaya çıkarır.

Köprü, kaldırılması bağlantılı bileşenlerin sayısını artıran kenardır. İki bölge arasındaki tek yoldur.

Kesim noktası, kaldırılması grafiğin bağlantısını koparan düğümdür. Ağlar, bu tür tekil arıza noktalarından çekinir.

Her ikisi de tek bir DFS üzerinde çalışır; keşif zamanını ve bir low değerini izler. Tarjan algoritmasına benzer, ancak yönsüz bir grafikte uygulanır.

Bir düğümün en düşük erişim değeri, DFS alt ağacından, olası bir geri kenarla yukarı doğru geçerek erişilebilen en erken keşif kimliğidir.

DFS bir düğüme girdiğinde, disc ve low değerlerini geçerli zamanlayıcıya ayarlayın ve komşularına doğru ilerleyin.

Alt düğüm v'ye özyinelemeyle girdikten sonra low[v] > disc[u] ise, u'nun ötesine geçen hiçbir geri kenar yoktur; bu nedenle u-v kenarı bir köprüdür.

Kök olmayan u düğümü, bir v alt düğümü low[v] >= disc[u] koşulunu sağladığında kesim noktasıdır: v'nin alt ağacı u'yu atlayamaz.

DFS kökü, yalnızca DFS ağacında iki veya daha fazla alt düğümü varsa kesim noktasıdır; bu nedenle onları sayın.

Bir geri kenardan low değerini güncellerken, kenar üzerinden ebeveyne geri dönmeyin; aksi hâlde köprüleri yanlış değerlendirebilirsiniz.

Tek bir DFS, her köprüyü ve kesim noktasını birlikte O(V + E) sürede bulur. Ek bir dolaşma gerekmez.

u düğümünden v alt düğümüne özyinelemeyle girdikten sonra low[v] > disc[u] olduğunu görüyorsunuz. Ne buldunuz?

disc ve low değerlerini kullanan tek bir DFS her şeyi bulur: low[v] > disc[u] bir köprüyü, low[v] >= disc[u] ise bir kesim noktasını gösterir. 🌉