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 TEORIJA SKUPOVA

k-regularan graf zadatak

[inlmath]C\backslash\left(A\cap B\right)=\left(C\backslash A\right)\cup\left(C\backslash B\right)[/inlmath]

k-regularan graf zadatak

Postod Zarko97 » Subota, 25. Februar 2017, 14:30

Kao prvo izvinjavam se ako postavljam temu koja već postoji, ili nije na odgovarajućem 'mestu'. Naime zadatak je iz predmeta diskretna matematika, ali na nekim smerovima se ovaj predmet zove i 'Teorija skupova i matematička logika'. Da ne dužim više zadatak glasi ovako:

Odrediti sve parove prirodnih brojeva [inlmath](n,k)[/inlmath] za koje važi: Postoji [inlmath]k[/inlmath]-regularan graf sa [inlmath]n[/inlmath] čvorova.

E sad, pod [inlmath]k[/inlmath]-regularnim grafom smatra se graf čiji čvorovi imaju jednake stepene, odnosno graf kod kog svaki čvor ima jedan broj grana. Evo i nekih primera [inlmath]k[/inlmath]-regularnih grafova:

Slika

Ali kako se radi ovaj zadatak, stvarno ne znam pa bi mi dobrodošla pomoć :)
Hvala unapred! :)
Zarko97  OFFLINE
 
Postovi: 1
Zahvalio se: 1 puta
Pohvaljen: 0 puta

Sharuj ovu temu na:

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

Re: k-regularan graf zadatak

Postod mala_mu » Nedelja, 26. Februar 2017, 17:28

Postoji predmet i 'Teorija grafova' :D

Da li ti je poznata Erdos Gallai teorema za niz stepena čvorova grafa, koja otprilike kaže: Niz stepena nekog grafa sa [inlmath]n[/inlmath] čvorova je [inlmath]d_1\ge\cdots\ge d_n\iff\sum\limits_{i=1}^nd_i[/inlmath] je parna i [inlmath]\sum\limits_{i=1}^pd_i\le p(p-1)+\sum\limits_{i=p+1}^n\min\{d_i,p\},\;p\in\{1,2,\ldots,n\}[/inlmath], za svako [inlmath]p[/inlmath], tako da [inlmath]1\le p\le n[/inlmath] ?

Dokažimo da je tvrdnja zadatka tačna za [inlmath]k[/inlmath] ili [inlmath]n[/inlmath] parno
Za [inlmath]d_1\ge\cdots\ge d_n=k[/inlmath] se lako ispituje
Za [inlmath]k=n-1[/inlmath] trivijalno znamo da postoji regularan graf [inlmath]K_n[/inlmath]
Pretpostavimo da je [inlmath]k<n-1[/inlmath]. Za [inlmath]1\le p\le k[/inlmath] je [inlmath]p(p-1)+p(k-p)+(n-k)k-pk=nk-k^2-p\ge nk-k^2-k=k(n-k-1)>0[/inlmath]
Za [inlmath]p>k[/inlmath] imamo [inlmath]p(p-1)+k(n-p)-pk=p^2-p(2k+1)+nk=\left(p-\frac{2k+1}{2}\right)^2+nk-\left(\frac{2k+1}{2}\right)^2[/inlmath]
Za [inlmath]k<n-1[/inlmath] je
[dispmath]4nk>4k^2+4k[/dispmath][dispmath]4nk\ge4k^2+4k+1[/dispmath][dispmath]4nk\ge(2k+1)^2[/dispmath] Te imamo da je [inlmath]p(p-1)+k(n-p)-pk\ge0[/inlmath]
Ako je [inlmath]kn[/inlmath] parno, tvrdnja zadatka je tačna
Sorry I'm late a black cat blocked my path so I had to take a different way then a dragon came down and blocked my path then I saw an old lady having trouble crossing the street so I helped her then a cat was stuck in a tree and the owners asked me to help then I got lost on the road of life
Korisnikov avatar
mala_mu  OFFLINE
Zaslužni forumaš
 
Postovi: 50
Lokacija: Banja Luka
Zahvalio se: 23 puta
Pohvaljen: 72 puta

  • +1

Re: k-regularan graf zadatak

Postod Daniel » Utorak, 28. Februar 2017, 18:48

mala_mu je napisao:Pretpostavimo da je [inlmath]k<n-1[/inlmath]. Za [inlmath]1\le p\le k[/inlmath] je [inlmath]p(p-1)+p(k-p)+(n-k)k-pk=nk-k^2-p\ge nk-k^2-k=k(n-k-1)>0[/inlmath]

Zapravo, nejednakost za ovaj slučaj bi trebalo da glasi (nakon uvrštavanja [inlmath]k[/inlmath] umesto [inlmath]d_i[/inlmath] i uslova da je [inlmath]\min\{k,p\}=p)[/inlmath]:
[dispmath]\underbrace{\sum\limits_{i=1}^pk}_{pk}\le p(p-1)+\sum_{i=p+1}^n\underbrace{\min\{k,p\}}_p\\
pk\le p(p-1)+\underbrace{\sum_{i=p+1}^np}_{(n-p)p}\\
pk\le p(p-1)+(n-p)p[/dispmath] Zatim podelimo obe strane sa [inlmath]p[/inlmath] (što smemo da učinimo, zbog uslova da je [inlmath]p\ge1[/inlmath], što znači da [inlmath]p[/inlmath] ne može biti ni nula ni negativno,
[dispmath]k\le\cancel p-1+n-\cancel p\\
k\le n-1[/dispmath] čime je dokazano da je polazna nejednakost ispunjena, jer je po pretpostavci [inlmath]k<n-1[/inlmath].



Inače, uslov da [inlmath]\sum\limits_{i=1}^nd_i[/inlmath] kod svih grafova (ne samo regularnih) mora biti parno prilično je očigledan. Pošto svaka grana koja povezuje dva čvora povećava stepen oba ta čvora za jedan, to povećava sumu svih stepena čvorova za dva (isti slučaj i s granama koje predstavljaju petlje, one povećavaju stepen tog jednog čvora za dva), odatle sledi da je suma stepena svih čvorova jednaka dvostrukom broju grana u grafu. A pošto je broj grana u grafu prirodan broj, sledi da suma stepena svih čvorova, kao proizvod prirodnog broja i broja dva, mora biti paran broj.
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 TEORIJA SKUPOVA

Ko je OnLine

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


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