22. 1. 2009, O. Pangrác

Ú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í).
Jurassic
Matfyz(ák|ačka) level I
Příspěvky: 1
Registrován: 17. 10. 2008 14:02
Typ studia: Informatika Bc.

22. 1. 2009, O. Pangrác

Příspěvek od Jurassic »

1. Definujte bipartitní graf. Rozhodněte, zda je kružnice délky n bipartitním grafem.

2. Formulujte a dokažte větu o barevnosti rovinných grafů. (Věta o 5 barvách)

3. Kolik existuje uspořádaných dvojic (A,B) takových, že A i B jsou podmnožiny {1,2,...,n} a |A průnik B| = 1?
K4

Re: 22. 1. 2009, O. Pangrác

Příspěvek od K4 »

1) Kdy jsou dva jevy nezávislé (definice). Kdy jsou tři jevy nezávislé. Vymyslet příklad, kdy jsou tři jevy závislé, ale po dvojicích nezávislé.
2) nejlepší dolní odhad počtu navzájem neizomorfních grafů na n vrcholech + důkaz
3) zjistit počet koster grafu vzniklého z K4 dělením všech hran
Uživatelský avatar
DZuXO
Matfyz(ák|ačka) level I
Příspěvky: 11
Registrován: 20. 1. 2009 11:28
Typ studia: Informatika Bc.

Re: 22. 1. 2009, O. Pangrác

Příspěvek od DZuXO »

1 - Definuj realnu nahodnu velicinu, definuj indikator javu
2 - Sformuluj vetu o barevnosti rovinnych grafov a dokaz
3 - Kolko najviac vrcholov s roznym stupnom moze byt na grafe s poctom vrcholov n.

(bolo to n-1, a vynimka ked je graf jediny vrchol, vtedy je to n)
(inac ako v pohode skuska :-) Pangrac je fajn, v 3. ulohe som spravil chybu takze mi dal
nahradny priklad - (co je to ekvivalencia, co je to rozkladova trieda, kolko roznych ekvivalencii je na stvroprvkovej mnozine
- vysledok sa vypocita pomocou kombinacnych cisel, o tom som ale nemal sajn, takze nakoniec za 2)
UIRA — UIRA Isn't a Recursive Acronym.
cman
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 3. 11. 2008 10:36
Typ studia: Informatika Bc.

Re: 22. 1. 2009, O. Pangrác

Příspěvek od cman »

Jsem nějak mimo, jak se tohle řeší, poradí někdo?

Kolik existuje uspořádaných dvojic (A,B) takových, že A i B jsou podmnožiny {1,2,...,n} a |A průnik B| = 1?
Návštěvník

Re: 22. 1. 2009, O. Pangrác

Příspěvek od Návštěvník »

|A prienik B|=1 =>existuje n roznych prienikov (1,2,3...)
Ak uz mam zvolene cislo ktore bude prienikom ostava mi n-1 cisel x a pre kazde z nich plati:
(x patri A) xor (x patri B) xor (x nepatri ani A ani B) teda pre kazde z tych n-1 existuju 3 moznosti ako sa chovat, teda vzorec je
n.3^(n-1)
cman
Matfyz(ák|ačka) level I
Příspěvky: 7
Registrován: 3. 11. 2008 10:36
Typ studia: Informatika Bc.

Re: 22. 1. 2009, O. Pangrác

Příspěvek od cman »

Díky, takhle to už vypadá jednoduše. Musím prostě víc cvičit...
Odpovědět

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