Deveta lekcija: Izomorﬁzmi in avtomorﬁzmi

Pritisnite F11

Iz varnostnih razlogov je mogoče celozaslonski način vključiti samo s pritiskom na gumb F11 na tipkovnici.

Ko ste enkrat v celozaslonskem načinu, ga izključite spet s pritiskom na F11.

Deveta lekcija: Izomorﬁzmi in avtomorﬁzmi

Avtor: Primož Potočnik

Sodelujoče organizacije

Izvedbo projekta je omogočilo sofinanciranje Evropskega sklada za regionalni razvoj in Ministrstva za visoko šolstvo, znanost in tehnologijo. Pri tehnični izvedbi projekta so sodelovali: Fakulteta za matematiko in fiziko Univerze v Ljubljani, Društvo matematikov, fizikov in astronomov Slovenije ter DMFA-založništvo.

8 Izomorfizmi in avtomorfizmi

Vzemimo grafa $\Gamma$ in $\Gamma'$ . Bijektivni preslikavi $\varphi : V(\Gamma) \to V(\Gamma')$ , za katero je $uv \in E(\Gamma)$ natanko tedaj, ko je $\varphi (u) \varphi (v) \in E(\Gamma')$ , pravimo izomorfizem grafov. Grafa $\Gamma$ in $\Gamma'$ sta izomorfna, oznaka $\Gamma \simeq \Gamma'$ , če med njima obstaja kakšen izomorfizem. Pri delu z grafi izomorfnih grafov med seboj običajno ne ločimo (npr. pravimo, da graf vsebuje cikel, kar pomeni, da vsebuje podgraf, ki je izomorfen nekemu ciklu). V primeru, ko je graf $\Gamma'$ kar enak grafu $\Gamma$ , izomorfizmu grafov pravimo avtomorfizem grafa. Če množico avtomorfizmov danega grafa $\Gamma$ opremimo z operacijo komponiranja preslikav, dobimo grupo, ki ji pravimo grupa avtomorfizmov grafa $\Gamma$ in jo označimo z $Aut(\Gamma)$ . Kadar za poljubni točki grafa obstaja avtomorfizem, ki prvo preslika v drugo, pravimo, da je graf tranzitiven po točkah. Vsi cayleyjevi grafi so tranzitivni po točkah.

8.1 Izomorfnost grafov

Lastnosti grafa, ki jo imajo poleg grafa samega tudi vsi z njim izomorfni grafi, pravimo invarianta grafa. Osnovni način, s katerim dokažemo, da grafa nista izomorfna, je, da poiščemo grafovsko invarianto, v kateri se obravnavana grafa ločita. Preproste invariante so: število točk in povezav, število podgrafov izbrane vrste (npr. trikotniki), stopnje točk, dvodelnost, itn. Izomorfnost običajno dokažemo tako, da konstruiramo izomorfizem. Včasih si delo lahko poenostavimo, če upoštevamo, da sta grafa izomorfna natanko tedaj, ko sta izomorfna njuna komplementarna grafa.

Zgled
Dokažimo, da sta grafa $\Gamma_1$ in $\Gamma_2$ s slike 9 izomorfna, grafa $\Gamma_3$ in $\Gamma_4$ s slike 10 pa ne.

Rešitev

Graf $\Gamma_2$ je dvodelen z razbitjem $C =\{v_1,v_2,v_3,v_4\}$ , $D=\{v_5,v_6,v_7,v_8\}$ . Hitro tudi opazimo, da množici $A =\{u_1,u_3,u_6,u_8\}$ in $B =\{u_2,u_4,u_5,u_7\}$ tvorita dvodelno razbitje grafa $\Gamma_1$ . Izomorfizem $\varphi: \Gamma_2 \to \Gamma_1$ mora dvodelno razbitje seveda ohranjati. Poskusimo preslikati točko $v_1$ v $u_2$ . Ker je $v_5$ edina točka v množici $D$ , ki točki $v_1$ ni sosednja, in točka $u_8$ edina točka v množici $B$ , ki točki $u_2$ ni sosednja, mora izomorfizem $\varphi$ preslikati točko $v_5$ v točko $u_8$ .
Pri sliki točke $v_2$ imamo spet nekaj svobode, pa se odločimo za točko $u_4$ . S tem smo, enako kot zgoraj, določili sliko točke $v_6$ , ki se mora preslikati v točko $u_6$ .

Rešitev (nadaljevanje)

Nadaljujemo podobno in dobimo preslikavo $\varphi$ , ki se nam zdi primeren kandidat za izomorfizem:

Sedaj moramo preveriti, ali preslikava $\varphi$ povezave grafa $\Gamma_2$ res preslika bijektivno na povezave grafa $\Gamma_1$ . Za vsak $xy \in E(\Gamma_2)$ poglejmo sliko $\varphi(x) \varphi(y)$ :

V spodnji vrstici smo dobili natanko vse povezave grafa $G_1$ , kar pomeni, da je preslikava $\varphi$ res izomorfizem. Omenimo še, da je graf $\Gamma_1$ prikazan kot $3$ -kocka $Q_3$ , graf $\Gamma_2$ pa kot polni dvodelni graf $K_{4,4}$ brez štirih neodvisnih povezav, $K_{4,4} - 4K_2$ .

Oglejmo si sedaj grafa $\Gamma_3$ in $\Gamma_4$ . Vidimo, da graf $\Gamma_4$ vsebuje cikel dolžine $4$ , graf $\Gamma_3$ pa ne. Podobno vsebuje graf $\Gamma_4$ le dva cikla dolžine $5$ , $\Gamma_3$ pa mnogo več. Grafa tako nista izomorfna. Graf $\Gamma_3$ je izomorfen Petersenovemu grafu, graf $\Gamma_4$ pa $5$ -strani prizmi $C_5$ $\box$ $K_2$ .

8.2 Avtomorﬁzmi grafov

Izomorfizmu grafa vase rečemo tudi avtomorfizem grafa. Avtomorfizem grafa $\Gamma$ je torej permutacija točk grafa, ki vsak par sosednjih vozlišč preslika v par sosednjih vozlišč. (Pozor: če bi dovoljevali tudi neskončne grafe, bi morali zahtevati tudi, da se par nesosednjih vozlišč preslika v par nesosednjih vozlišč.) Avtomorfizem grafa $\Gamma$ lahko torej razumemo kot element simetrične grupe $Sym(V(\Gamma))$ .
Ker je produkt dveh avtomorfizmov grafa očitno spet avtomorfizem grafa (in ker je identiteta tudi avtomorfizem vsakega grafa), tvori množica vseh avtomorfizmov grafa podgrupo grupe $Sym(V(\Gamma))$ . To množico označimo s simbolom $Aut(\Gamma)$ in jo imenujemo grupa avtomorfizmov grafa $\Gamma$ .
Določati grupo avtomorfizmov grafa je načeloma težak problem, za nekatere posebne družine grafov, pa je naloga dokaj lahka. Poglejmo si nekaj primerov:

$Aut(K_n) = S_n$ ;
$Aut(C_n) = D_n$ ;
$Aut(K_{m,n}) \cong S_m \times S_n$ , če $m \ne n$ ;
$Aut(K_{n,n}) = S_n \times S_n \times S_2$ .

Nekoliko zanimivejše je določanje grupe avtomorfizmov Petersenovega grafa.

Zgled
Dokaži, da je grupa avtomorfizmov Petersenovega grafa izomorfna grupi $S_5$ .

Rešitev

Najprej opazimo, da lahko Petersenov graf predstavimo takole:

$V(Pet)= \{\{i,j\} : i,j \in \mathbb{Z}_5,i \ne j\}\}$ ,

$\{i,j\} \sim \{s,t\} \Leftrightarrow \{i,j\} \cap \{s,t\} = \emptyset$ .

Sedaj je očitno, da vsaka permutacija $\sigma \in Sym(\mathbb{Z}_5)$ porodi avtomorfizem grafa $\tilde{\sigma}$ , ki je definiran s predpisom $\{i,j\}^{\tilde{\sigma}} = \{i^{\sigma},j^{\sigma}\}$ . Na ta način smo grupo $Sym(\mathbb{Z}_n) \cong S_5$ vložili v grupo $Aut(\Gamma)$ . Dokazati moramo le še, da Petersenov graf ne premore drugih avtomorfizmov. To storimo z naslednjim premislekom.
Naj bo $v = \{0,1\} \in V(Pet)$ in $G = Aut(Pet)$ . Najprej opazimo, da $S_5$ (in zato tudi $Aut(Pet)$ ) deluje tranzitivno na točkah Petersenovega grafa. Zato nam lema o orbiti in stabilizatorju pove

$\mid G \mid = 10 \cdot \mid G_v \mid.$

Podobno vidimo, da $G_v$ deluje tranzitivno na soseščini $\{\{2,3\},\{3,4\},\{2,4\}\}$ vozlišča $v$ , saj vozlišče $u = \{2,3\}$ preslikamo v vozlišče $\{3,4\}$ z avtomorfizmom $\tilde{\alpha} \in G_v$ za $\alpha = (0)(1)(3)(2,4) \in S_5$ in v vozlišče $\{2,4\}$ z avtomorfizmov $\tilde{\alpha}$ za $\alpha = (0)(1)(2)(3,4)$ . Zato je

$\mid G \mid = 10 \cdot \mid G_v \mid = 10 \mid G_{vu} \mid \mid u_{G_v} \mid = 10 \cdot 3 \cdot \mid G_{vu} \mid.$

Rešitev (nadaljevanje)

Poglejmo si sedaj orbito elementa $z = \{3,4\}$ pri delovanju grupe $G_{vu}$ . Ker je $z$ sosed $v$ , se lahko z elementom iz $G_{vu}$ preslika zgolj v soseda $v$ . Očitno se ne more preslikati v $u$ , saj se tja preslika že $u$ sam. Po drugi stani pa avtomorfizem $\tilde{\alpha} \in G_{vu}$ za $\alpha = (0)(1)(2,3)(4)$ preslika z v tretjega soseda, $\{2,4\}$ , vozlišča $v$ . Zato je $z^{G_{vu}} = \{z,\{2,4\}\}$ , in zato

$\mid G \mid = 30 \cdot \mid G_{vu} \mid = 30 \cdot \mid G_{vuz} \mid \mid z^{G_{vu}} \mid = 60 \cdot \mid G_{vuz} \mid.$

Nazadnje poglejmo še orbito $w^G_{vuz}$ vozlišča $w =\{1,2\}$ . Ker je $w$ sosed točke $z$ , se z elementom iz $G_{vuz}$ preslika bodisi samega vase bodisi v $\{0,2\}$ , ne pa tudi v tretjega soseda, $u$ , točke $z$ , saj se v $u$ preslika že $u$ sam. Po drugi strani pa res obstaja permutacija $\alpha = (0,1)(2)(3)(4) \in S_5$ , za katero je $\tilde{\alpha} \in G_{vuz}$ in je $w^{\tilde{\alpha}} = \{0,2\}$ . Zato je

$\mid G \mid = 60 \cdot \mid G_{vuz} \mid = 60 \cdot \mid G_{vuzw} \mid \mid w^{G_{vuz}} \mid = 120 \cdot \mid G_{vuzw} \mid.$

Nazadnje pa premislimo še, da je $G_{vuzw}$ trivialna grupa. Namreč poljuben avtomorfizem Petersenovega grafa, ki pribije točke $u$ , $v$ , $z$ in $w$ pribije tudi peto točko, $t = \{4,5\}$ petcikla $uvzwt$ . Vsaka od preostalih petih točk pa je sosednja kaki izmed petih že pribitih točk tega petcikla. Zato takšno točko element iz $G_{vuzw}$ tudi pribije. S tem smo dokazali, da je $\mid G \mid = 120$ in zato

$Aut(Pet) \cong S_5.$