Matematické Fórum

SweetNelli · 01. 12. 2009 13:53

Dokažte, že doplněk nesouvislého grafu je nutně souvislý.

jak postupovat?

Wotton · 01. 12. 2009 16:08

Jestliže je graf nesovislý, tak platí $\forall u\in V(G)\forall v\in V(G)((u,v)\in E(G)\rightarrow\exists w\in V(G)((u,w)\not\in E(G)\wedge(v,w)\not\in E(G)))$ pro doplněk tedy platí $\forall u\in V(G)\forall v\in V(G)((u,v)\not\in E(G)\rightarrow\exists w\in V(G)((u,w)\in E(G)\wedge(v,w)\in E(G)))$ . To znamená, že pro každé dva vrcholy v doplňku grafu které nejsou spojeny hranou existuje cesta délky 2 z jednoho do druhého. Takže graf je souvislý.

petrkovar · 01. 12. 2009 21:57

↑ Wotton:To řeší úlohu pro graf na 3 a více vrcholech, protože jen v takovém můžeme využít existenci třetího vrcholu w. Pro graf na 2 vrcholech je řešení ještě jednodušší.

Wotton · 01. 12. 2009 22:09

↑ petrkovar:
Mnou navrhované řešení funguje i pro graf se dvěma vrcholy.

petrkovar · 01. 12. 2009 22:23

↑ Wotton:To je pravda. A pro graf s jedním vrcholem jsou obě implikace také pravdivé.

Wotton · 01. 12. 2009 23:05

↑ petrkovar:
Pro graf s jedním vrcholem není splněna druhá imlikace, ale graf s jedním vrcholem nesplňuje zadání. Je pravda že bych tam měl asi přidat podmínku u/=v, ale to důkaz příliš neovlivní, takže to necham být.

A asi bych měl řict "To znamená, že pro každé dva RŮZNÉ vrcholy v doplňku grafu které nejsou spojeny..."

petrkovar · 02. 12. 2009 16:31

↑ Wotton:Jen pro úplnost: implikace 0=>1 je pravdivá. A protože takové dva nesousední vrcholy u,v v grafu G nenajdeme (máme nepravdivý předpoklad implikace), tak je implikace pravdivá.

Wotton · 02. 12. 2009 16:37

↑ petrkovar:
Najdem, ... když vezmem dvakrát ten samý vrchol, tak z něj do něj nevede hrana. Proto by tam měla být ta podmínka že u/=v.

SweetNelli · 02. 12. 2009 19:26

↑ Wotton:

copak to je za podmínku u/ = v?:)

Wotton · 03. 12. 2009 11:37

↑ SweetNelli:

$u\not =v$

Matematické Fórum

#1 01. 12. 2009 13:53

doplněk grafu - souvislost

#2 01. 12. 2009 16:08

Re: doplněk grafu - souvislost

#3 01. 12. 2009 21:57

Re: doplněk grafu - souvislost

#4 01. 12. 2009 22:09

Re: doplněk grafu - souvislost

#5 01. 12. 2009 22:23

Re: doplněk grafu - souvislost

#6 01. 12. 2009 23:05

Re: doplněk grafu - souvislost

#7 02. 12. 2009 16:31

Re: doplněk grafu - souvislost

#8 02. 12. 2009 16:37

Re: doplněk grafu - souvislost

#9 02. 12. 2009 19:26

Re: doplněk grafu - souvislost

#10 03. 12. 2009 11:37

Re: doplněk grafu - souvislost

Zápatí