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
#6 09. 06. 2010 17:00
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Počet izomorfismů
↑ kajbl: I kdeže, musí přece platit, že vrchol stupně 2 se zobrazí na vrchol stupně 2, což nám pro 2 dává jedinou možnost, kam se může zobrazit, izomorfizmy jsou v tomto případě pouze 2. Obecně je počet izomorfizmů mezi dvěma izomorfními grafy roven počtu automorfizmů daného grafu (triviálně), jde tedy o číslo, které dělí n! ale jeho hodnota závisí na tvaru grafu.
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#8 09. 06. 2010 17:48
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Počet izomorfismů
↑ kajbl: Tak třeba síť krychle j 3-regulární na 8 vrcholech a automorfizmů má 48, což je podstatně méně než 8!. Pro 1-regulární graf na 2t vrcholech je automorfizmů 
. Pro 2-regulární graf je zřejmé, že už vzorec nevyrobíme. Za předpokladu spojitosti by to byl dvojnásobek počtu vrcholů.
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#13 09. 06. 2010 18:19
Re: Počet izomorfismů
↑ Stýv:
Styve ja vim, co Kondr napsal. Ale porad mi to neni proste jasne, a jde mi proste o to, jak zjistim pocet automorfismu u nejakyho grafu.
Ja se omlouvam, ze mi to fakt nedochazi. Ja si automorfismus proste vysvetluju jako " pocet ruznych prekresleni urciteho grafu".
Offline
#14 09. 06. 2010 18:29
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Počet izomorfismů
↑ kajbl: Neznám obecný algoritmus na určování počtu automorfizmů a dost pochybuju, že nějaký existuje. Pro konkrétní typy grafů ale existují lepší cesty, než pro všech n! permutací vrcholů ověřit, zda jde o izomorfizmus (jak jsem uvedl výše pro 2-regulární a 1-regulární grafy).
BRKOS - matematický korespondenční seminář pro střední školy
Offline
#19 10. 06. 2010 02:28
- Kondr
- Veterán
- Místo: Linz, Österreich
- Příspěvky: 4247
- Škola: FI MU 2013
- Pozice: Vývojář, JKU
- Reputace: 38
Re: Počet izomorfismů
↑ kajbl: C_n jich má 2n (n otočení, pro každé z nich dvě překlopení), K_a,b jich má a!b! pro a různé od b (prohazujeme libovolně v rámci partit) a 2(a!)^2 pro a=b (prohazujeme nejen v rámci partit, ale můžeme prohodit celé partity).
BRKOS - matematický korespondenční seminář pro střední školy
Offline