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?
22. 1. 2009, O. Pangrác
Re: 22. 1. 2009, O. Pangrác
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
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
- DZuXO
- Matfyz(ák|ačka) level I
- Příspěvky: 11
- Registrován: 20. 1. 2009 11:28
- Typ studia: Informatika Bc.
- Login do SIS: 55020672
Re: 22. 1. 2009, O. Pangrác
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)
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.
-
- 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
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?
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?
Re: 22. 1. 2009, O. Pangrác
|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)
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)
-
- 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
Díky, takhle to už vypadá jednoduše. Musím prostě víc cvičit...