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

Određivanje stepena čvorova stabla

Određivanje stepena čvorova stabla

Postod Acim » Nedelja, 05. Mart 2023, 09:20

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.
Acim  OFFLINE
 
Postovi: 370
Zahvalio se: 221 puta
Pohvaljen: 55 puta

Sharuj ovu temu na:

Share on Facebook Facebook Share on Twitter Twitter Share on MySpace MySpace Share on Google+ Google+

Re: Određivanje stepena čvorova stabla

Postod Daniel » Utorak, 07. Mart 2023, 07:41

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.
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 9300
Lokacija: Beograd
Zahvalio se: 5151 puta
Pohvaljen: 4951 puta

Re: Određivanje stepena čvorova stabla

Postod Acim » Sreda, 08. Mart 2023, 11:44

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?
Acim  OFFLINE
 
Postovi: 370
Zahvalio se: 221 puta
Pohvaljen: 55 puta

  • +1

Re: Određivanje stepena čvorova stabla

Postod Daniel » Petak, 10. Mart 2023, 08:26

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.
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 9300
Lokacija: Beograd
Zahvalio se: 5151 puta
Pohvaljen: 4951 puta

Re: Određivanje stepena čvorova stabla

Postod Acim » Subota, 22. April 2023, 15:59

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  OFFLINE
 
Postovi: 370
Zahvalio se: 221 puta
Pohvaljen: 55 puta

  • +1

Re: Određivanje stepena čvorova stabla

Postod Daniel » Subota, 22. April 2023, 18:00

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.
I do not fear death. I had been dead for billions and billions of years before I was born, and had not suffered the slightest inconvenience from it. – Mark Twain
Korisnikov avatar
Daniel  OFFLINE
Administrator
 
Postovi: 9300
Lokacija: Beograd
Zahvalio se: 5151 puta
Pohvaljen: 4951 puta


Povratak na GRAFOVI

Ko je OnLine

Korisnici koji su trenutno na forumu: Nema registrovanih korisnika i 1 gost


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