19. yüzyılın başında, Berlin'den bir geometri, Jacob Steinerüç köyün nasıl bağlanacağını belirleyerek görev süreleri en kısa olacaktı. Daha sonra, bu sorunu genelleştirdi: Uçakta bir nokta bulmak gerekiyor, böylece ondan diğer noktalara olan mesafe en küçük olacaktı. 20. yüzyılda bu konuda çalışmalara devam edildi. Birkaç puan alıp, aralarındaki mesafenin en kısa olması için onları birleştirmeye karar verildi. Bütün bunlar çalışılan sorunun özel bir halidir.
Açgözlü Algoritmalar
Kraskal algoritması "açgözlü" algoritmalara aittir.(aynı zamanda gradyan olarak da adlandırılırlar). Bunların özü - her adımda en büyük kazanç. Her zaman "açgözlü" algoritmalar soruna en iyi çözümü vermezler. Belirli görevlere uygulandığında en uygun çözümü sunduğunu gösteren bir teori var. Bu matroidlerin teorisidir. Kraskal algoritması böyle problemlere atıfta bulunur.
Minimum ağırlık çerçevesini bulmak
Düşünülen algoritma optimal oluştururgrafik çerçevesi. Bununla ilgili sorun şu şekildedir. Çoklu kenarları ve halkaları olmayan, yönlendirilmemiş bir grafik verilir ve her bir kenara e - w (e) 'nin bir ağırlık ağırlığı atan bir kenar kümesi üzerinde bir ağırlık işlevi w verilir. Her alt kümenin kenar kümesinden ağırlığı, kenarlarının ağırlıklarının toplamı ile belirlenir. En küçük ağırlığın iskeletini bulmak gerekir.
tanım
Kraskal algoritması bu şekilde çalışır.İlk olarak, orijinal grafiğin tüm kenarları artan ağırlıklara göre düzenlenmiştir. Başlangıçta, çerçeve herhangi bir kenar içermez, ancak grafiğin tüm köşelerini içerir. Algoritmanın bir sonraki basamağından sonra, çerçevenin hali hazırda oluşturulmuş olan kısmı olan ormana bir kenar eklenir. Keyfi olarak seçilmedi. Grafiğin karelere ait olmayan tüm kenarları kırmızı ve yeşil olarak adlandırılabilir. Her bir kırmızı kenarın köşeleri, yapım aşamasında olan ormanın bağlantılarının bir bileşenindedir ve yeşilin köşeleri farklıdır. Bu nedenle, oraya kırmızı bir kenar eklersek, bir döngü belirir ve yeşil ise, bu adımdan sonra elde edilen ormanda, bağlantı bileşeni birer birer az olacaktır. Bu nedenle, sonuçtaki yapıya hiçbir kırmızı kenar eklenemez, ancak bir orman elde etmek için herhangi bir yeşil kenar eklenebilir. Ve minimum ağırlıkta yeşil bir kenar ekleyin. Sonuç, en düşük ağırlığın bir çerçevesidir.
uygulama
Mevcut orman F'yi gösterelim.Grafiğin tepe noktaları kümesini bağlantılı bölgelere böler (birleşim formları F'dir ve çiftler halinde kesişmezler). Kırmızı kenarların aynı kısımda her iki köşesi vardır. (X) bölümü, her bir köşe noktası için x'in ait olduğu parçanın adını döndüren bir işlevdir. Unite (x, y), x ve y parçalarının ve diğer tüm parçaların birleşiminden oluşan yeni bir bölüm oluşturan bir prosedürdür. Grafikteki kenar sayısı n olsun. Tüm bu kavramlar Kruskal'ın algoritmasına dahil edilmiştir. Uygulama:
Grafiğin tüm kenarlarını artan ağırlıklarda 1'den ’ye kadar sıralayın. (ai, bi, i sayısı olan kenarların köşeleridir).
i = 1 ila n yapın.
x: = Bölüm (ai).
y: = Bölüm (bi).
X, y'ye eşit değilse Unite (x, y), F'ye i kenarını dahil et.
Doğruluk
T, Kruskal algoritması kullanılarak oluşturulan orijinal grafiğin iskeleti ve S'nin keyfi iskeleti olsun. W (T) 'nin w (S)' yi geçmediğini kanıtlamamız gerekir.
M kenarlar kümesi olsun, P kenar kümesi olsunT. Eğer S, T'ye eşit değilse, T çerçevesinin S'ye ait olmayan bir kenarı vardır. E'yi S'ye bağlarız. Bir döngü oluşur, C diyelim S'ye ait herhangi bir kenarı C'den çıkarırız, çünkü kenarlar ve içinde pek çok zirve var. Kruskal algoritması sayesinde w (et) en fazla w (s) olduğundan ağırlığı w (S) 'yi geçmez. Bu işlemi (S kenarlarını T kenarları ile değiştirerek) T'yi elde edene kadar tekrarlayacağız. Sonuçta ortaya çıkan her bir çerçevenin ağırlığı, bir öncekinin ağırlığından daha büyük değildir, bu nedenle w (T), w (S) 'den büyük değildir.
Ayrıca, Kruskal'ın algoritmasının doğruluğu, matroidler üzerindeki Rado-Edmonds teoremini takip eder.
Kruskal algoritmasını kullanma örnekleri
A, b, c, d, e köşeleri ve kenarları (a,b), (a, e), (b, c), (b, e), (c, d), (c, e), (d, e). Kaburga ağırlıkları tablo ve şekilde gösterilmiştir. Başlangıçta, yapım aşamasındaki F ormanı grafiğin tüm köşelerini içerir ve herhangi bir kenar içermez. Kruskal'ın algoritması, en küçük ağırlığa sahip olduğu için ilk olarak kenarı (a, e) ekler ve a ve e köşeleri F ormanının farklı bağlantılı bileşenlerindedir (kenar (a, e) yeşildir), sonra kenar (c, d), bu nedenle Bu kenar, grafiğin F'ye ait olmayan kenarlarının en az ağırlığına sahip olması ve yeşil olması, ardından aynı nedenlerle kenar (a, b) eklenmiştir. Ancak kenar (b, e), kırmızı olduğu için, kalan kenarların en küçük ağırlığına sahip olmasına rağmen atlanır: b ve e köşeleri, F ormanının aynı bağlantılı bileşenine aittir, yani, F'ye bir kenar (b, e) eklersek, döngü. Daha sonra yeşil bir kenar (b, c) eklenir, kırmızı bir kenar (c, e) atlanır ve ardından d, e. Böylece (a, e), (c, d), (a, b), (b, c) kenarları sırayla eklenir. İlk grafiğin optimal iskeleti bunlardan oluşur. Bu durumda algoritma böyle çalışır Boyalı. Bunu bir örnek göstermiştir.
Şekilde, bağlı iki bileşenden oluşan bir grafik gösterilmektedir. Kalın çizgiler, Kruskal algoritması kullanılarak oluşturulan optimum tel kafesin (yeşil) kenarlarını gösterir.
Üstteki şekil orijinal grafiği ve alttaki şekil, dikkate alınan algoritma kullanılarak bunun için oluşturulan minimum ağırlık iskeletini gösterir.
Eklenen kenarların sırası: (1,6); (0.3), (2.6) veya (2.6), (0.3) - önemli değil; (3.4); (0.1), (1.6) veya (1.6), (0.1) de kayıtsızdır (5.6).
Kruskal'ın algoritması, örneğin, her ülkenin yerleşim yerlerinin yeni mahallelerinde ve diğer durumlarda iletişimin, yolların yerleştirilmesini optimize etmek için pratik uygulama bulur.
