Forum@DeGiorgi :: Pogledajte temu - eulerov, Hamiltonov, planaran graf

through

[^/[Print]\]
Idite na 1, 2 Sljedeće :| |:
Forum@DeGiorgi -> Diskretna matematika

#1: eulerov, Hamiltonov, planaran graf Autor/ica: Luuka, Lokacija: Hakuna Matata

Postano: 11:28 čet, 14. 2. 2008
—
Imam jednu malu zamolbu...

izgleda da nisam bio na nekim vježbama (ili zakasnio) pa nemam sve u bilježnici... Embarassed

jel bi mogli tu napisat glavne 'teoreme' što se tiču gore navedenih svojstava grafa? Neke ograde na broj bridova, stupanj vrhova, područja i sl...nešto poput ovog kaj je rafaelm napiso...

hvala... Smile

#2: Autor/ica: sun,

Postano: 16:06 čet, 14. 2. 2008
—
tm. p-q+r=2
tm. suma d(f)=2*E(G)

zad. jedn.povezan planaran graf s n vrhova ima najvise 3n-6 bridova
zad. ocjena za bipartitne q<=2n-4

Euler:

tm. ono sa a) i b) mulitgraf bez izoliranih je eul akko.. to imas u pred
tm(Ore)
korolar (Dirac)
zad. graf sa n vrhova i 2+1/2 * (n-2)(n-1) bridova je hamiltonov

mislim da je to to.... Smile

#3: Autor/ica: desire,

Postano: 16:11 čet, 14. 2. 2008
—
E kad smo vec kod toga, aj vi meni recite cemu ta 2 teorema sluze (Dirac i Ore). Jer gledajuci ove zadatke sa vjezbi, niti jedan od njih ne vrijedi, a graf ipak je Hamiltonov. A sta ce mi onda uopce ovi teoremi kad su skoro pa neprimjenjivi. Confused

I jos nesto. Moze li mi netko napisati kako se dokazuje jedan teorem sa predavanja, ostavljeno nam je to za dz:
Graf je stablo ako i samo ako ne sadrzi cikluse, ali dodavanjem bilo kojeg novog brida dobivamo ciklus.

Hvala

#4: Autor/ica: Luuka, Lokacija: Hakuna Matata

Postano: 16:22 čet, 14. 2. 2008
—
@sun Hvala! karma++

desire (napisa):

Graf je stablo ako i samo ako ne sadrzi cikluse, ali dodavanjem bilo kojeg novog brida dobivamo ciklus.

→ graf je stablo. Pošto je graf stablo, onda nema ciklusa i povezan je(iz definicije). Pošto je povezan ima samo 1 komponentu povezanosti, dakle postoji put između svaka 2 vrha. Uzmimo a,b nesusjedne vrhove. Ubacimo e=(a,b) u graf i dobivamo ciklus jer postoji put između a i b. (a,v1,v2,..,vn,b,a) pa graf više nije stablo.

← ono drugo vrijedi. Želimo dokazati da je graf stablo. Po prep nema ciklusa, još treba dokazati da je povezan. Da bi bio povezan mora imati jednu komp povezanosti. P.S. da ima više komp povezanosti, A1 i A2 (može i više, pa one druge stavimo u uniju koju nazovemo A2). Uzmemo a iz A1 i b iz A2. Ne postoji put između njih (razl komp povezanosti). Dodamo brid (a,b). Nismo dobili ciklus što je u kontardikciji s pretpostavkom.

#5: Autor/ica: desire,

Postano: 16:26 čet, 14. 2. 2008
—
Hvala. karma++

#6: Autor/ica: buzov5, Lokacija: zg

Postano: 16:47 čet, 14. 2. 2008
—
@ luuka: sve tm sa vjezbi imas na predavanjima, ona ograda je bila zadatak.
ak ti je kriza napisi izmedju kojih zadataka ti je rupa u biljeznici pa
ti skeniram

#7: Autor/ica: Luuka, Lokacija: Hakuna Matata

Postano: 16:48 čet, 14. 2. 2008
—
Nije kriza.Imam predavanja, samo mi te neke ograde fale, al sun ih je napisala...ak još koja fali, napiši tu. Tnx

#8: Autor/ica: betty,

Postano: 17:13 čet, 14. 2. 2008
—
jel mi može neko napisati samo prvu rečenicu iz dokaza prop.3.3.1. (planarnost), jer ja imam nešto nebulozno:?: Rolling Eyes

#9: Autor/ica: Luuka, Lokacija: Hakuna Matata

Postano: 17:15 čet, 14. 2. 2008
—

predavanja (napisa):

Odaberemo neki pravac p i označimo vrhove grafa točkama na pravcu p. ...

Eto.

#10: Autor/ica: buzov5, Lokacija: zg

Postano: 17:20 čet, 14. 2. 2008
—
ja ne pisem brojeve, al jedina prop. u dijelu o planarnosti
mi je da se svaki graf moze uloziti u R^3,
ak je to to dokaz kaze:
povucemo pravac u R^3, na pravcu oznacimo toliko
tocaka koliko graf ima vrhova. buduci da je pravac presjek
beskonacno mnogo ravnina za svaki brid odaberemo jednu od tih
ravnina i polukruznicom spojimo dvije tocke koje oznavaju vrhove
tog brida.

EDIT: preso me

#11: Autor/ica: amorphis, Lokacija: zg

Postano: 17:21 čet, 14. 2. 2008
—
koji je raspis izraza (-n povrh x)?

thnx

#12: Autor/ica: Luuka, Lokacija: Hakuna Matata

Postano: 17:25 čet, 14. 2. 2008
—

#13: Autor/ica: betty,

Postano: 17:26 čet, 14. 2. 2008
—
zahvaljujem.. Very Happy

#14: Autor/ica: ivanzub,

Postano: 19:36 čet, 14. 2. 2008
—
da ne otvaram novu temu..

kako dokazat da Primov algoritam generira razapinjuce stablo minimalne tezine?

i kako dokazat da su stabla bipartitni grafovi?

#15: Autor/ica: Luuka, Lokacija: Hakuna Matata

Postano: 19:41 čet, 14. 2. 2008
—
Stablo je bipartitan graf jer nema ciklusa. Zašto? Uzmimo jedan list stabla i označimo ga s A. Krećimo se po stablu i svaki idući vrh na kojeg naiđemo označimo naizmjenično s B i A. Pošto stablo nema ciklusa, neće se desit da postoji brid AA ili BB. Vjerojatno se to može i ljepše ispričat...

Recimo: Uzmimo vrh čiji je stupanj bar 2 i recimo nek je on korijen i označimo ga s A. Njegovu djecu označimo sa B. Djecu njegove djece ponovo s A itd. Dobili smo sve bridove AB (i BA) jer nema ciklusa.

#16: Autor/ica: ivanzub,

Postano: 19:47 čet, 14. 2. 2008
—
hvala puno..

jel zna netko ovaj s primovim algoritmom?

#17: Autor/ica: j.b.i.n.s.h.,

Postano: 20:13 čet, 14. 2. 2008
—
evo velikog problema:

multigraf bez izoliranih vrhova je eulerov akko je povezan i svaki vrh je parnog stupnja.

i sad, meni je u našoj skriptarnici netko toliko lijepo kopirao da ne vidim pročitati prvu rečenicu dokaza. ima možda neka dobra duša da se sažali nad mojom sudbinom? Molim, kumim i preklinjem!

može čak i Luuka Very Happy

#18: Autor/ica: lyra,

Postano: 20:15 čet, 14. 2. 2008
—
u mojim kopijama piše "Uvjet povezanosti je očito nužan." Laughing

#19: Autor/ica: j.b.i.n.s.h.,

Postano: 20:19 čet, 14. 2. 2008
—
onda mi još nešto nedostaje...
prvo što vidim je: ...stupanj mora biti paran. isto vrijedi i za početni vrh

#20: Autor/ica: lyra,

Postano: 20:23 čet, 14. 2. 2008
—
e onda ovak..
"Uvjet povezanosti je očito nužan. Promatramo graf s Eulerovom turom. Krećući se stazom, svaki put kada dođemo do nekog vrha pomoću nekog brida, moramo ga napustiti drugim bridom, dakle iskoristit ćemo dva brida iz tog vrha. Budući da posjetimo svaki brid tog vrha, stupanj mora biti paran."

evo, sad sam se čak uspjela natjerat da ovo pročitam. jupii Very Happy

Forum@DeGiorgi -> Diskretna matematika

output generated using printer-friendly topic mod. Vremenska zona: GMT + 01:00.

Idite na 1, 2 Sljedeće :| |: Stranica 1 / 2.