Gönderen Konu: Tübitak Lise Takım Seçme 1993 Soru 4  (Okunma sayısı 2316 defa)

Çevrimdışı scarface

  • Lokman Gökçe
  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 3199
  • Karma: +22/-0
  • İstanbul
Tübitak Lise Takım Seçme 1993 Soru 4
« : Ağustos 08, 2013, 03:46:58 ös »
İki şehir arasında en fazla bir yol bulunmak şartı ile, $v$ adet şehrin kimileri bir yol ile birbirine bağlanmıştır. $e$, bu yolların sayısını göstermek üzere
  • $e<v-1$ olması halinde birinden diğerine seyahat edemeyeceğimiz en az bir çift şehrin bulunduğunu;
  • $2e>(v-1)(v-2)$ olması halinde herhangi iki şehir arasında bir seyahatın mümkün olduğunu gösteriniz.
« Son Düzenleme: Haziran 22, 2014, 09:33:11 öö Gönderen: geo »
Uğraşınca çözebileceğim zorlukta olan soruları çözmeyi severim.

Çevrimdışı geo

  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 1812
  • Karma: +8/-0
Ynt: Tübitak Lise Takım Seçme 1993 Soru 4
« Yanıtla #1 : Eylül 07, 2013, 04:59:47 ös »
  • $2$ şehir için en az  $1$ yol gerekli. $3$ şehir için en az $2$ yol gerekli. $v-1$ şehir için en az  $v-2$ yol gereksin. $v$ şehir için en az $v-1$ yol gerekeceğini tümevarımla göstereceğiz. Çizge kuramında $\sum d\left(v\right)=2|E|$ şeklinde köşelere ait derecelerin toplamı kenar sayısının iki katıdır diye bir kural var. Buna takılı kalmadan, her şehirden geçen yol sayısına o şehrin derecesi diyelim. Her yol iki köşeden geçtiğine göre, derecelerin toplamı yol sayısının iki katı kadar olacaktır. Tümevarıma geri dönersek, her şehrin derecesi $1$ den büyük olsaydı, $\dfrac{2v}{2}=v$ yol olurdu. Demek ki en az $1$ tane şehrin derecesi $1$. (Derecenin $0$ olması demek, o şehrin diğer şehirlerle bağlantısı yok demektir.) Bu şehrin bağlantısını diğer şehirlerden kopardığımızda, diğer şehirlerden birbirlerine gidilebilme koşulunda bir değişiklik yapmamış oluyoruz. Çünkü çıkardığımız şehir üzerinden başka bir şehre gidilemiyor. Bu $v-1$ şehir için en az $v-2$ yol gerekeceği tümevarım hipotezinde belirtildi. Şimdi bu çıkardığımız şehri, $v-1$ şehirli yol dağıtımına eklediğimizde en az $\left(v-2\right)+1=v-1$ yol gerekmiş olacak. Bu durumda $e<v-1$ için en az bir şehir çifti için güzergah yoktur.
  • Şehirler arasında böyle bir ulaşımın olmadığını varsayalım. Çizge kuramı üzerinden konuşursak, $G$ nin birbirinden bağımsız iki bileşenini ele alalım. $A=\dfrac{V\left(G\right)}{B}$ , $B\ \subset V\left(G\right)$, $v-1\ge \left|B\right|=k\ge 1$ ise $\left|A\right|=v-k$. $B$ deki şehirler ile $A$ nın herhangi bir şehrini bağlayan yol yok. $A$ da en fazla $\left( \begin{array}{c}
    v-k \\
    2 \end{array}
    \right)$, $B$ de de  en fazla $\left( \begin{array}{c}
    k \\
    2 \end{array}
    \right)$ kadar yol bulunabilir. Toplamda en fazla $\left( \begin{array}{c}
    k \\
    2 \end{array}
    \right)+\left( \begin{array}{c}
    v-k \\
    2 \end{array}
    \right)=\dfrac{k\left(k-1\right)}{2}+\dfrac{\left(v-k\right)\left(v-k-1\right)}{2}=\dfrac{v^2-2vk+2k^2}{2}\ $yol bulunabilir. Bu ifade $k=v-k$ olduğunda en küçük değerini, dolayısıyla da $k=1$ veya $k=v-1$ olduğunda en büyük değerini alacak. Demek ki bağlantısız bir çizge en fazla $\left( \begin{array}{c}
    1 \\
    2 \end{array}
    \right)+\left( \begin{array}{c}
    v-1 \\
    2 \end{array}
    \right)=\dfrac{\left(v-1\right)\left(v-2\right)}{2}$ adet kenar içerebiliyor. Bunun üzerine bir yol daha eklediğimizde, $e>\dfrac{\left(v-1\right)\left(v-2\right)}{2}$ şartı sağlanmış, çizge bağlı olmuş olacak. Bu durumda herhangi bir şehirden diğerine gitmek mümkün olmuş olacak.
« Son Düzenleme: Haziran 22, 2014, 09:33:05 öö Gönderen: geo »

 


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