Matematické Fórum

geovektor1 · 06. 03. 2015 23:11

Ahoj, toto je treti dokaz ale tento mi je najmenej zrozumitelny. Dokazte: Ak G je suvisly graf, tak d(G)\le p-1 kde p je pocet vrcholov. Ako na to?

Brano · 07. 03. 2015 13:05

ak spojis dva vrcholy najkratsim sledom (ci ako sa tomu nadava) v tom grafe (da sa lebo je suvisly)
tak sa ti tam nemozu opakovat vrcholy teda mas: zaciatocny vrchol, hrana, vrchol, hrana, ..., hrana, koncovy vrchol. Mas tam maximalne p vrcholov, tak kolko je tam hran?

geovektor1

Ak G je suvisly graf, tak $d(G)\le p-1$ kde p je pocet vrcholov. Takto to ma byt. Hran neviem kolko tam je ale v tej vete sa jedna o vrcholy nie o hrany.

byk7 · 07. 03. 2015 15:51

↑ geovektor1: Rozmysli si větu: Graf $G$ o $p$ vrcholech je souvislý, pokud má alespoň $p-1$ hran.

geovektor1

preco? je ta veta zla? v knihe je takto sformulovana: http://www.fastimages.eu/images/vetadokaza.png

Brano · 07. 03. 2015 16:29 — Editoval Brano (07. 03. 2015 16:34)

nie, nie je ta veta zla. ↑ byk7: ti dal hint v zmysle, ze ked si dokazaes vetu co povedal on, tak by si si mal zvladnut dokazat aj tvoju vetu.

BTW v tej vete na ktoru sa pytas sa ocividne jedna aj o vrcholy aj o hrany: p je pocet vrcholov a pojem d(cosi) ako si ho uz v inom vlakne definoval v sebe zahrna pocet hran, lebo "priemer" je nejaka "excentricita"; a "excentricita" je dlzka nejakej "cesty" a "dlzka cesty" je pocet hran v tej ceste

a zistit odpoved na moju otazku by nemal byt taky problem
skusme si rozpisat nejake priklady

"vrchol hrana vrchol" kolko krat sa tu nachadza slovo "vrchol" a kolko krat slovo "hrana"?
"vrchol hrana vrchol hrana vrchol" rovnaka otazka ako predtym.
"vrchol hrana vrchol hrana vrchol hrana vrchol" rovnaka otazka ako predtym.
"vrchol hrana vrchol hrana vrchol hrana vrchol hrana vrchol" rovnaka otazka ako predtym.
a uz by si mal zacat vidiet system

geovektor1 · 07. 03. 2015 19:39

no v prvej otazke su 2 vrcholy a jedna hrana. v druhom pripade je to tri vrcholy a dve hrany, v tretom je to 4 vrcholy a tri hrany a v stvrtom je to 5 vrcholov a 4 hrany, ako nam to pomoze?

Brano · 07. 03. 2015 23:47

↑ geovektor1:
no to co si si mohol vsimnut je, ze ak mas v nejakej ceste k vrcholov tak tam mas k-1 hran a teda ak je tam najviac p vrcholov, tak je tam najviac p-1 hran - t.j. dlzka tej cesty je najviac p-1

misaH · 08. 03. 2015 06:50

↑ geovektor1:

Ahoj.

Ty čo študuješ, na akú chodíš školu?

geovektor1 · 09. 03. 2015 19:44

Studujem matematiku na Katolickej univerzite.

byk7 · 09. 03. 2015 21:24

↑ geovektor1:

Mohl bys si prosím projít svá starší témata a pooznačovat za vyřešené nebo tam položit doplňující otázky? Děkuji.

geovektor1 · 10. 03. 2015 00:38

ano hned zajtra si to dam do poriadku dakujem za upozornenie.

geovektor1 · 10. 03. 2015 16:28

Brano napsal(a):
↑ geovektor1:
no to co si si mohol vsimnut je, ze ak mas v nejakej ceste k vrcholov tak tam mas k-1 hran a teda ak je tam najviac p vrcholov, tak je tam najviac p-1 hran - t.j. dlzka tej cesty je najviac p-1

Toto by mal byt uz dokaz nie? Pretoze je ukazane ze dlzka cesty je najviac p-1 co tvrdenie, ktore chceme dokazat.

Matematické Fórum

#1 06. 03. 2015 23:11

Dokaz teoria grafov - treti

#2 07. 03. 2015 13:05

Re: Dokaz teoria grafov - treti

#3 07. 03. 2015 15:23 — Editoval geovektor1 (07. 03. 2015 15:24)

Re: Dokaz teoria grafov - treti

#4 07. 03. 2015 15:51

Re: Dokaz teoria grafov - treti

#5 07. 03. 2015 16:03 — Editoval geovektor1 (07. 03. 2015 16:06)

Re: Dokaz teoria grafov - treti

#6 07. 03. 2015 16:29 — Editoval Brano (07. 03. 2015 16:34)

Re: Dokaz teoria grafov - treti

#7 07. 03. 2015 19:39

Re: Dokaz teoria grafov - treti

#8 07. 03. 2015 23:47

Re: Dokaz teoria grafov - treti

#9 08. 03. 2015 06:50

Re: Dokaz teoria grafov - treti

#10 09. 03. 2015 19:44

Re: Dokaz teoria grafov - treti

#11 09. 03. 2015 21:24

Re: Dokaz teoria grafov - treti

#12 10. 03. 2015 00:38

Re: Dokaz teoria grafov - treti

#13 10. 03. 2015 16:28

Re: Dokaz teoria grafov - treti

Brano napsal(a):

Zápatí