Çok yönlü grafiğin minimum kapsayan ağacı

Question

Köklü bir ağacı bağlantılı basit bir grafikten çıkarırken sorun yaşıyorum.

Çıkarım, minimum yayılma ağacını bularak yapılabilir, ancak sonuç ek iki tür koşulla sınırlandırılmıştır:

• sAşağıdaki örnekte bilinen bir kök var .
• Seçildikleri takdirde bazı kenarların yönlerini biliyoruz . Bu kenarlar vardır değil henüz seçilmiş veya sorun Steiner ağaç sorun haline gelir.

Kenarlardaki sayıların ağırlıkları olduğunu unutmayın. Yani s -> b -> c -> anormal bir min yayılma ağacının uygulanıp uygulanmadığını, ancak kenarın acyönü yanlış olduğunu anlayacağız . Öte yandan, Chu – Liu / Edmonds'un algoritmasını yönlendirilmiş grafiklerin arboresansını yaymak için kullanamayız çünkü kenarın yönünü bilmiyoruz ve çıkaramayız bc.

Kökün konumuna göre bazı kenarların yönlerini çıkarabiliriz. Örneğin, örnekte s -> bve biliyoruz s -> a.

Görünüşe göre problem iki adımda çözülebilir :

1. basit grafiği çoklu grafiğe dönüştürün. Yönleri bilinmeyen kenarlar için (orijinal basit grafikte), bunları ters yönlere sahip iki köşe arasında iki yönlendirilmiş kenar kullanarak çoklu grafikte temsil ederiz.
2. Bu çoklu grafiğin minimum yönelimli yayılma ağacını buluyoruz.

---

Odaklı Genişleme Ağacı

Genişleyen ağacın son bölümünde , Wikipedia , yönelimli yayılan ağaçtan bahsedilir ve bir kağıt [levine2011sandpile] 'den bahsedilir. Sorun ortama uyuyor. Diyor ki:

Bir köşe Verilen vyönlendirilmiş ufak matbaa üzerine G, bir yönelimli yayılan ağaç Tkökü vbir asiklik subgraph olduğunu Gdışındaki her köşe hangi voutdegree 1 sahiptir.

"Outdegree" teriminin biraz kafa karıştırıcı olduğuna dikkat edin, bence "kararsız" olmalıdır. Ancak önemli değil, çünkü basit alt grafiğin, kök kaynak veya havuz olan yönlendirilmiş bir ağaç olmasını kısıtlıyor.

Ancak bu makaleye göre bir algoritmanın nasıl uygulanabileceği benim için net değil.

---

• Levine, L. (2011). Kum tepesi grupları ve yönlendirilmiş çizgi grafiklerin kapsayan ağaçları. Journal of Combinatorial Theory, Series A, 118 (2), 350-364.
• https://en.wikipedia.org/wiki/Spanning_tree

Answer 1

Yorumlarda belirtildiği gibi, bu, Edmonds'un algoritması (veya Chu – Liu / Edmonds'un algoritması) ile verimli bir şekilde çözülebilen, minimum genişleyen bir ağaç problemidir.