MATEMANIJA

Hteo bih da pitam u vezi 2 zadatka, sličan im je tekst ali mi nije najjasniji jedan deo kod njih:

Prvi zadatak - Da li postoji stablo sa [inlmath]9[/inlmath] čvorova u kom dva čvora imaju stepen [inlmath]5[/inlmath]?

Oni su pretpostavili (da osim [inlmath]2[/inlmath] čvora koja imaju stepen [inlmath]5[/inlmath]) da preostalih [inlmath]7[/inlmath] čvorova imaju stepen [inlmath]1[/inlmath].

Međutim, u ovom zadatku je totalno druga priča;

Neka je [inlmath]T[/inlmath] stablo sa [inlmath]12[/inlmath] čvorova koje sadrži tačno [inlmath]3[/inlmath] čvora stepena [inlmath]3[/inlmath] i tačno [inlmath]1[/inlmath] čvor stepena [inlmath]2[/inlmath].

Kod ovog zadatka su rekli (osim [inlmath]3[/inlmath] čvora stepena [inlmath]3[/inlmath] i [inlmath]1[/inlmath] čvor stepena [inlmath]2[/inlmath]) da imamo sigurno i [inlmath]2[/inlmath] čvora stepena [inlmath]1[/inlmath] jer svako stablo ima [inlmath]2[/inlmath] viseća čvora, ali zbog čega to nisu primenili i u prethodnom zadatku? Takođe za preostalih [inlmath]6[/inlmath] sad nisu rekli da su stepena [inlmath]1[/inlmath] kao u prethodnom zadatku.

U prvom zadatku treba iskoristiti činjenicu da je kod stabla broj grana za [inlmath]1[/inlmath] manji od broja čvorova, kao i činjenicu da je (kod svakog grafa, a samim tim i kod stabla) zbir stepena svih čvorova jednak broju grana pomnoženom sa [inlmath]2[/inlmath]. Takođe, i činjenicu da kod stabla nijedan čvor ne može imati stepen [inlmath]0[/inlmath] (jer stablo mora biti povezan graf).

Za drugi zadatak nisi naveo kompletan tekst (napisao si samo prvu rečenicu), tako da je nejasno kako glasi pitanje, pa ne mogu ni da ga komentarišem.

Izvinjavam se, zaboravio sam da dodam. Odnosio se na deo pod a), gde se traži - Odrediti niz stepena čvorova stabla [inlmath]T[/inlmath].

Kod tog dela su napisali ono što sam napisao za taj drugi zadatak. Osim [inlmath]3[/inlmath] čvora stepena [inlmath]3[/inlmath] i jednog čvora stepena [inlmath]2[/inlmath], što za preostalih [inlmath]8[/inlmath] čvorova nisu rekli da ima stepen [inlmath]1[/inlmath] kao što su to pretpostavili u prvom zadatku?

Pa različite stvari se traže u prvom i u drugom zadatku. U prvom se ispituje mogućnost postojanja zadatog grafa. Pretpostavili su najpovoljniji slučaj za postojanje – a to je da su stepeni preostalih čvorova [inlmath]1[/inlmath]. Ako se pokaže da u tom slučaju graf ne može postojati, neće moći postojati ni u nepovoljnijem slučaju, a to je da neki od preostalih čvorova (ili svi) imaju stepene veće od [inlmath]1[/inlmath].

U drugom zadatku se ne traži ispitivanje postojanja datog grafa (čak se postojanje istog i ne dovodi u pitanje), već treba odrediti koliko ima čvorova s kojim stepenom. Znači, dato je da tačno [inlmath]3[/inlmath] čvora ima stepen [inlmath]3[/inlmath], tačno [inlmath]1[/inlmath] ima stepen [inlmath]2[/inlmath], a takođe su zaključili i da bar [inlmath]2[/inlmath] čvora imaju stepen [inlmath]1[/inlmath]. Pošto je poznat ukupan broj čvorova, a takođe se (na osnovu broja grana) može naći i koliko mora iznositi zbir stepena svih čvorova, preostaje samo jedna mogućnost za stepene preostalih čvorova.

Sada kada ponovo obnavljam grafove, kod drugog navedenog zadatka mi nije bio jasan nastavak.

Prvo ću citirati njihovo celo rešenje.

Kako su stabla povezani grafovi, imamo da je [inlmath]b(T)\ge1[/inlmath]. Osim stepena četiri čvora koji su dati u uslovu zadatka, znamo da sigurno imamo i dva čvora stepena [inlmath]1[/inlmath], jer svako stablo ima bar dva viseća čvora. Sada važi [inlmath]2\cdot11=\sum d(v)=2\cdot1+1\cdot2+3\cdot3+\sum'd(v)[/inlmath], gde smo sa [inlmath]\sum'd(v)[/inlmath] označili sumu stepena preostalih šest čvorova. Dobijamo da je [inlmath]\sum'd(v)=9[/inlmath], pri čemu u sumi imamo šest sabiraka i [inlmath]d(v)\in\{1,4,5,\ldots,11\}[/inlmath]. Kako je ovo ispunjeno samo ako jedan čvor ima stepen [inlmath]4[/inlmath], a ostalih pet čvorova su viseći, dobijamo da je niz stepena čvorova posmatranog stabla [inlmath]4,3,3,3,2,1,1,1,1,1,1,1[/inlmath]


Jasno mi je sve do dela kad smo odredili da je [inlmath]\sum'd(v)=9[/inlmath]. E sad, zbog čega su kod navedenog skupa izostavili brojeve tipa [inlmath]2,3[/inlmath], nego su išli [inlmath]1,4,5[/inlmath]. Takođe, nisam shvatio šta [inlmath]4[/inlmath] ispunjava kao i zbog čega je [inlmath]4[/inlmath] na prvom mestu i kako smo dobili ovih [inlmath]6[/inlmath] jedinica na kraju (mislim, intuitivno bih rekao da je [inlmath]1[/inlmath], ali ne bih znao da objasnim zbog čega)?

Acim je napisao:E sad, zbog čega su kod navedenog skupa izostavili brojeve tipa [inlmath]2,3[/inlmath], nego su išli [inlmath]1,4,5[/inlmath].

Zato što je u tekstu zadatka rečeno da graf ima tačno [inlmath]3[/inlmath] čvora stepena [inlmath]3[/inlmath] i tačno [inlmath]1[/inlmath] čvor stepena [inlmath]2[/inlmath]. Ako bi se među ovim čvorovima nepoznatih stepena nalazio i neki sa stepenom [inlmath]3[/inlmath], tada unutar celog grafa ne bismo imali tačno [inlmath]3[/inlmath] čvora stepena [inlmath]3[/inlmath], nego bismo ih imali više, što je protivno uslovu zadatka. Slično i za stepen [inlmath]2[/inlmath]. Iz tog razloga, među preostalim čvorovima ne smeju se nalaziti čvorovi sa stepenom [inlmath]2[/inlmath] i sa stepenom [inlmath]3[/inlmath].

Acim je napisao:Takođe, nisam shvatio šta [inlmath]4[/inlmath] ispunjava kao i zbog čega je [inlmath]4[/inlmath] na prvom mestu i kako smo dobili ovih [inlmath]6[/inlmath] jedinica na kraju (mislim, intuitivno bih rekao da je [inlmath]1[/inlmath], ali ne bih znao da objasnim zbog čega)?

To što je [inlmath]4[/inlmath] na prvom mestu ne moraš da gledaš. Niz je, jednostavno, napisan u nerastućem redosledu. Mogao je isto tako biti napisan i u neopadajućem, pa i u proizvoljnom redosledu.
E sad, kako smo došli do toga da postoji čvor stepena [inlmath]4[/inlmath] – pa, sistemom eliminacije. Ako bismo pretpostavili da među tih [inlmath]6[/inlmath] čvorova nepoznatog stepena postoji jedan koji je stepena [inlmath]5[/inlmath] (ili većeg), to bi značilo da, pošto stepeni ostalih [inlmath]5[/inlmath] čvorova moraju biti najmanje [inlmath]1[/inlmath], ukupan zbir stepena tih [inlmath]6[/inlmath] čvorova mora biti najmanje [inlmath]10[/inlmath], što je u suprotnosti s ranijim zaključkom da njihov zbir mora biti [inlmath]9[/inlmath]. Kontradikcija. Znači, stepeni tih nepoznatih čvorova mogu biti samo [inlmath]1[/inlmath] ili [inlmath]4[/inlmath] (za [inlmath]2[/inlmath] i [inlmath]3[/inlmath] napisah gore zašto ne mogu da budu). Dalje, nemoguće je da postoji više od jednog čvora stepena [inlmath]4[/inlmath], jer bi tada zbir tih [inlmath]6[/inlmath] čvorova, računajući i one preostale čiji je stepen [inlmath]1[/inlmath], morao biti najmanje [inlmath]12[/inlmath], što je opet kontradikcija. S druge strane, kad ne bismo imali nijedan čvor stepena [inlmath]4[/inlmath] već bi svi bili stepena [inlmath]1[/inlmath], tada bi njihov zbir bio [inlmath]6[/inlmath], iako mora biti [inlmath]9[/inlmath]. Prema tome, jedini slučaj koji preostaje jeste da jedan čvor ima stepen [inlmath]4[/inlmath], a preostalih [inlmath]5[/inlmath] imaju stepen [inlmath]1[/inlmath] – i zbir njihovih stepena je tada [inlmath]9[/inlmath], dakle sve se slaže.

Kako bi ti ovo bilo do kraja jasno, preporučujem da pokušaš da nacrtaš najmanje jedan primer ovakvog grafa.