Matematické Fórum

Baron · 01. 02. 2011 21:43

Dokažte, že barevnost rovinných grafů bez trojúhelníku je 4, a to bez pomoci
věty o čtyřech barvách. Hint: dokažte, že každý takový graf je 3-degenerovaný.

nekdo nejaky napad?

FailED · 01. 02. 2011 22:47

↑ Baron:

Indukcí, pro rovinné grafy bez trojúhelníků platí $|E|\le2|V|-4$ , z toho aspoň jeden vrchol má stupeň nejvýš 3 - utrhnout, použít indukční předpoklad, obarvit, vrátit. :)

Baron · 02. 02. 2011 21:07

neni mi jasna jedna vec.. z ukolu vyplyva, ze graf bez trojuhelniku je 3-degenerovany. ale trojuhelnik neobsahuje a je 4-degenerovany. kde je chyba? cumim na to aspon hodinu jak blby a nechapu..

FailED · 03. 02. 2011 02:23

↑ Baron:

Ten tvůj graf je 2-degenerovaný.

Wikipedia napsal(a):
The degeneracy of a graph is the maximum, over all induced subgraphs of the graph, of the minimum degree of a vertex in the subgraph.

Baron · 04. 02. 2011 17:56 — Editoval Baron (04. 02. 2011 18:05)

takze cesky to je maximum minimalniho stupne vsech podgrafu?

tedy ze vsechny podgrafy grafu G maji minimalni stupen mensi nebo roven k, pricemz graf G obsahuje podgraf, jehoz minimalni stupen je k?

FailED · 04. 02. 2011 17:57

↑ Baron:

ano

Baron · 04. 02. 2011 18:12 — Editoval Baron (04. 02. 2011 19:37)

takze potrebuji dokazat, ze rovinny graf bez trojuhelniku obsahuje podgraf, jehoz minimalni stupen je maximalne 3. Jinak receno musis dokazat, ze graf s minimalnim stupnem 4 nebo 5 obsahuje trojuhelnik. Ale porad nemuzu prijit na to, jak :-/

btw. jedinna definice co jsem nasel byla tato:
Graf G je k-degenerovaný, pokud každý podgraf G obsahuje vrchol stupně nejvýše k.
takze bud je tahle definice spatna nebo jsem ji ja spatne pochopil.

FailED · 04. 02. 2011 20:18 — Editoval FailED (04. 02. 2011 20:20)

↑ Baron:

Graf G je k-degenerovaný, pokud každý podgraf G obsahuje vrchol stupně nejvýše k.

a

vsechny podgrafy grafu G maji minimalni stupen mensi nebo roven k, pricemz graf G obsahuje podgraf, jehoz minimalni stupen je k

znamená totéž.

takze potrebuji dokazat, ze rovinny graf bez trojuhelniku obsahuje podgraf, jehoz minimalni stupen je maximalne 3

Ano.

K tomu se hodí, když znáš ↑ vztah: pro rovinné grafy $|E|\le2|V|-4$ , plyne to z Eulerovy formule, když dosadíš za počet stěn odhad $f\le\frac{e}{2}$ . Ten odhad si zkus rozmyslet, počítej počet hran přes stěny.

Teď kdyby měly všechny vrcholy stupeň aspoň 4, bylo by $2|E|=\sum_{v\in V}deg(v)\ge 4|V|$ tedy $|E|\ge 2|V|$ a to je spor, v každém rovinném grafu bez trojúhelníků, tedy ve všech indukovaných podgrafech našeho grafu, existuje vrchol stupně nejvýše 3, a náš graf je tedy 3-degenerovaný.

Baron · 04. 02. 2011 20:20

dukaz pozorovanim, ze rovinne nakresleni platonovskeho osmistenu (4-regularni) a dvacetistenu (5-regularni) trojuhelnik obsahuje asi nebude stacit co?

FailED · 04. 02. 2011 20:24

↑ Baron:

To opravdu ne, takové pozorování o rovinných grafech bez trojúhelníků říká jen že tam tyto dva grafy nepatří :)

Baron · 04. 02. 2011 20:42

uz to konecne chapu, mockrat dekuji, nejspis jsi mi zachranil zapocet :)

Matematické Fórum

#1 01. 02. 2011 21:43

barevnost rovinných grafů

#2 01. 02. 2011 22:47

Re: barevnost rovinných grafů

#3 02. 02. 2011 21:07

Re: barevnost rovinných grafů

#4 03. 02. 2011 02:23

Re: barevnost rovinných grafů

Wikipedia napsal(a):

#5 04. 02. 2011 17:56 — Editoval Baron (04. 02. 2011 18:05)

Re: barevnost rovinných grafů

#6 04. 02. 2011 17:57

Re: barevnost rovinných grafů

#7 04. 02. 2011 18:12 — Editoval Baron (04. 02. 2011 19:37)

Re: barevnost rovinných grafů

#8 04. 02. 2011 20:18 — Editoval FailED (04. 02. 2011 20:20)

Re: barevnost rovinných grafů

#9 04. 02. 2011 20:20

Re: barevnost rovinných grafů

#10 04. 02. 2011 20:24

Re: barevnost rovinných grafů

#11 04. 02. 2011 20:42

Re: barevnost rovinných grafů

Zápatí