Korisnički Kontrolni Panel
Pogledajte svoj profil
Pogledajte svoje postove
ČPP
Prijavite se

Matematički forum na kojem možete da diskutujete o raznim matematičkim oblastima, pomognete drugima oko rešavanja zadataka, a i da dobijete pomoć kada vam zatreba


















Index stranica OSTALE MATEMATIČKE OBLASTI GRAFOVI

Grafovi - Stablo

Grafovi - Stablo

Postod Batonja » Nedelja, 13. Maj 2018, 19:27

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.
Batonja  OFFLINE
 
Postovi: 94
Zahvalio se: 44 puta
Pohvaljen: 1 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+
  • +1

Re: Grafovi - Stablo

Postod ubavic » Ponedeljak, 14. Maj 2018, 09:49

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.
ubavic  OFFLINE
Zaslužni forumaš
 
Postovi: 623
Zahvalio se: 384 puta
Pohvaljen: 641 puta

Re: Grafovi - Stablo

Postod Batonja » Ponedeljak, 14. Maj 2018, 11:31

Jel znas kako bi trebao da ide dokaz? Radi se o grafu koji je i stablo a ne samo graf .
Batonja  OFFLINE
 
Postovi: 94
Zahvalio se: 44 puta
Pohvaljen: 1 puta

Re: Grafovi - Stablo

Postod ubavic » Ponedeljak, 14. Maj 2018, 12:42

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.
ubavic  OFFLINE
Zaslužni forumaš
 
Postovi: 623
Zahvalio se: 384 puta
Pohvaljen: 641 puta

Re: Grafovi - Stablo

Postod Batonja » Ponedeljak, 14. Maj 2018, 14:01

http://prntscr.com/jhoml4
Maksimalni broj cvorova 4 , stablo ima 3 viseca cvora a trebalo bi 4 ?
Batonja  OFFLINE
 
Postovi: 94
Zahvalio se: 44 puta
Pohvaljen: 1 puta


Povratak na GRAFOVI

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 0 gostiju


Index stranicaTimObriši sve kolačiće boarda
Danas je Utorak, 19. Mart 2024, 10:37 • Sva vremena su u UTC + 1 sat
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs