Yazan : Şadi Evren ŞEKER
Bilgisayar bilimlerinde çeşitli amaçlar için kullanılan eşleştirme problemlerinin genel ismidir. Genellikle bir arz ile bir talebin eşleştirilmesi şeklinde olur. Örneğin bilgisayarın kaynaklarının, bu kaynakları talep eden işlemler ile eşleştirilmesi gibi. Ya da gerçek hayattan bir çalışanın uygun iş ile eşleştirilmesi veya evlilik problemleri veya iş akış diyagramları (işin doğru kaynak üzerinden akması) gibi problemler bu grupta sayılabilir.
İçerik
1. Eşleme Tipleri
a. Çoklu Eşleme (Maximal Matching)
b. Asgari Eşleme (Maximum Matching)
c. Mükemmel Eşleme (Perfect Matching)
d. Yaklaşık Mükemmel Eşleme (Near Perfect Matching)
2. Eşleme yolları
a. Dalgayı yol (Alternating Path)
b. Uzatılmış Yol (Augmented Path)
Eşleme problemleri genel olarak bir graf problemi olarak da düşünülebilir. Yani amaçlanan eşleme işlemi bir graf ile modellenebilir ve bu model üzerinde graf teorsinin bize sunduğu bütün imkanlar kullanılabilir.
Örneğin Petri Ağları (Petri Networks) bu konuda oldukça uygun bir çözüm ortamıdır. Benzer şekilde koşul programlama (constraint programming) başlığı altında da pek çok graf modellemesi ve çözümü (örneğin kiriş koşulu (arc constraint) ) kullanmak mümkündür.
Eşleme problemlerinde genellikle kenar bağımsız kümesi (edge independent set) bulunmaya çalışılır. Bu küme genellikle eşleşecek olan varlıkları ( grafta genellikle düğümler (nodes) ile gösterilir) eşlenmiş olarak modeller ve eşlenmeyen dışarıda kalan düğümlerin tespitini kolaylaştırır.
Bir grafta bulunan bir düğüm (node , vertex) şayet bir kenara (edge) bağlıysa bu düğüm eşleşmiş kabul edilir (matched). Şayet bir kenara bağlı değilse, eşleşmemiş (unmatched) kabul edilir.
a. Çoklu Eşleşme (Maximal Matching)
Bir grafta ortak düğümleri bulunmaksızın alınabilecek en fazla kenar sayısı o grafın çoklu eşlemesini veriri (maximal match). Örneğin aşağıda bu duruma örnek graflar bulunmaktadır:
Yukarıdaki grafta 3 kenar (edge) bulunmaktadır ve çoklu eşleşme bu kenarlardan sadece birisinin alınması ile olabilir. YAni A-K kenarı alındığı için B-K veya C-K kenarları alınamaz çünkü bu kenarlardan herhangi birisinin daha alınması durumunda K düğümü ile ortak kesişim düğümü bulunmuş olacaktır.
Alternatif olarak yukarıdaki grafta sadece B-K veya sadece C-K düğümleri alınabilir. Ancak yukarıdaki çoklu eşleme sonucunda 1 kenar alınabilmektedir.
Örneğin yukarıdaki grafta çoklu eşleşme sonucunda iki kenar alınabilmektedir. Yukarıdaki grafta bu kenarlar Ş-İ ve A-D olarak belirlenmiştir. Alternatif olarak Ş-A ve D-İ kenarları da olabilirdi ancak örneğin Ş-A ve A-D kenarları aynı anda alınamaz çünkü bu durumda A düğümü hem Ş hem de D düğümü ile eşleşmiş olur.
Amacımız olan eşleşmeye geri dönecek ve bu bilgiyi yorumlayacak olursak. Bir düğüm (bir kaynak, kişi ya da varlık) sadece bir düğüm ile eşleşebilir. Örneğin bir kişi sadece bir başka kişi ile evlenebilir veya bir kişinin sadece bir işi olabilir şeklinde düşünülebilir. Bu durumun dışındaki talepler graf teorisinde farklı şekillerde çözülür. Şimdilik bu eşleşme tanımı üzerinden farklı eşleşme türlerini tanıyalım.
b. Azami Eşleme (Maximum Matching)
Azami eşleme, çoklu eşlemeden farklı olarak bir grafta bulunabilecek en fazla eşi arar. Örneğin aşağıdaki şekilde bu iki eşleme arasındaki farkı görebiliriz.
Örneğin yukarıdaki şekilde birbiri ile komşu olmadığı için alınan iki kenar (edge) görülüyor. Bu durumda yukarıdaki graf çoklu eşleme (maximal matching) için uygun bir graf iken azami eşeleme (maximum matching) kabul edilemez. Yukarıdaki grafın azami eşleme olması için aşağıdaki şekilde alınabilecek en fazla kenarı eşlemesi gerekir:
Yukarıdaki şekilde, bir önceki şekilden farklı olarak iki kenar yerine 3 kenar alınmıştır. Yukaırdaki şekilde 4 kenar eşlemenin imkanı bulunmadığı için azami eşleme (maximum matching) olarak kabul edilebilir.
c. Mükemmel Eşleme (Perfect Matching)
Şayet bir graftaki bütün düğümler bir başka düğüm ile eşlendiyse ve eşleşmemiş bir düğüm kalmadıysa bu eşleme tipine mükemmel eşleme ismi verilir.
Örneğin aşağıdaki grafta yapılan eşleme mükemmel eşleme değildir:
Yukarıdaki graf mükemmel eşleme değildir çünkü E ve F düğümleri eşleme dışında bırakılmıştır.
Buna karşılık yukarıdaki eşleme mükemmel eşleme olarak kabul edilebilir çünkü bütün düğümler en az bir eşlemenin içine alınmıştır.
d. Yaklaşık Mükemmel Eşleme (Near Perfect Matching)
Bu eşleme, mükemmel eşlemeden farklı olarak tek bir düğümün eşlenmemesi durumunu kabul eder. Yani grafta şayet tek sayıda düğüm varsa eşleme sonucunda bir düğümün dışarıda kalması zaten beklenen bir durumdur. İşet bu durumda diğer bütün düğümler eşleniyor ancak tek bir düğüm dışarıda kalıyorsa buna yaklaşık mükemmel eşleme ismi verilir.
2. Eşleme sonucu yollar (Paths)
Bir eşleme (matching) işlemi sonucunda grafta elde edilen yollar için aşağıdaki tanımlar yapılabilir.
a. Dalgalı Yol (Alternating Path)
Şayet grafta elde edilen yol bir eşlenmiş bir de eşlenmemiş şeklinde devam ediyorsa bu yola dalgalı yol ismi verilir.
Örneğin aşağıdaki grafta bu durum görülebilir:
Yukarıdaki grafta F-İ-Ş-A-D-E yolu veya F-İ-D-E yolu birer dalgalı yoldur çünkü yoldaki eşlemeler sonucunda geçilen kenarlar bir eşlenmiş bir de eşlenmemiş olarak sınıflandırlabilir.
b. Uzatılmış Yol (Augmented Path)
Bir dalgalı yolun ilave bir düğüm ile başlaması durumudur. Yani şayet yola eşleşmemiş bir düğüm ile başlanıyorsa yada farklı bir ifadeyle başlanan düğüm herhangi bir eşleme içerisinde değilse bu yola uzatılmış yol ismi verilir.
Örneğin yukarıdaki şekilde C-K-A veya B-K-A yolları uzatılmış yollara örnektir. Başlana düğümler herhangi bir eşleme içerisinde değildir.