Matematické Fórum
Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.
Nástěnka
❗22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
❗04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
❗23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.
Nejste přihlášen(a). Přihlásit
#4 08. 03. 2010 22:11
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Počet neisomorfních grafů
Má jich být jedenáct, to je jediné, co jsem chtěl odkazem říci.
Burnsideovo lemma říká, že počet různých objektů je průměrný počet pevných bodů všech možných symetrií. V našem případě symetrie = permutace vrcholů.
Identita má 2^6 pevných bodů.
Každá z 8 permutací tvořených trojprvkovým cyklem má 4 pevné body.
Každá z 6 permutací tvořených čtyřprvkovým cyklem má 4 pevné body.
Každá z 6 permutací tvořených dvojprvkovým cyklem má 16 pevných bodů.
Každá z 3 permutací tvořených dvěma dvouprvkovými cykly má 16 pevných bodů.
Celkem máme (64+8*4+6*4+6*16+3*16)/24=11 možných grafů.
Na představu bez kreslení je snazší vyhodnotit, co je pevný bod, než jestli jsou dva grafy izomorfní.
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#5 08. 03. 2010 22:25
Re: Počet neisomorfních grafů
↑ Kondr:
Omlouvám se, ale to je na mě příliš složitý. Teorii grafů mám asi měsíc a zatím jsem k permutacím a pevným bodům nedošli.Vím,že na 4 vrcholech je 64 možných grafů. Ve škole jsme dělali jen příklad (graficky) pro 3 vrcholech :(
Offline
#6 08. 03. 2010 22:26
Re: Počet neisomorfních grafů
Permutace a pevné body nejsou z teorie grafů, to se spíš zařazuje do kombinatoriky či lineární algebry.
Offline
#7 08. 03. 2010 22:30
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Počet neisomorfních grafů
↑ kajbl: Burnsideovo lemma je hodně "advanced", krom semináře z matiky na našem matematickém gymplu jsem ho neslyšel.
BRKOS - matematický korespondenční seminář pro střední školy
Offline