Ağaç Çizgenin Kenar Sayısı

Question

$\color{red}{\text{Problem:}}$ $n\geq 1$ köşeli (noktalı) bir ağaç çizgenin $n-1$ kenarı vardır, kanıtlayınız.

 

 

$\color{blue}{\text{Not:}}$

Bağlantılı ve döngü içermeyen çizgelere ağaç denir.  Ağaç çizge ile ilgili buraya veya site içinde şuraya bakılabilir.

Answer 1

Bilmediğim bir konu fakat kanıt tümevarımdan yapılır sanırım:

$n=1$ için ağaç çizge bir nokta ve sıfır kenardan , $n=2$ için iki nokta ve bunları birleştiren bir yoldan (kenar) ibaret olduğundan iddia doğru. $n\gt 2$ için  $n$ köşeli ağaç çizgenin $n-1$ kenarı olsun. Şimdi $n+1$ köşeli bir ağaç çizgenin $n$ kenarı olduğunu söyleyebilirsek kanıt tamamdır. Bu $n+1$ köşeli ağaç çizgenin içinde $n$ köşeli bir alt ağaç çizge bulunur ve kabülümüze göre $n-1$ kenarı vardır. Bu ağaç çizgeden $n+1$ köşeli ağaç çizgeye geçebilmek için $n$ inci  köşesini $n+1$inci köşeye birleştirmek gereklidir ve bunun için $1$ kenara ihtiyaç vardır. O zaman $n+1$ köşeli bir ağaç çizgenin $$n-1+1=n$$ kenarı vardır.

Comments

Bence ispatınız olmuş gibi görünüyor Alper hocam. Sadece ispatınızda bahsettiğiniz çizgelerin, "ağaç çizge" olduğunu vurgularsanız daha iyi olabilir diye düşündüm. Bildiğim bir başka tümevarım yardımıyla yapılan ispat var, onu da ekleyeceğim. Katkınız için teşekkür ederim.

---

Teşekkür ederim Lokman hocam. Dediğin minvalde eklemeler yaptım. Selamlar.

Answer 2

Tümevarımı biraz daha farklı biçimde uygulayarak yapılan bir başka ispatı paylaşabilirim.

 

 

$\color{red}{\textbf{İspat:}}$

$\bullet$ (Başlangıç basamağı) $n=1$ durmunda çizge yalnız bir noktadan oluşur ve hiç kenar içermediği için kenar sayısı $n-1=1-1=0$ özelliğini sağlamaktadır.

$\bullet$ (Tümevarım basamağı) $0<r<n$ aralığındaki her $r$ pozitif tam sayısı için $r$ köşeli ağaç çizgelerinin $r-1$ kenara sahip olduğunu kabul edelim.

$\bullet$ (İspat basamağı) $n>1$ köşeli bir $T$ ağacını göz önüne alalım. $T$ ağacının bir $e$ kenarını seçelim ve bu kenarı silelim. Fakat kenarın uç noktalarını silmeyelim. Böylece $T-e$ çizgesi ile, bağlantısız iki küçük ağaç elde etmiş olduk. Bunlardan birinin $n_1$ köşesi, diğerinin de $n_2$ köşesi olsun. Elbette $n_1 + n_2 = n$ dir. Tümevarım hipotezi gereğince bu küçük ağaçların sırasıyla $n_1 - 1$ ve $n_2 - 1$ tane kenarı vardır. Sildiğimiz $e$ kenarını da hesaba katarak $T$ ağacının kenar sayısını bulabiliriz:

$$(n_1 - 1) + (n_2 - 1) + 1 = (n_1 + n_2) - 1 = n - 1$$

elde edilir. Göstermek istediğimiz de buydu.