Geomania.Org Forumları
Fantezi Cebir => Kombinatorik => Konuyu başlatan: Lokman Gökçe - Eylül 25, 2022, 12:20:17 öö
-
Problem: $n\geq 1$ köşeli (noktalı) bir ağaç çizgenin $n-1$ kenarı vardır, kanıtlayınız.
Not: Bağlantılı olup döngü içermeyen çizgelere ağaç denir. Ağaç çizge ile ilgili buraya (https://en.wikipedia.org/wiki/Tree_(graph_theory)) bakılabilir.
-
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 ağaç çizgenin içinde $n$ köşeli bir ağaç çizge bulunur ve kabülümüze göre $n-1$ kenarı vardır. Bu ç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.
-
Tümevarımı biraz daha farklı biçimde uygulayarak yapılan bir başka ispatı paylaşabilirim.
İ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.