Eşleme (Matching)

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.

1. Eşleşme Tipleri

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:

esleme

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.

eslesme

Ö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.

maximal

Ö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:

asgariesleme

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:

maximal

Yukarıdaki graf mükemmel eşleme değildir çünkü E ve F düğümleri eşleme dışında bırakılmıştır.

asgariesleme

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:

asgariesleme

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.

esleme

Ö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.

« Petri Ağları (Petri Nets) | Reichenbach Zaman Analizi (Reichenbachian Tense Analysis) »

Yorumlar

Bu Yazı Hakkında

Bilgisayar Kavramları üzerinde şu anda okumakta olduğunuz 'Eşleme (Matching)' isimli yazı 02 May 2009 tarihinde, saat: 23:32 'de Şadi Evren ŞEKER tarafından gönderilmiş, toplam 528 defa okunmuştur.

Benzer yazıları algoritma analizi (teory of algorithms), graf teorisi (graph theory, çizge kuramı), veri yapıları kategorilerinden okuyabilirsiniz. Yazar ile irtibat kurmak için email gönderebilirsiniz. Yazıya yorum yapabilir ya da yapılan yorumları RSS 2.0 ile takibe alabilirsiniz.

Yazarın Kitabı

Bu yazının yazarı Şadi Evren ŞEKER'in son çıkan kitabı "Programlama ve Veri Yapılarına giriş (C, C++ ve JAVA ile)" hakkında bilgi almak için Buraya tıklayabilirsiniz.
Eklenen Son Yazılar