1 26 k = v K ∈ , jij KKKKKKKKKKKKK

2004 Aralık 2.Soru
Bir ülkedeki 80 kentten bazıları arasında karşılıklı uçak seferleri yapılmaktadır. Her kentten
en az 7 başka kente doğrudan uçak seferi bulunmakta olup, herhangi bir kentten bir diğerine doğrudan ya da sonlu sayıda aktarma yaparak uçakla ulaşmak mümkündür. Karşılıklı uçak seferleri hangi
kentler arasında düzenlenmiş olursa olsun. Herhangi bir kentten bir diğerine en çok
ulaşılmasını olanaklı kılan en küçük
k
k
aktarmayla
sayısını bulunuz.
Cevap: Bunu mümkün kılan en küçük k sayısı 26 dır.
Çözüm:
80 kentimizi 80 köşeli bir grafın köşeleri ve karşılıklı uçak seferlerini de bu köşeler arasındaki
yönlü kenarlar olarak düşünelim. k aktarma ile, yani grafımızı düşünürsek en fazla k  1 kenar üzerinden herhangi bir köşeden başka bir köşeye her zaman ulaşılmasını sağlayan en küçük k 'yı arıyoruz. Ayrıca her köşenin derecesinin en az 7 olduğunu biliyoruz.
Öncelikle k  26 aktarma için bir örnek verelim: K m ile m köşeli bir complete grafı gösterelim. Eğer her v1  Ki , K j deki köşelerden her birine direkt bağlı ve her v2  K j , K i deki köşelerden
her birine direkt bağlı ise bu durumu Ki  K j ile gösterelim. Dolayısıyla eğer Ki  K j ise bu
i  j köşe bir Ki  j oluşturur.
Grafımız şu şekilde olsun:
K5  K3  K3  K 2  K3  K3  K 2  K 3  ...  K 3  K 2  K 3  K 3  K 5
8 Köşe
8 Köşe
8 Köşe
8 Köşe
8 Köşe
Aradaki K3  K2  K3 üçlülerinden 8 tane olsun. Dolayısıyla toplamda 80 köşe vardır ve her köşenin derecesi en az 7 dir. Diğer taraftan en soldaki K 5 teki bir köşeden başlarsak, en sağdaki K 5 e
en az 27 kenar üzerinden yani 26 aktarma ile gidebiliriz. Ayrıca bu grafta belirtilen kenar bağlantıları
dışında bir kenar da olmasın. Şimdi 27 nin maksimum olduğunu ispatlayalım.
Grafımızı bir ağaç şeklinde ifade edeceğiz. Bir V köşesi seçelim ve ağacın en tepesine koyalım. V nin bir alt katmanına V nin direkt bağlı olduğu köşeleri yerleştirelim. Ondan sonra gelen her
k . katmana, 1, 2,..,(k 1). katmanlarda bulunma1.katman
V
yan ve (k  1). katmandaki köşelerden en az biri-
2.katman
ne direkt bağlı olan köşeleri yerleştireceğiz.
Grafımızın sonlu sayıda köşesi olduğundan, sonlu
sayıda katman yer alır.
3.katman
Toplam m katman olsun. t. katmanda da
at (1  t  m) alsın. Grafımız bağlantılı olduğundan bu “katmanlandırma” tüm köşeleri kapsar.
www.matematikolimpiyati.com®
1
Dolayısıyla a1  a2  ..  am  80 ve l . katmandaki bir köşenin direkt bağlı olduğu köşeler
sadece l. ,(l  1). veya (l  1). katmanlarda yer alabilir.
Fakat bir v1  l. katman alırsak, 7  der (vi )  (al  1)  al 1  al 1 olduğundan her m  1  l  2
için al 1  al  al 1  8 olmalıdır.
Ayrıca benzer mantıkla a1  a2  8 ve am1  am  8 olduğunu söyleyebiliriz. m  28 olduğunu göstermek istiyoruz, çünkü böylece V 'den herhangi bir köşeye en fazla m  1  27 kenar
kullanılarak ve dolayısıyla 26 aktarmada ulaşılmış olacak.
Aksini varsayalım, m  28 olsun. Her
r için ar  0 olduğundan :
80  a1  a2  ..  am  (a1  a2 )  (a3  a4  a5 )  ...  (a24  a25  a26 )  (a27  a 28  ..am 2 ) 
(am1  am )  (a1  a2 )  (a3  a4  a5 )  ...  (a24  a25  a26 )  (am1  am )  8  8..  8  80.
Böylece çelişki elde ederiz. Demek ki m  28 ve dolayısıyla m  1  27 bulunur.
Dolayısıyla en fazla 26 aktarma ile istenilen yere ulaşılır.
www.matematikolimpiyati.com®
2