Geomania.Org Forumları
Fantezi Cebir => Kombinatorik => Konuyu başlatan: Lokman Gökçe - Eylül 28, 2022, 01:01:48 öö
-
Teorem: Köşe sayısı $1$ den büyük olan (sonlu) ağaç çizgede derecesi $1$ olan en az iki köşe vardır, ispatlayınız.
Bu teoremi kullanarak elde edilebileceğimiz kolay bir sonuç şudur:
Sonuç: $n+1$ köşeli bir ağacın içinde $n$ köşeli bir ağaç vardır ($n\ge 1$ tam sayı).
-
Teoremin İspatı: Çalıştığımız çizgelerin "sonlu" çizgeler olduğunu vurguladıktan sonra, ağaç çizgemizdeki yollar için en büyük değer/en küçük değer ilkesi (extremal principle (https://brilliant.org/wiki/extremal-principle/#:~:text=The%20extremal%20principle%20is%20a,can%20understand%20the%20simplified%20problem.)) gereğince, (en az) bir en uzun yol vardır. Daha sade bir dille, ağaç çizgeden yolların uzunluklarını listelersek listede bir minimum değer bir de maksimum değer olduğunu söyleyebiliriz. Örneğin, $[ 1, 1, 1, 2, 2, \dots , 9, 10, 10 ,10]$ gibi bir liste olabilir. Birden fazla en uzun yol varsa da bunlardan istediğimiz birini göz önüne alalım. Bu en uzun yolun başlangıç köşesi $A$, bitiş köşesi $B$ olsun. Bu yol, "en uzun" olduğu için $A$ ve $B$ köşelerinin dereceleri $1$ olmak zorundadır. Böylece, derecesi $1$ olan (en az) iki köşe elde etmiş olduk.
Sonucun İspatı: Köşe sayısı $n+1$ olan bir ağaç çizge ile ilgileniyoruz. "Köşe sayısı $1$ den büyük olan sonlu ağaç çizgede derecesi $1$ olan en az iki köşe vardır." teoreminden dolayı, derecesi $1$ olan bir $A$ köşesini göz önüne alalım. $A$ köşesi, $C$ köşesi ile bağlantılı olsun. Ağaç çizgeden $AC$ kenarını ve $A$ köşesini silelim, fakat $C$ köşesini silmeyelim. Böylece geriye kalan çizge, $n$ köşeye sahip olan bir ağaçtır.
Bu sonucun, Alper Çay hocamızın Ağaç Çizgenin Kenar Sayısı (https://geomania.org/forum/index.php?topic=7871.msg21769;topicseen#new) başlığında sunduğu kanıtta faydalı olduğunu görebiliriz.