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

$n \ge 4$ çift bir tam sayı olsun. Mertebesi $n$ olan $3$-düzenli bir çizgenin mevcut olması gerektiğini gösteriniz.

Örneğin: $K_4$ bu şartlarda bir çizge. Bu nedenle $n=4$ için böyle bir çizge mevcut.

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

Hocam çok cahilce soruyorsam affet ama mertebesi tek olan 3- düzenli çizge var mıdır?

Kose sayisi $n$ olsa, dereceler toplami $3n$  olur. Dereceler toplami cift olmali, "el sıkışma", bu nedenle $n$ kesinlikle cift olmali.

ooo pardon sorunun başında çift yazıyormuş zaten,özür dilerim.

2 Cevaplar

1 beğenilme 0 beğenilmeme
En İyi Cevap

Şöyle bir çizim yaptım: $n=4, 6, 8, 10$ durumlarını görüyoruz.

Önce kareleri yan yana ekleyerek şeklimizi donatıyoruz. Sonra her bir kare için sol alt köşeden sağ üst köşeye uzanan köşegeni çizerek donatıyoruz.. Son hamlede de, oluşan dikdörtgende kesikli çizgilerle gönünen köşegeni çiziyoruz. Yani sağ alttan sol üste doğru donatıyoruz. (Cinci Abla'nın graf teorisi anlattığını hayal edelim.)  

 

$\color{blue}{\text{Not:}}$ Bu çizim, Sercan hocamın açıkladığı yönteme eşdeğer olmalıdır.

(2.6k puan) tarafından 
tarafından düzenlendi
1 beğenilme 0 beğenilmeme

$n=4$ icin $K_4$ cizgesi $3$-duzenli.

$k \ge 4$ icin mevcut oldugunu var sayalim ve $k+2$ icin olasi gerektigini gosterelim:

$k$ icin var olan cizgenin koseleri $$v_1,\cdots, v_k$$ olsun ve buna su sekilde $$a,b$$ koselrini ekleyelim: cizgenin ilk halinden $$y$$  kosesi alalim ve buna komsu iki $$x,z$$ kose secelim. ($3$-duzenli oldugundan boyle $2$ kose var, hatta $3$ kose). Aradaki bu kenarlari silelim. (Eger basit cizge degilse aradaki kenarlardan birini secip silelim). Bu durumda dereceler $$d(x)=2,d(y)=1, d(z)=2$$ olur ve ilk cizgenin diger koselerinin derecesi $3$ olur. $a$ ile $b,x,y$ ve $b$ ile (ilk basta cizdigimiz $a$ ile arasindaki kose disinda) $y,z$ arasinda birer kose secelim. Bu koseler diger koselerin derecesini etkilemediginden $a,b,x,y,z$ disindaki koselerin derecesi $3$ olarak kalmaya devam eder ve $a,b,c,x,y$'nin dereceleri de $3$ tamamlanmis olur. Kisacasi mertebesi $k+2$ olan $3$-duzenli bir cizge elde etmis olduk.

Tumevarim ile ispat biter.

(25.3k puan) tarafından 
20,200 soru
21,728 cevap
73,277 yorum
1,888,015 kullanıcı