Grafovi - Stablo

PostPoslato: Nedelja, 13. Maj 2018, 19:27
od Batonja
Neka je G stablo i neka je [inlmath]\Delta(G) = k[/inlmath]. Dokazati da G ima bar k visecih cvorova.
Moje resenje:
Sobzirom da je k minimalni stepen povezanosti (svaki cvor ce biti povezan sa najmanje k ostalih) tu imamo k visecih cvorova, dalje svaki od tih cvorova ce biti povezan sa k-1 susedom (da bi se odrzao minimalni stepen k) sto je k*(k-1) > k , i kako idemo dublje u stablo povecavace nam se broj visecih cvorova => imacemo bar k visecih cvorova.

Razumem zadatak cak i mislim da razumem ideju ali nisam siguran da dobro dokazujem , ako moze neko strucan da pogleda i da mi kaze kako bi ovo trebalo da se uradi . Hvala

Nisam znao gde bih ovo smestio posto nema topic grafovi ili diskretna matematika. Ako sam pogresio molim moderatora da pomeri temu gde treba.

Re: Grafovi - Stablo

PostPoslato: Ponedeljak, 14. Maj 2018, 09:49
od ubavic
Prvo bih ti skrenuo pažnju da [inlmath]\Delta(G) = k[/inlmath] označava maksimalan stepen čvorova u grafu. Tako da ti dokaz nije uopšte dobar (krenuo si od loše pretpostavke). Skrenuo bih ti pažnju i na još neke greške koje si napravio u dokazu.

Batonja je napisao:Sobzirom da je k minimalni stepen povezanosti (svaki cvor ce biti povezan sa najmanje k ostalih) tu imamo k visecih cvorova...

Ovo u opšte nije tačno. Ako je neko [inlmath]k[/inlmath] minimalan stepen povezanosti u [inlmath]G[/inlmath] tada [inlmath]G[/inlmath] ne mora imati viseće čvorove (listove). Najjednostavniji primeri za to su ti kompletni grafovi. Takođe, da bi neki graf bio stablo, potreban uslov je da minimalan stepen čvorova u grafu bude [inlmath]1[/inlmath].

Ali ovo uopšte nije ni bitno, jer se zadatak odnosi na maksimalan stepen čvorova u grafu.

Batonja je napisao:i kako idemo dublje u stablo povecavace nam se broj visecih cvorova

Ovde vidim na šta ciljaš, i to nije tačno. Ako imaš neki čvor [inlmath]v[/inlmath], susedi njegovih suseda mogu biti susedi čvora [inlmath]v[/inlmath]. Opet kompletni grafovi su najjednostavniji primer.

I molim te koristi slova sa dijakritičkim znakovima (č, ć, đ, dž, š i ž), i Letex kodove oko svih matematičkih izraza i oznaka.

Re: Grafovi - Stablo

PostPoslato: Ponedeljak, 14. Maj 2018, 11:31
od Batonja
Jel znas kako bi trebao da ide dokaz? Radi se o grafu koji je i stablo a ne samo graf .

Re: Grafovi - Stablo

PostPoslato: Ponedeljak, 14. Maj 2018, 12:42
od ubavic
Nacrtaj jedno stablo sa maksimalnim stepenom većim od [inlmath]3[/inlmath], i posmatraj u njemu gde se se nalaze listovi u odnosu na čvor koji ima maksimalan broj suseda. Ovo tvrđenje je sasvim jednostvno, i odma se uočava zašto važi.

Re: Grafovi - Stablo

PostPoslato: Ponedeljak, 14. Maj 2018, 14:01
od Batonja
http://prntscr.com/jhoml4
Maksimalni broj cvorova 4 , stablo ima 3 viseca cvora a trebalo bi 4 ?