Matematické Fórum

1-2-3
a-b-c

kolik najdeš izomorfismů?

tak hledej;)

↑ 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.

↑ 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ů.

Kondr napsal(a):

Obecně je počet izomorfizmů mezi dvěma izomorfními grafy roven počtu automorfizmů daného grafu

Stýv napsal(a):

Kondr napsal(a):

Obecně je počet izomorfizmů mezi dvěma izomorfními grafy roven počtu automorfizmů daného grafu

↑ 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).

uz jsem to tak nejak pochopil , jen se pro jistotu zeptam :

C3 ma automorfismu 6 , C4 nasel jsem 4 , K3,3  36?
Ja vim, ze porad otravuju s tim n!, ale tak mi vychazi pocet automorfismu u uplnych grafu

↑ Stýv:
a ten počet automorfismů je dobře ?

↑ Kondr:

takže c3 -6 , c4 -8 , K3,3 72 ? Díky moc a omlouvám se za svoji natvrdlost

↑ Kondr:

Ano, moc děkuji oběma, moc jste mi pomohli a ještě jednou se omlouvám.