Matematické Fórum

Billy · 08. 06. 2011 21:55

Ahoj,

potreboval by som pomoct s nasledujucim dokazom:

Co nechapem:
- preco prienik A,B implikuje existenciu hrany $\{u_i,u_{i-1}\}$ a co ma spolocne s existenciou Hamiltovonskej kruznice?
- a preco plati $A\subseteq \{2,3,...,n-1\}$ a pre mna este nerozumnejsia inkluzia pre B ?

Chvatalov uzaver je mozne najst napr tu.

Dik za akukolvek radu, uz na tom sedim velmi dlho.

Olin · 08. 06. 2011 23:19 — Editoval Olin (08. 06. 2011 23:20)

Ono to možná není úplně nejlépe formulované, chce se říct to, že neprázdný průnik $A \cap B$ implikuje existenci hrany $\{u_{i-1}, u_i\}$ takové, že v $G$ jsou hrany $\{u_1, u_i\}$ a $\{u_n, u_{i-1}\}$ , tedy jako na obrázku.

$A \subseteq \{2, \dots, n-1\}$ , jelikož vrchol $u = u_1$ může být spojen hranou pouze s vrcholy $u_2, \dots, u_{n-1}$ , s $u_n = v$ už dle předpokladu není spojen.

Matematické Fórum

#1 08. 06. 2011 21:55

Chvatalova veta dukaz

#2 08. 06. 2011 23:19 — Editoval Olin (08. 06. 2011 23:20)

Re: Chvatalova veta dukaz

Zápatí