Eşleştirme algoritmaları, graf teorisindeki graf eşleştirme problemlerini çözmek için kullanılan algoritmalardır. Herhangi bir köşeyi paylaşmayan bir kenar kümesi çizilmesi gerektiğinde eşleştirme sorunu ortaya çıkar. Aslında bu kuramla ve sorunla hepimizin karşılaştığını söyleyebiliriz. “Elini kaldırmadan şu şekli çiz” ya da “aynı yoldan geçmeden bu noktalara uğra” türündeki problemlerin tamamı bu kuramla ve eşleştirme algoritmasıyla ilgilidir.
Grafik eşleştirme sorunları günlük aktivitelerde çok yaygındır. Çevrimiçi eşleştirme ve buluşma sitelerinden, tıbbi yerleşim yerleştirme programlarına kadar eşleştirme algoritmaları birçok landa kullanılır. Daha özel olarak, eşleşme stratejileri, Ford-Fulkerson algoritması ve Edmonds-Karp algoritması gibi akış ağı algoritmalarında çok faydalıdır.
5 noktadan birisinden başlayarak elinizi hiç kaldırmadan bu şekli çizebilir misiniz?
Graf eşleştirme problemleri genellikle, bir sınıftaki öğrencilerin kendi niteliklerine göre eşleştirilmesi tarzında, ortak köşeleri paylaşmayan uçlar kullanarak grafikler arasında bağlantı kurma; veya zirvelerin alt kümesinin ayırt edildiği ve bir alt gruptaki her tepe noktasının başka bir alt gruptaki bir tepe noktasıyla eşleştirilmesi gereken iki taraflı bir eşleştirme oluşturma durumlarından ortaya çıkabilir. Örneğin bipartit eşleştirme, bir çöpçatanlık sitesindeki kadın ve erkekleri eşleştirmek için kullanılır.
Değişken ve Çoğalan Yollar
Grafik eşleme algoritmaları, bir eşleşmedeki mevcut yaklaşık en uygun alt alanları tanımlamak için çoğu zaman belirli özellikleri kullanır, burada istenen hedefe ulaşmak için iyileştirmeler yapılabilir. İki ünlü özelliğe, bir grafiğin maksimum veya minimum eşleştirme içerip içermediğini veya eşleştirmenin daha da iyileştirilip geliştirilemeyeceğini hızlıca belirlemek için kullanılan yollara, çoğalan yollar veya değişken yollar denir
Grafik 1, iki taraflı grafiği bağlayan tüm kenarları mavi renkte göstermektedir. Eşleşen bir algoritmanın amacı, bu grafikte ve bütün iki taraflı grafik durumlarda, alt kümedeki A köşeleri arasındaki bağlantı sayısını, alt kümedeki B köşeleriyle en üst düzeye çıkarmaktır.
Grafik 1
Çoğu algoritma rastgele bir grafik içinde bir eşleşme oluşturarak başlar ve istenen amaca ulaşmak için eşleştirmeyi daha fazla ayrıntılı hale getirir.
Kırmızı kenarlarla temsil edilen GrafİK M1’in rastgele ilk eşleşmesi
Eşleşen M’nin görüldüğü olan Grafik 1’in, kenarları eşleşen bir yolu varsa alternatif bir yolu olduğu (M) ve eşleşmede yoksa, değişen şekilde bir yol varsa, alternatif bir şekilde olduğu söylenir. Alternatif bir yol genellikle benzersiz bir tepe noktasıyla başlar ve alternatif sırayı korurken yolun kuyruğuna başka bir kenar ekleyemediğinde sona erer.
Grafik 1’deki alternatif bir yol, eşleşme durumunda kırmızı kenarlarla temsil edilmiştir eşleşme olmadığında, yeşil çizgilerle birleşmiştir.
Eşleşmeler kırmızı kenarlarla, eşleşme olmayanlar yeşil kenarlarla gösterilmiş.
Ardından, bir çoğalma yolu, bitiş noktaları, yolun başlangıcı ve sonunda köşeler serbest veya eşleşmemiş köşeler olan bir yolu tanımlamak için alternatif bir yolun tanımına dayanır; köşeler eşleşmeye dahil değildir. Grafikteki genişleme yollarını bulmak, maksimum eşleşmenin bulunmadığını gösterir.
Ardından bir çoğalma yolu, bitiş eksenleri, yolun başlangıcındaki ve sonundaki köşeleri , serbest, eşleşmemiş köşeleri, eşleşmeye dahil edilmeyen köşeleri tanımlanmamış bir yol için alternatif bir yol tanımlaması oluşturur. Grafikte çoğalma yolu sinyalleri bulmak, maksimum eşleşmenin eksikliğine işaret eder.
Grafik 1 için M eşleşmesi serbest köşelerde başlamaz ve bitmez, bu nedenle bir çoğalma yolu yoktur. Bu, eşleşmenin bir maksimum eşleşme olduğunu gösterir.
Grafik Etiketleme
Gerçekçi eşleşme sorunlarının çoğu yukarıda sunulanlardan çok daha karmaşıktır. Bu artmış karmaşıklık genellikle, ağırlıklar, maliyetler, tercihler veya potansiyel eşleşmelere kısıtlamalar getiren diğer spesifikasyonlar gibi nicel niteliklere sahip kenarların veya köşelerin mevcut olduğu grafik etiketlemeden kaynaklanır.
Etiketleme ile ilgili bir grafikte incelenen yaygın bir özellik, olan olası etiketleme, bir kenara verilen değerin, ilgili tepe noktalarının ağırlıklarının katma değerini asla geçmediği, uygulanabilir bir etiketleme olarak bilinir. Bu özellik üçgen eşitsizliği olarak düşünülebilir.
Macar Eşleştirme Algoritması
Yaygın bir çift taraflı grafik eşleştirme algoritması, çoğaltma yolları bularak bir maksimum eşleşme sunan Macar maksimum eşleştirme algoritmasıdır. Daha resmi olarak, algoritma, çoğaltma yolları aracılığı ile mevcut eşleşme M için daha büyük bir eşleşme bulmayı amaçlar. Her artırma yolu bulunduğunda, eşleşme sayısı veya toplam ağırlık 1 artar. Ana fikir, M kısıtlamalarının ihlal edilmediğinden emin olarak en kısa büyütme yolu ile M artırılmasıdır.
Macar eşleştirme algoritması. İlk şekilde 4 vinç için atanmaları gereken 4 işe ulaşmaları gereken mesafeler gösterilmiştir. İşlemin ilk aşamasında her sıradaki minimum değer belirlenmiş ve sıralardaki değerlerden çıkartılmıştır. İkinci şekil bu sonucu göstermektedir. Burada yeni oluşan sütunlardaki en küçük değer belirlenmiş ve o sütundaki bütün değerlerden çıkartılmıştır. 3. şekilde her sıra ve sütunda bulunan 0 (sıfır) değerine öncelik verilmek üzere en küçük değerlerin eşleştirilmesi sağlanmıştır. Kırmızı ile işaretlediğimiz bölgeleri ilk şekildeki değerleri koyarak hesaplarsanız, minimum yol katetmek üzere yapılması gereken eşleşmeleri bulmuş olursunuz. Yani crane1-job3: 5 km, crane2-job2: 3km, crane3-job4 5km, crane4-job1 6km. Toplam 19 km yol almaları gerekecektir. Başka hiç bir atama şekli bu rakamın altına inilmesini sağlamayacaktır.
Algoritma, boş bir eşleme de dahil olmak üzere herhangi bir rastgele eşleştirme ile başlar. Ardından, çoğaltma yolunu bulmak için sığlık öncelikli aramasını kullanarak bir ağaç oluşturur. Arama bir çoğaltma yolu bulursa, eşleştirme bir kenar daha kazanır. Eşleştirme güncellendiğinde, algoritma devam eder ve yeni bir artırma yolu için tekrar arama yapar. Arama başarısız olursa, algoritma şu anki eşleşmenin mümkün olan en büyük eşleşme olmak zorunda olduğundan sona erer.