Matematické Fórum

geovektor1

Ahojte, narazil som na tvrdenie z oblasti teorie grafov, ktore akosi neviem dokazat. Pomoze mi niekto? Znenie:
Ak $G$ je nesuvisly graf, potom komplementarny graf $\overline{G}$ je suvisly (da sa dokazat viac: $d\overline{G}=2$ ) Tomu v zatvorke nerozumiem ale cele znenie je taketo v knihe takze som to tu hodil. Ak vas nieco napada tak budem rad za pomoc.

Brano · 07. 03. 2015 12:54 — Editoval Brano (07. 03. 2015 12:59)

Cize ak je $G$ nesuvisly, tak ma aspon 2 komponenty suvislosti - nech teda jeho komponenty su $K_1,...,K_n$
graf $\overline G$ ma tie iste vrcholy, len ine hrany. Ak $u$ je vrchol z $K_i$ a $v$ je vrchol z $K_j$ pricom $i\not=j$ tak su v grafe $\overline G$ priamo spojene hranou $uv$ , lebo v grafe $G$ neboli. A ak mas $u,v$ vrcholy z $K_i$ tak si vyber lubovolny vrchol $w$ z nejakej $K_j$ , $i\not=j$ a potom mas hrany $uw$ a $wv$ . Cize $\overline G$ je suvisly.

Asi $d$ bude znacit priemer t.j. maximalnu vzdialenost dvoch vrcholov v $\overline G$ a to sme prave nahliadli, ze je najviac $2$ . (este to moze byt aj $=1$ to by bolo vtedy ked je $\overline G$ uplny, cize $G$ neobsahuje ziadne hrany)

geovektor1 · 07. 03. 2015 15:31

a to je dokaz?

jarrro · 07. 03. 2015 15:33

áno je prečo by nemal byť?

geovektor1 · 07. 03. 2015 15:33

nehovorim ze by nemal byt len mne to akosi nie je jasne tak prepacte mozno som sa zle vyjadril

Brano · 07. 03. 2015 16:22

skor to co jarro chcel povedat bolo, ze "povedz co nie je jasne"

jarrro · 07. 03. 2015 16:28 — Editoval jarrro (07. 03. 2015 16:36)

čo nie je jasné ? ak je nesúvislý tak má aspoň dva komponenty a v doplnku grafu sú 2 vrcholy priamo spojené ak sú z iných komponentov a spojené cez nejaký tretí vrchol z iného komponentu ak sú z jedného komponentu
Brano pôvodne som chcel naozaj odpovedať, že je to dôkaz teda ,že by (dúfam) mohol byť povedaný alebo napísaný na skúške tak ako si ho napísal ty

Matematické Fórum

#1 06. 03. 2015 23:06 — Editoval geovektor1 (06. 03. 2015 23:07)

Dokaz teoria grafov

#2 07. 03. 2015 12:54 — Editoval Brano (07. 03. 2015 12:59)

Re: Dokaz teoria grafov

#3 07. 03. 2015 15:31

Re: Dokaz teoria grafov

#4 07. 03. 2015 15:33

Re: Dokaz teoria grafov

#5 07. 03. 2015 15:33

Re: Dokaz teoria grafov

#6 07. 03. 2015 16:22

Re: Dokaz teoria grafov

#7 07. 03. 2015 16:28 — Editoval jarrro (07. 03. 2015 16:36)

Re: Dokaz teoria grafov

Zápatí