Gönderen Konu: Köşe sayısı 1 den büyük olan ağaçta derecesi 1 olan iki köşe vardır {Çözüldü}  (Okunma sayısı 4025 defa)

Çevrimdışı Lokman Gökçe

  • Lokman Gökçe
  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 3.716
  • Karma: +23/-0
  • İstanbul
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ı).
« Son Düzenleme: Ekim 01, 2022, 04:22:48 ös Gönderen: Lokman Gökçe »
Uğraşınca çözebileceğim zorlukta olan soruları çözmeyi severim.

Çevrimdışı Lokman Gökçe

  • Lokman Gökçe
  • Administrator
  • Geo-Maniac
  • *********
  • İleti: 3.716
  • Karma: +23/-0
  • İstanbul
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) 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ı başlığında sunduğu kanıtta faydalı olduğunu görebiliriz.
Uğraşınca çözebileceğim zorlukta olan soruları çözmeyi severim.

 


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 35 36 37 
SimplePortal 2.3.3 © 2008-2010, SimplePortal