#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