Minimum Kapsayan Ağaçlar
Minimum kapsayan bir ağaç, ağırlıklı ve bağlantılı bir grafiğin tüm köşelerini mümkün olan en küçük toplam kenar ağırlığıyla birbirine bağlar; Kruskal ve Prim gibi açgözlü algoritmalar bunu verimli bir şekilde hesaplar.
Tanım
Bağlantılı, kenar ağırlıklı bir grafiğin minimum kapsayan ağacı, tüm köşeleri birbirine bağlayan, döngü içermeyen ve bu tür tüm kapsayan ağaçlar arasında minimum toplam ağırlığa sahip olan bir kenar alt kümesidir.
Kapsam
Bu konu, minimum kapsayan ağaç problemini ve klasik açgözlü çözümlerini — ayrık küme yapısı kullanarak kenarları artan ağırlık sırasına göre ekleyen Kruskal algoritması ve öncelik kuyruğu kullanarak tek bir ağacı büyüten Prim algoritması — bu algoritmaların doğruluğunu kanıtlayan kesme ve döngü özellikleri ile birlikte ele almaktadır. Ayrıca destekleyici ayrık küme (birleştir-bul) veri yapısına da değinilmektedir.
Temel sorular
- Kapsayan bir ağaç nedir ve onu minimum ağırlıklı yapan nedir?
- Açgözlü kenar eklemeleri neden küresel olarak minimum kapsayan bir ağaç üretir?
- Kesme özelliği ve döngü özelliği MST algoritmalarını nasıl doğrular?
- Kruskal ve Prim algoritmaları strateji ve veri yapısı açısından nasıl farklılık gösterir?
- Ayrık küme (birleştir-bul) yapısı Kruskal algoritmasını nasıl verimli hale getirir?
Anahtar kavramlar
- kapsayan ağaç
- kesme özelliği
- döngü özelliği
- Kruskal algoritması
- Prim algoritması
- ayrık küme (birleştir-bul)
- açgözlü güvenli kenar
- kenar ağırlıkları
Temel kuramlar
- Kesme özelliği
- Köşelerin herhangi iki kümeye ayrılması durumunda, bu ayrımı geçen minimum ağırlıklı kenar, bazı minimum kapsayan ağaçlara aittir; bu güvenli kenar garantisi, hem Kruskal hem de Prim'in açgözlü algoritmalarının doğruluk temelini oluşturur.
- Ayrık küme birleştir-bul desteği
- Kruskal algoritması, bir kenar eklemenin bir döngü oluşturup oluşturmayacağını neredeyse sabit amortize edilmiş zamanda test etmek için rütbeye göre birleştirme ve yol sıkıştırma özelliklerine sahip bir birleştir-bul yapısı kullanır.
Klinik önem
Minimum kapsayan ağaçlar, en düşük maliyetli ağ tasarımını modellemektedir: tüm noktaları ucuza birbirine bağlayan iletişim, elektrik veya ulaşım ağlarının döşenmesi gibi. Ayrıca kümeleme, görüntü segmentasyonu, gezgin satıcı problemi için yaklaştırma algoritmaları ve nokta kümelerinin analizinde yapı taşı olarak da hizmet etmektedirler.
Tarihçe
Minimum kapsayan ağaç problemi ilk olarak 1926'da Otakar Borůvka tarafından elektrik ağı tasarımı için çözülmüştür. Vojtěch Jarník (1930) ve daha sonra Prim (1957) ile Dijkstra ağaç büyütme yaklaşımını geliştirirken, Kruskal (1956) kenar sıralamalı açgözlü yöntemi sunmuş ve bu problemi en erken iyi anlaşılan kombinatoryal optimizasyon problemlerinden biri haline getirmiştir.
Öne çıkan isimler
- Joseph Kruskal
- Robert Prim
- Otakar Borůvka
- Vojtěch Jarník
İlgili konular
Temel eserler
- kruskal1956
- cormen2009
Sıkça sorulan sorular
- Kruskal ve Prim algoritmaları arasındaki fark nedir?
- Kruskal algoritması tüm kenarları sıralar ve artan ağırlık sırasına göre ekler, döngü oluşturacak olanları atlar ve döngüleri tespit etmek için birleştir-bul yapısını kullanır. Prim algoritması ise bir başlangıç köşesinden tek bir bağlantılı ağaç büyütür, mevcut ağaçtan çıkan en ucuz kenarı tekrar tekrar ekler ve bir öncelik kuyruğu kullanır. Her ikisi de minimum kapsayan bir ağaç üretir.
- Minimum kapsayan ağaç benzersiz midir?
- Tüm kenar ağırlıkları farklıysa, minimum kapsayan ağaç benzersizdir. Bazı ağırlıklar eşit olduğunda, hepsi aynı minimum toplam ağırlığa sahip birkaç farklı minimum kapsayan ağaç olabilir.