Akademisyenler öncülüğünde matematik/fizik/bilgisayar bilimleri soru cevap platformu
0 beğenilme 0 beğenilmeme
359 kez görüntülendi

$\color{red}{\textbf{Teorem:}}$ Köşe sayısı $1$ den büyük olan ağaç çizgede derecesi $1$ olan en az iki köşe vardır, ispatlayınız.

 

 

$\color{blue}{\text{Not:}}$ Bu teoremi, $n+1$ köseli bir ağacın içinde $n$ köşeli bir ağaç vardır probleminin çözümünde kullanabiliriz.

Lisans Matematik kategorisinde (2.6k puan) tarafından  | 359 kez görüntülendi
Bu soruya sonlu agaclar sarti getirmek lazim yoksa sonsuz binary agacin hic yapragi yok mesela
Teşekkürler @eloi , Elbette teorem sonlu çizgelerde geçerlidir. Yazdığım tüm çizge teorisi sorularında, aksi belirtilmedikçe çizgelerimiz "sonlu çizge" ve "basit çizge" dir. Bazı problemler basit/sonlu olmayan çizgelerde de doğru kalabilir. Bu problem özelinde, yazdığınız türde ters örnekler oluşacağı için "sonlu çizge" şartı kaldırılamaz. Sonlu çizgelerde ise kritik önemi olan kısım, extremal principle uygulayabilmemize olanak tanımasıdır.

2 Cevaplar

1 beğenilme 0 beğenilmeme
En İyi Cevap
Agacin uzerindeki maksimal yolu alalim. Bu yolun baslangic ve bitis noktasinin derecesi bir olmali cunku degilse ya en uzun yolu almamisiz ve yolumuzu uzatabiliriz yada elimizde bir dongu var
(1.6k puan) tarafından 
tarafından seçilmiş
0 beğenilme 0 beğenilmeme

Bir çizge teorisi kitabında okuduğum bir ispata detaylar ekleyerek paylaşıyorum. Kaynak olan kitabı hatırlayamıyorum. Uzun süre önce, eğer çizge teorisi çalışırsam bakarım diye not almıştım. Şimdi lazım oldu.

 

$\color{red}{\textbf{İ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. $ [ 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.

(2.6k puan) tarafından 
20,282 soru
21,821 cevap
73,503 yorum
2,529,622 kullanıcı