Gönderen Konu: Tübitak Lise 2. Aşama 2004 Soru 2  (Okunma sayısı 3096 defa)

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 1801
  • Karma: +8/-0
Tübitak Lise 2. Aşama 2004 Soru 2
« : Ağustos 06, 2013, 04:33:56 öö »
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 $k$ aktarmayla ulaşılmasını olanaklı kılan en küçük $k$ sayısını bulunuz.
« Son Düzenleme: Ocak 17, 2015, 01:48:31 ös Gönderen: geo »

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 1801
  • Karma: +8/-0
Ynt: 2 - Tashih edildi
« Yanıtla #1 : Ağustos 06, 2013, 05:08:55 öö »
(Burak VARICI)

Bunu mümkün kılan en küçük $k$ sayısı $26$ dır.

$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 $v_{1} \in K_{i} $, $K_{j} $deki köşelerden her birine direkt bağlı ve her $v_{2} \in K_{j} $, $K_{i} $ deki köşelerden her birine direkt bağlı ise bu durumu $K_{i} \leftrightarrow K_{j} $ ile gösterelim. Dolayısıyla eğer $K_{i} \leftrightarrow K_{j} $ ise bu $i+j$ köşe bir  $K_{i+j} $ oluşturur.

Grafımız şu şekilde olsun:   $\underbrace{K_{5} \leftrightarrow K_{3} }_{8 \text{ Köşe} }\leftrightarrow \underbrace{K_{3} \leftrightarrow K_{2} \leftrightarrow K_{3} }_{8 \text{ Köşe} }\leftrightarrow \underbrace{K_{3} \leftrightarrow K_{2} \leftrightarrow K_{3} }_{8 \text{ Köşe} }\leftrightarrow \dots\leftrightarrow \underbrace{K_{3} \leftrightarrow K_{2} \leftrightarrow K_{3} }_{8 \text{ Köşe} }\leftrightarrow \underbrace{K_{3} \leftrightarrow K_{5} }_{8 \text{ Köşe} }$ Aradaki  $K_{3} \leftrightarrow K_{2} \leftrightarrow K_{3} $ üç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 bulunmayan ve $(k-1).$katmandaki   köşelerden en az birine 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.

Toplam m katman olsun.  $t.$ katmanda da  $a_{t} {\rm \; }(1\le t\le m)$ alsın. Grafımız bağlantılı olduğundan bu "katmanlandırma''   tüm köşeleri kapsar.

Dolayısıyla $a_{1} +a_{2} +..+a_{m} =80$ ve $l.$ katmandaki bir köşenin direkt bağlı olduğu köşeler sadece $l.{\rm \; ,}(l-1).$ veya $(l+1).$ katmanlarda yer alabilir. 

Fakat bir $v_{1} \in l.$katman alırsak, $7\le der(v_{i} )\le (a_{l} -1)+a_{l-1} +a_{l+1} $ olduğundan her $m-1\ge l\ge 2$  için $a_{l-1} +a_{l} +a_{l+1} \ge 8$ olmalıdır.

Ayrıca benzer mantıkla $a_{1} +a_{2} \ge 8$ ve $a_{m-1} +a_{m} \ge 8$ olduğunu söyleyebiliriz. $m\le 28$ olduğunu göstermek istiyoruz,  çünkü böylece $V$'den herhangi bir köşeye en fazla  $m-1\le 27$  kenar kullanılarak ve dolayısıyla $26$ aktarmada ulaşılmış olacak.

Aksini varsayalım, $m>28$ olsun. Her $r$ için $a_{r} >0$ olduğundan :  $$\begin{array}{l}
80=a_{1} +a_{2} + \dots +a_{m} \\
=(a_{1} +a_{2} )+(a_{3} +a_{4} +a_{5} )+\dots+(a_{24} +a_{25} +a_{26} )+(a_{27} +a_{28} +..a_{m-2} ) +(a_{m-1} +a_{m} ) \\
>(a_{1} +a_{2} )+(a_{3} +a_{4} +a_{5} )+\dots+(a_{24} +a_{25} +a_{26} )+(a_{m-1} +a_{m} ) \\
\ge 8+8+ \dots +8=80.
\end{array}$$

Böylece çelişki elde ederiz. Demek ki $m\le 28$ ve dolayısıyla${\rm \; }m-1\le 27$ bulunur.

Dolayısıyla en fazla $26$ aktarma ile istenilen yere ulaşılır. $\triangleright $
« Son Düzenleme: Ocak 17, 2015, 01:48:35 ös Gönderen: geo »

Çevrimdışı efecan

  • G.O Yeni Üye
  • *
  • İleti: 5
  • Karma: +0/-0
Ynt: 2
« Yanıtla #2 : Ağustos 19, 2013, 06:12:15 ös »
Çözüm tashih edilmiştir.

Düzeltme:
5. satırda bir kod hatası yer alıyor. Ayrıca Burak Varıcı'nın yazdığı orjinalde yer alan resim eksik.

Çözüm düzeltildi
« Son Düzenleme: Nisan 23, 2016, 01:02:22 ös Gönderen: geo »
- Müsbet anlamda "Carpe Diem" -

 


Sitemap 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 
SimplePortal 2.3.3 © 2008-2010, SimplePortal