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

Problem: n1 köşeli (noktalı) bir ağaç çizgenin n1 kenarı vardır, kanıtlayınız.

 

 

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.

Lisans Matematik kategorisinde (2.6k puan) tarafından  | 545 kez görüntülendi

2 Cevaplar

1 beğenilme 0 beğenilmeme
En İyi Cevap
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>2 için  n köşeli ağaç çizgenin n1 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 n1 kenarı vardır. Bu ağaç çizgeden n+1 köşeli ağaç çizgeye geçebilmek için n inci  köşesini n+1inci köşeye birleştirmek gereklidir ve bunun için 1 kenara ihtiyaç vardır. O zaman n+1 köşeli bir ağaç çizgenin n1+1=n
kenarı vardır.
(3.2k puan) tarafından 
tarafından düzenlendi
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.
n+1 köşeli bir ağacın içinde n köşeli bir ağaç vardır
0 beğenilme 0 beğenilmeme
Tümevarımı biraz daha farklı biçimde uygulayarak yapılan bir başka ispatı paylaşabilirim.

 

 

İspat:

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

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

(İ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 Te çizgesi ile, bağlantısız iki küçük ağaç elde etmiş olduk. Bunlardan birinin n1 köşesi, diğerinin de n2 köşesi olsun. Elbette n1+n2=n dir. Tümevarım hipotezi gereğince bu küçük ağaçların sırasıyla n11 ve n21 tane kenarı vardır. Sildiğimiz e kenarını da hesaba katarak T ağacının kenar sayısını bulabiliriz:

(n11)+(n21)+1=(n1+n2)1=n1


elde edilir. Göstermek istediğimiz de buydu.
(2.6k puan) tarafından 
tarafından düzenlendi
20,296 soru
21,840 cevap
73,541 yorum
2,723,817 kullanıcı