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

Komplement grafa G

Komplement grafa G

Postod Acim » Četvrtak, 08. Jun 2023, 21:23

Unapred se izvinjavam što nemam precizan tekst zadatka, nisu nam dali sa ispita da iznesemo, ali bih samo pitao za ideju kako bi trebao da se reši, pošto na istom nisam uspeo da ga "izguram" do kraja.
Dokazati da je komplement grafa [inlmath]G[/inlmath] kod koga je stepen svakog čvora [inlmath]25[/inlmath] Hamiltonov.


Pre svega, nisam najbolje shvatio šta predstavlja komplement grafa [inlmath]G[/inlmath] nego sam prvo iz osnovne teoreme izrazio da mi je [inlmath]n\le\frac{2e}{25}[/inlmath].

Onda, primenio sam teoremu Dirak, tj. da je [inlmath]d(v)\ge\frac{n}{2}[/inlmath], odakle sam dobio da je [inlmath]n\ge\frac{2e}{1250}[/inlmath], odakle nisam znao šta dalje da radim.

U početku sam mislio da fali još neki podatak, međutim samo nam je to bilo dato.

Hvala unapred na pomoći.
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: Komplement grafa G

Postod Daniel » Petak, 09. Jun 2023, 15:16

Biće da u tekstu ipak nešto nedostaje. Jer, ovako kako je napisano, nije teško naći kontraprimer:
Neka graf [inlmath]G[/inlmath] ima [inlmath]26[/inlmath] čvorova. Pošto je stepen svakog čvora [inlmath]25[/inlmath], znači da je graf kompletan. Komplement grafa [inlmath]G[/inlmath] samim tim će biti prazan graf (komplement nekog grafa dobijamo time što tamo gde postoje grane uklanjamo ih, a tamo gde grane ne postoje umećemo ih). A čim je komplement grafa [inlmath]G[/inlmath] prazan graf, znači da ne može biti Hamiltonov.
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: 9323
Lokacija: Beograd
Zahvalio se: 5173 puta
Pohvaljen: 4960 puta


Povratak na GRAFOVI

Ko je OnLine

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

cron

Index stranicaTimObriši sve kolačiće boarda
Danas je Utorak, 16. Jul 2024, 02:06 • Sva vremena su u UTC + 1 sat [ DST ]
Pokreće ga phpBB® Forum Software © phpBB Group
Prevod – www.CyberCom.rs