Tübitak Lise Takım Seçme 1993 Soru 4

[Lokman Gökçe]

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

[geo]

• $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.