Minimum yayılan ağaç
Çizge teorisinden bir dizi problem Minimum yayılan ağaç olarak adlandırılır. Çizge teorisinde bir ağaç, tüm köşeleri birbirine bağlamanın bir yoludur, böylece herhangi bir köşeden ağacın diğer herhangi bir köşesine tam olarak bir yol vardır. Çizge, yollarla birbirine bağlanmış bir dizi şehri temsil ediyorsa, her şehre diğerlerinden ulaşılabilecek, ancak bir şehirden diğerine seyahat etmek için birden fazla yol olmayacak şekilde bir dizi yol seçilebilir.
Bir grafikte birden fazla yayılan ağaç olabilir, tıpkı şehirler arasındaki yolları seçmenin birden fazla yolu olabileceği gibi.
Çoğu zaman grafikler ağırlıklandırılır; iki şehir arasındaki her bağlantının bir ağırlığı vardır: Belirli bir yolda seyahat etmenin bir maliyeti olabilir veya bir bağlantı diğerinden daha uzun olabilir, bu da o bağlantıda seyahat etmenin daha fazla zaman aldığı anlamına gelir. Çizge teorisi dilinde, bağlantılar kenar olarak adlandırılır.
Minimum yayılan ağaç bir ağaçtır. Diğer ağaçlardan farkı, kenarlara bağlı ağırlıkların toplamını en aza indirmesidir. Grafiğin nasıl göründüğüne bağlı olarak, birden fazla minimum yayılan ağaç olabilir. Tüm kenarların aynı ağırlığa sahip olduğu bir grafikte, her ağaç bir minimum yayılan ağaçtır. Tüm kenarlar farklı ağırlıklara sahipse (yani aynı ağırlığa sahip iki kenar yoksa), tam olarak bir tane minimum yayılan ağaç vardır.
Düzlemsel bir grafiğin minimum yayılan ağacı. Her kenar, burada kabaca uzunluğu ile orantılı olan ağırlığı ile etiketlenmiştir.
Minimum yayılan ağacı bulma
Bir ilk deneme
Minimum yayılan ağacı keşfedecek bir algoritma yapmak çok basit olabilir:
fonksiyonu MST(G,W): T = {} T bir yayılan ağaç oluşturmazken: E'de T için güvenli olan minimum ağırlıklı kenarı bulun T = T union {(u,v)} return TBu durumda "güvenli", kenarın dahil edilmesinin grafikte bir döngü oluşturmadığı anlamına gelir. Döngü, bir köşeden başlayıp bir dizi başka köşeye gitmek ve aynı kenarı iki kez kullanmadan tekrar başlangıç noktasına varmak anlamına gelir.
Tarih
Çek bilim adamı Otakar Borůvka, 1926 yılında minimum yayılan ağaç bulmak için bilinen ilk algoritmayı geliştirdi. Moravya'nın elektrikle verimli bir şekilde kapsanması sorununu çözmek istiyordu. Günümüzde bu algoritma Borůvka'nın algoritması olarak bilinmektedir. Diğer iki algoritma günümüzde yaygın olarak kullanılmaktadır. Bunlardan biri 1930 yılında Vojtěch Jarník tarafından geliştirilmiş ve 1957 yılında Robert Clay Prim tarafından uygulamaya konulmuştur. Edsger Wybe Dijkstra bunu 1959'da yeniden keşfetmiş ve Prim'in algoritması olarak adlandırmıştır. Diğer algoritma Kruskal'ın algoritması olarak adlandırılır ve 1956 yılında Joseph Kruskal tarafından ortaya atılmıştır. Her üç algoritma da açgözlüdür ve polinom zamanda çalışır.
Bugüne kadarki en hızlı minimum yayılan ağaç algoritması Bernard Chazelle tarafından geliştirilmiştir. Algoritma, yaklaşık bir öncelik sırası olan yumuşak yığına dayanmaktadır. Çalışma süresi O(m α(m,n))'dir; burada m kenar sayısı, n köşe sayısı ve α Ackermann fonksiyonunun klasik fonksiyonel tersidir. α fonksiyonu son derece yavaş büyür, böylece tüm pratik amaçlar için 4'ten büyük olmayan bir sabit olarak kabul edilebilir; bu nedenle Chazelle'in algoritması doğrusal zamana çok yakın sürer.
Bu problem için mümkün olan en hızlı algoritma nedir? Bu, bilgisayar bilimlerindeki en eski açık sorulardan biridir. En azından tüm ağırlıkları incelememiz gerektiğinden, açıkça doğrusal bir alt sınır vardır. Eğer kenar ağırlıkları sınırlı bit uzunluğuna sahip tamsayılar ise, doğrusal çalışma süresine sahip deterministik algoritmalar bilinmektedir. Genel ağırlıklar için, beklenen çalışma süresi doğrusal olan rastgele algoritmalar vardır.
Soruna dağıtılmış bir şekilde de yaklaşılabilir. Her düğüm bir bilgisayar olarak kabul edilirse ve hiçbir düğüm kendi bağlı bağlantıları dışında bir şey bilmiyorsa, dağıtılmış minimum yayılan ağaç yine de hesaplanabilir.
Sorular ve Yanıtlar
S: Çizge teorisinde minimum yayılan ağaç nedir?
C: Minimum yayılan ağaç, çizge kuramında kenarlara eklenen toplam ağırlıkları en aza indiren bir ağaçtır.
S: Çizge teorisinde ağaç nedir?
C: Ağaç, çizge teorisinde tüm köşeleri birbirine bağlamanın bir yoludur, böylece herhangi bir köşeden ağacın diğer herhangi bir köşesine yalnızca bir yol vardır.
S: Şehirleri temsil eden bir çizge teorisi senaryosunda yolları seçmenin amacı nedir?
C: Şehirleri temsil eden bir çizge teorisi senaryosunda yolların seçilmesinin amacı, her şehre diğer tüm şehirlerden ulaşılabilmesini sağlamaktır, ancak bir şehirden diğerine seyahat etmek için birden fazla olası yol yoktur.
S: Bir çizge birden fazla yayılan ağaca sahip olabilir mi?
C: Evet, bir çizge birden fazla yayılan ağaca sahip olabilir.
S: Minimum yayılan ağaç ile çizge kuramındaki diğer ağaçlar arasındaki fark nedir?
C: Minimum yayılan ağaç, kenarlara bağlı toplam ağırlıkları en aza indirirken, diğer ağaçlar bu özelliğe sahip değildir.
S: Çizge teorisinde kenarlar nedir?
C: Kenarlar, çizge teorisinde iki köşe arasındaki bağlantılardır.
S: Bir grafikte farklı ağırlıklı kenarlara sahip birden fazla minimum yayılan ağaç olabilir mi?
C: Evet, grafiğin nasıl göründüğüne bağlı olarak, birden fazla minimum yayılan ağaç olabilir.
