Ukol z DMA - na zapocet
-
- Matfyz(ák|ačka) level II
- Příspěvky: 69
- Registrován: 4. 10. 2008 11:05
- Typ studia: Informatika Mgr.
- Login do SIS: 36138549
- Kontaktovat uživatele:
Ukol z DMA - na zapocet
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. 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???
-
- 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
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ý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???
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
- lukax
- Matfyz(ák|ačka) level I
- Příspěvky: 45
- Registrován: 12. 1. 2009 11:32
- Typ studia: Informatika Bc.
- Login do SIS: 62666361
Re: Ukol z DMA - na zapocet
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í, žemarion 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
|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ě“.
-
- 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
Najde3. 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???
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ímeli 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.
- 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
FUJ, rict o obarvovani "hladove" by melo byt trestne (pokud nejde o on-line barveni)!lukax píše:... proto mu můžeme vrcholy barvit „hladově“.
- hippies
- Admin(ka) level I
- Příspěvky: 990
- Registrován: 29. 9. 2004 12:46
- Typ studia: Informatika Mgr.
- Login do SIS: procj4am
- Bydliště: Mladá Boleslav
- Kontaktovat uživatele:
Re: Ukol z DMA - na zapocet
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ů..
-
- 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
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?
Poradil by mi prosím někdo jak na to?
-
- 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
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.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?
Osiris