2014 yılının Kasım ayında Rusya’nın St. Petersburg şehrinde bulunan dünyaca ünlü Hermitage müzesini ziyaret etmiştim. İçinde 1057 tane oda olan Hermitage’ı baştan sona yürüyen biri 22 km mesafe kat etmiş olur. Müzede bulunan eserlerin tamamına bakmak istiyorsanız, her esere sadece 1 dakika ayırsanız bile bu işi 11 yıldan önce bitirmenin mümkün olmadığını bilmeniz gerekir.
Bu yüzden Hermitage’ı sadece birkaç saatliğine ziyaret etmeye çalıştığımda nerede ne kadar süre geçirmem gerektiğini iyi ayarlamalıydım. Çünkü devasa müzeyi kısa sürede gezmem, ama bunu yaparken ilgimi çeken eserleri görmem gerekiyordu.
Aslında bu, çok orijinal bir problem değil. Hemen herkes günlük yaşamında bu tür problemlerle karşılaşır: “Ev-iş arasında hangi saatte hangi yolu kullanmalı?” gibi.
Postacının Yolu
St. Petersburg’da bu problemle karşılaşmam çok hoş bir tesadüftü. Çünkü Petersburg 18. yüzyılda ünlü matematikçi Leonhard Euler’e ev sahipliği yapmıştı. İlk graf yazısından hatırlayacağınız üzere Euler Königsberg’in yedi köprüsü problemiyle birlikte çizge teorisinin ortaya çıkmasına önayak olmuştu.
Königsberg probleminden 230 yıl sonra 1960’da Çinli bir matematikçi olan Mei-Ko Kwan soruyu biraz daha farklı şekilde ele almıştı:
Bir postacı rotasındaki evlere elindeki mektupları dağıtmak üzere posta ofisinden ayrılır. Postacının en kısa sürede tüm evlere uğrayıp tekrar posta ofisine dönmesi için nasıl bir rota izlemesi gerekir?
Kwan’a ithafen Çinli Postacı Problemi olarak bilinen bu problemde önemli olan detaylar şunlardır:
- Postacı rotası üzerindeki tüm sokakları kullanmalıdır. Fakat her sokak sadece ama sadece bir defa kullanılmalıdır.
- Postacının rotasında başlangıç ve bitiş posta ofisinde olmalıdır.
- Postacının amacı en kısa sürede yukarıdaki iki şartı yerine getirmektir.
Çizge Teorisinin Gücü
Mei-Ko Kwan Çinli Postacı Probleminin çözümünde Euler’in Königsberg’in yedi köprüsü için ortaya keşfettiklerinden yararlanmıştı. Kwan’a göre problem Euler’in yaptığı gibi graf haline getirebilirdi. Postacının gitmesi gereken mahalleler noktalarla, mahalleler arasındaki mesafeler (yani sokaklar) ise çizgilerle gösterilebilir.
Örnek Graf:
Hatırlatma
Euler döngüsü nedir?
Eğer bir grafta Euler döngüsü varsa o grafta bulunan tüm çizgiler bir ama sadece bir defa kullanılarak tam bir tur atılabilir demektir. Ayrıca Euler döngüsünde başlangıç ve bitiş aynı noktadadır.
Euler döngüsü ne zaman vardır?
Bir graftaki bir noktanın sahip olduğu çizgi sayısı, o noktanın derecesini verir. Eğer bir grafta Euler döngüsü varsa, o graftaki tüm noktalar çift derecelidir.
Çözüm
Anlaşıldığı üzere Çinli Postacı Probleminin çözümü için postacının rotasında Euler döngüsü olmalıdır. Örneğin postacının güzergahı aşağıdaki gibi olsun:
İlk yapılması gereken şey tüm noktaların (harflerin) sahip olduğu çizgi sayısını bulmak:
Yukarı görüldüğü üzere graftaki tüm noktalar çift derecelidir. Bu sayede hiç denememize bile gerek kalmadan bu rotada Euler döngüsü olduğunu söyleyebiliriz. O halde postacının en kısa sürede görevini tamamlaması için graftaki yolları kullanması yeterlidir:
Tek dereceli noktalar varsa grafa yeni çizgiler eklenerek (yani postacı yeni yollar üretmek zorundadır) tüm noktalar çift dereceye çevrilmelidir. Peki bu nasıl yapılır?
- Tek dereceli noktaları bul.
- Bu noktaları ikili gruplara ayır.
- İkili gruplar arası mesafeleri bul. En düşük mesafeliler eklenmesi gereken çizgileri belirtir.
- Çizgileri grafa ekle.
Yukarıda verdiğim mahalle örneği üzerinden giderek açıklamaya çalışalım. Sorun postacının A mahallesinden başlayıp yine A’da bitecek gününü en kısa sürede tamamlamak istemesidir.
Önce her mahallenin (yani noktanın) sahip olduğu yol sayısına (yani çizgi sayısına) bakalım:
Her nokta çift sayıda çizgiye sahip olsaydı burada bir Euler yolu olurdu ve postacının en kısa turu direk mesafelerin toplanmasıyla bulunabilirdi. Fakat A ve D noktalarının tek sayıda çizgiye sahip olması bunu engelliyor:
Bu durumda yapılması gereken şey, tek çizgiye sahip noktalar arasında yeni yol veya yollar yapmaktır. A ve D mahalleri arasında üç farklı yol vardır. Bunlardan en kısasını bulup grafa eklersek sorumuz çözülmüş olur:
A-D mahalleri arasındaki yollar yukarıdaki gibidir. Görüldüğü üzere en kısa süre direk A-D arasındaki yoldadır. O halde A-D arasına yeni bir yol eklersek postacının sorunu çözülmüş olur:
Bi’ Göz Atmakta Fayda Var
Aşağıdaki rotada A’dan başlayıp A’ya dönmesi gereken postacının en kısa yolu ne kadar süre alır? Bunu yapabilmek için kullanması gereken rota nedir?
M. Serkan Kalaycıoğlu
kmatematikatolyesi.com 