Permutationsgrupp och bana (Matematik/Universitet)

$S_4$ är permutationsgruppen på 4 element och utgör mängden av alla bijektioner mellan $\{1,2,3,4\} \to \{1,2,3,4\}$ vilka kallas för permutationer.

Aut står för automorfi från ordet auto (för själv) och morphism från omvandlig/avbildning och utgör här alla permutationer på V som bevarar grafstrukturen. En grafs automorfismer är i praktiken dess symmetrier, de geometriska operationernasom man man kan göra på grafen som inte förändrar hur den sitter ihop.

Formellt så är automorphismerna i detta sammanhang de permutationer som bevarar E.

Definition: $\sigma \in \text{Aut}(V,E)$ om och endast om det för varje $\{x,y\} \in E$ gäller att $\{\sigma(x), \sigma(y)\}$

eller om man vill använda funktion-på-mängdnotation

$\sigma(E) = E$

Sättet man läser det aktuella problemet är att man vet att en automorfism är en symmetri och man undersöka vila symmetrier grafen har. Man kan byta plats på 1 och 2 utan att grafen förändras så (12) är en symmetri. Man kan rotera 123 noderna runt 4 utan att grafen förändras så en annan symmetri är (123). Osv.

Finns algoritmer som kan generera automofigruppen direkt från E men behövs inte när grafen är enkel.

SeriousCephalopod skrev:
$S_4$ är permutationsgruppen på 4 element och utgör mängden av alla bijektioner mellan $\{1,2,3,4\} \to \{1,2,3,4\}$ vilka kallas för permutationer.

Aut står för automorfi från ordet auto (för själv) och morphism från omvandlig/avbildning och utgör här alla permutationer på V som bevarar grafstrukturen. En grafs automorfismer är i praktiken dess symmetrier, de geometriska operationernasom man man kan göra på grafen som inte förändrar hur den sitter ihop.

Formellt så är automorphismerna i detta sammanhang de permutationer som bevarar E.

Definition: $\sigma \in \text{Aut}(V,E)$ om och endast om det för varje $\{x,y\} \in E$ gäller att $\{\sigma(x), \sigma(y)\}$

eller om man vill använda funktion-på-mängdnotation

$\sigma(E) = E$

Sättet man läser det aktuella problemet är att man vet att en automorfism är en symmetri och man undersöka vila symmetrier grafen har. Man kan byta plats på 1 och 2 utan att grafen förändras så (12) är en symmetri. Man kan rotera 123 noderna runt 4 utan att grafen förändras så en annan symmetri är (123). Osv.

Finns algoritmer som kan generera automofigruppen direkt från E men behövs inte när grafen är enkel.

Tack för förklaringen!

Jag har lite svårt med att förstå och visualisera hur man kan rotera och byta platser, liksom varför är inte (3,4) symmetri? Hur skulle figuren se ut då?

Låt säga att vi tog σ = (34) och tillämpade den på E = {{1,4}, {2,4}, {3,4}}

Vi får då

σ(E) = {{1,3}, {2,3}, {3,4}}

3 och 4 är fortfarande sammanlänkade men nu är 1 och 3 sammanlänkade vilka de inte var ursprungligen så då har vi förändrat grafen och då är det inte en automorfi.

Allmänna algoritmer är ganska komplexa men i fallet där en graf är ett träd så kan det vara enklare att se symmetrierna om man skriver grafen på traditionell trädform

Ta detta exempel.

Det är förhållandevis lätt att se att (56) är en automorfism eftersom de i praktiken utför en spegelsymmetri. Båda kommer att vara sammanlänkade med 1 även om vi byter plats på dem. På samma sätt är (47) en spegelsymmetri.

Ritar man upp grafen på ett mer symmetriskt sätt så kan man 'se' ännu fler symmetrier. Kan du hitta alla automorfismer om jag ritar samma graf på följande mer symmetriska sätt?

(1,2)(5,6)(4,7)(6,7)(5,7)(4,5)(5,7)(4,6)?

Du kan inte byta plats på bara (12) utan att förstöra grafstrukturen. Om vi gör (12) på grafen men inte ändrar något annat så blir 2 länkad med 5, och 6 vilket inte är förenkligt med grafstrukturen (E). Byter vi plats på 1 och 2 så måste måste vi även byta plats på 5,6 och 4,7

Ska vi ha en permutation som innehåller (12) så måste grenarna under 1 och 2 också byta plats. Så en automorfism är

(12)(57)(64)

men även (12)(54)(67)

I ett kan man byta plats på 'två underträd'/två grenar' om de är ekvivalenta.

De individuella transpositionerna i botten är automorfismer

(56) och (47)

Så jah får automorfismgruppen till

id, (56), (47), (12)(57)(64), och (12)(54)(67)

[men jag kan ha missat någon permutation]

Det vi försöker komma fram till här är en praktiskt förståelse av vad automorphismer på grafer är men procedurer för att finna dem är inte enkelt.

jahaaa okej nu tror jag att jag fattar, tack!