Matematické Fórum

Olin · 09. 02. 2011 18:46 — Editoval Olin (09. 02. 2011 18:46)

Zdravím kolegy. Pročítám si knížku Modern Graph Theory od B. Bollobáse a trochu jsem se zasekl u důkazu Vizingovy věty. Konkrétně jde o podtržené tvrzení. Jak může tvrdit, že se změna netýká hran s barvami $s$ a $t_h$ , když hrana $xy_j$ původně měla barvu $t_h$ , ale byla přebarvena na $t_j$ , naopak hrana $xy_{j-1}$ barvu $t_h$ dostala?

Možná jsem jen nepochopil, co přesně tím chce básník říct. Děkuji za jakoukoliv pomoc, vím, že je ten důkaz poměrně dlouhý.

FailED · 09. 02. 2011 19:44 — Editoval FailED (09. 02. 2011 19:57)

↑ Olin:

Ahoj,
podle mě pokračuje s přebarvováním se kterým začal v (b), mluví o změně v tomhle pokračování.

( $H(s,t_h)$ definoval až po přebarvení hran $xy_1,\,\ldots \,, xy_j$ .)

check_drummer · 09. 02. 2011 20:09

Podle spojení "continue the recoloring" bych to chápal tak, že budu přebarvovat sice hrany i<h jak je psáno, ovšem už ne ty, které jsem předchozím kroku přebarvil (i<j). Rovněž si myslím, že graf H(s,th) je definován až na grafu, který vznikne po obarvení hran i<j.

Pavel Brožek · 09. 02. 2011 20:23

Když už jsem věnoval tolik času porozumění důkazu, tak alespoň potvrdím to, co píší kolegové. Podgraf H sestrojíme teprve po přebarvení hran $xy_i$ s $i\in\{1,\ldots,j-1\}$ . Slova „This change“ se pak vztahují k obarvení hran $xy_i$ s $i\in\{j,\ldots,h-1\}$

Olin · 09. 02. 2011 20:26 — Editoval Olin (09. 02. 2011 20:27)

Hmm, už jsem asi přišel na to, v čem je ten vtip - $xy_j$ byl přebarven na "žádnou" barvu, teprv pak byl sestrojen $H(s, t_h)$ . Díky všem za podněty.

No není to zajímavá věta?

FailED · 09. 02. 2011 20:48

↑ Olin:

To určitě je :)

Jak bys hodnotil tu knihu?

Olin · 09. 02. 2011 21:43

Kniha se mi docela líbí, určitě mohu doporučit komukoliv, koho zaujala diskrétní matematika.

FailED · 09. 02. 2011 22:19

↑ Olin:

Fajn, díky, podívám se na to.

Matematické Fórum

#1 09. 02. 2011 18:46 — Editoval Olin (09. 02. 2011 18:46)

Důkaz Vizingovy věty

#2 09. 02. 2011 19:44 — Editoval FailED (09. 02. 2011 19:57)

Re: Důkaz Vizingovy věty

#3 09. 02. 2011 20:09

Re: Důkaz Vizingovy věty

#4 09. 02. 2011 20:23

Re: Důkaz Vizingovy věty

#5 09. 02. 2011 20:26 — Editoval Olin (09. 02. 2011 20:27)

Re: Důkaz Vizingovy věty

#6 09. 02. 2011 20:48

Re: Důkaz Vizingovy věty

#7 09. 02. 2011 21:43

Re: Důkaz Vizingovy věty

#8 09. 02. 2011 22:19

Re: Důkaz Vizingovy věty

Zápatí