Ukol z DMA - na zapocet

Úvod do kombinatoriky a teorie grafů. Důraz je kladen na aktivní zvládnuti základních pojmů a metod (relace, zobrazení, graf; přesná formulace matematických tvrzení, řešení příkladů a dokazovaní jednoduchých tvrzení).
marion
Matfyz(ák|ačka) level II
Příspěvky: 69
Registrován: 4. 10. 2008 11:05
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Ukol z DMA - na zapocet

Příspěvek od marion »

Zdravim, potrebujeme pomoct se zapoctovym ukolem. Budem velice vdecni za jakekoli napady:
1. Dokazte, ze uplny bipartitni graf K(m,n) je rovinny prave tehdy, kdyz min{n,m}<=2

2. Dokazte, ze barevnost rovinnych grafu bez trojuhelniku je 4, a to bez pomoci vety o ctyrech barvach. Hint: dokazte, ze kazdy takovy graf je 3-degenerovany

3. Necht G je graf. Dokazte nasledujici vztah:
X(G)*a(G)>=|V(G)|,
kde X(G) znaci barevnost grafu G a a(G) velikost nejvetsi nezavisle mnoziny v G.

.....
Najde se nejaka dobra duse???
Osiris
Supermatfyz(ák|ačka)
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: Ukol z DMA - na zapocet

Příspěvek od Osiris »

marion píše:Zdravim, potrebujeme pomoct se zapoctovym ukolem. Budem velice vdecni za jakekoli napady:
1. Dokazte, ze uplny bipartitni graf K(m,n) je rovinny prave tehdy, kdyz min{n,m}<=2

2. Dokazte, ze barevnost rovinnych grafu bez trojuhelniku je 4, a to bez pomoci vety o ctyrech barvach. Hint: dokazte, ze kazdy takovy graf je 3-degenerovany

3. Necht G je graf. Dokazte nasledujici vztah:
X(G)*a(G)>=|V(G)|,
kde X(G) znaci barevnost grafu G a a(G) velikost nejvetsi nezavisle mnoziny v G.

.....
Najde se nejaka dobra duse???
1) Myslím, že by stačilo ukázat, rozborem případů pro velikost partity rovnající se 0,1,2 - snadné a pak by stačilo jen říct, že když je minimální stupeň 3, pak už nutně obsahuje K(3,3), který není rovinný
3) Největší nezávislou množinu můžeš obarvit jednou barvou, obarvení je korektní. Dále by to šlo udělat třeba tak, že postupně odebíráš zbylé největší nezávislé množiny (poté co sebereš ty předchozí) a ty barvíš další a další barvou. Asi by se to dalo nějak udělat indukcí podle počtu nezávislých množin, nebo tak něco...
Osiris
Uživatelský avatar
lukax
Matfyz(ák|ačka) level I
Příspěvky: 45
Registrován: 12. 1. 2009 11:32
Typ studia: Informatika Bc.

Re: Ukol z DMA - na zapocet

Příspěvek od lukax »

marion píše:2. Dokazte, ze barevnost rovinnych grafu bez trojuhelniku je 4, a to bez pomoci vety o ctyrech barvach. Hint: dokazte, ze kazdy takovy graf je 3-degenerovany
Máme |E|≤2|V|-4, takže |E|/2+2≤|V|. Předpokládejme pro spor, že stupeň každého vrcholu grafu je větší než tři (tj. graf není 3-degenerovaný). Pak musí platit, že |V|≤2·|E|/4 (dvakrát počet konců hran je počet hran). No ale teď nám ty dva vzorečky dohromady říkají, že

|E|/2+2≤|V|≤2·|E|/4
|E|/2+2≤|E|/2

což je spor. Platí to určitě i pro každý podgraf, protože ani ten nebude obsahovat trojúhelník. Proto je takový graf 3-degenerovaný a proto mu můžeme vrcholy barvit „hladově“.
cman
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 3. 11. 2008 10:36
Typ studia: Informatika Bc.

Re: Ukol z DMA - na zapocet

Příspěvek od cman »

3. Necht G je graf. Dokazte nasledujici vztah:
X(G)*a(G)>=|V(G)|,
kde X(G) znaci barevnost grafu G a a(G) velikost nejvetsi nezavisle mnoziny v G.

.....
Najde se nejaka dobra duse???
Najde 8)

Tvrzení lze dokázat přímo, neboť vlastní obarvení vrcholů G minimálním počtem barev 
je zobrazení takové, že V→ {1,2,...,χ(G)}. Pro každou barvu i označím Vi množinu 
vrcholů, které dostaly barvu i.  Je zřejmé, že  V 1∪V 2 ...∪Vχ (G je  rozklad množiny V. 
Mezi vrcholy obarvené barvou i není žádná hrana, takže množina Vi je nezávislá 
množina  a její mohutnost je nejvýše rovná maximální velikosti nezávislé množiny G
( ∣V i∣≤α (G ).  Obarvíme­li tedy graf G pomocí χ(G) barev, získáme χ(G) 
nezávislých množin, z nichž každá obsahuje nejvýše α(G) vrcholů. Protože α(G) značí 
největší nezávislou množinu, zjevně platí dokazovaná nerovnost.
Uživatelský avatar
op
Matfyz(ák|ačka) level I
Příspěvky: 3
Registrován: 15. 5. 2006 14:48
Typ studia: Nestuduji ale učím na MFF

Re: Ukol z DMA - na zapocet

Příspěvek od op »

lukax píše:... proto mu můžeme vrcholy barvit „hladově“.
FUJ, rict o obarvovani "hladove" by melo byt trestne (pokud nejde o on-line barveni)!
Uživatelský avatar
hippies
Admin(ka) level I
Příspěvky: 990
Registrován: 29. 9. 2004 12:46
Typ studia: Informatika Mgr.
Bydliště: Mladá Boleslav
Kontaktovat uživatele:

Re: Ukol z DMA - na zapocet

Příspěvek od hippies »

Muzu se zeptat proc by to melo byt trestne? Nejak v tom nevidim zadnou zasadni chybu.
Chjo, dovede te si představit svět, kde by byla každá harmonická diferenciální forma (jistého typu) nesingulární projektivní algebraické variety racionální kombinací kohomologických tříd algebraických cyklů..
Glandrian
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 9. 11. 2010 12:55
Typ studia: Informatika Bc.

Re: Ukol z DMA - na zapocet

Příspěvek od Glandrian »

Dokažte, že v každém grafu G s δ(G) ≥ 2 existuje kružnice délky alespoň δ(g) + 1. (Symbol δ(g) značí minimální stupeň grafu G.)

Poradil by mi prosím někdo jak na to?
Osiris
Supermatfyz(ák|ačka)
Příspěvky: 403
Registrován: 11. 11. 2006 14:10
Typ studia: Informatika Mgr.
Bydliště: Praha
Kontaktovat uživatele:

Re: Ukol z DMA - na zapocet

Příspěvek od Osiris »

Glandrian píše:Dokažte, že v každém grafu G s δ(G) ≥ 2 existuje kružnice délky alespoň δ(g) + 1. (Symbol δ(g) značí minimální stupeň grafu G.)

Poradil by mi prosím někdo jak na to?
Uvaž nejdelší cestu v tom grafu. Z koncového vrcholu té cesty musí vést hrany nazpět do té cesty, jinak by ta cesta nebyla nejdelší. No a každá taková hrana tvoří kružnici.
Osiris
Odpovědět

Zpět na „DMI002 Diskrétní matematika“