Chapitre 2 Constructions

2.1 Graphes

On a des opérations pour fabriquer des graphes à partir de graphes existants.

Soient G₁ et G₂ deux graphes dont les ensembles des sommets et arêtes sont V₁ et V₂, E₁ et E₂. On peut former sur l'ensemble produit V₁× V₂ des ensembles d'arêtes, et donc des graphes, avec les règles : {(u₁,u₂),(v₁,v₂)}Î V ssi

(u₁=v₁Ù u₂~ v₂)Ú(u₁~ v₁Ù u₂=v₂)	somme cartésienne

u₁~ v₁Ù u₂~ v₂	produit cartésien

(u₁=v₁Ù u₂~ v₂)Ú(u₁~ v₁Ù u₂=v₂) Ú(u₁~ v₁Ù u₂~ v₂)	produit fort

(u₁~ v₁Ù u₂=v₂)Ú(u₂~ v₂)	composition

Le line-graphe de G a pour sommets les arêtes de G et pour arêtes les paires d'arêtes qui ont un sommet en commun. Dans le cas orienté. on met un arc de (u₁,v₁) vers (u₂,v₂) si u₁=v₂.

Figure 2.1 : Le line-graphe du graphe de Petersen

Bien sûr, on peut en inventer bien d'autres.

2.2 Groupes

On a des opérations qui à partir de groupes permettent d'en fabriquer d'autres, et des constructions ex nihilo. Certaines peuvent être mises à profit pour construire des graphes de Cayley.

On a par exemple le groupe

des entiers relatifs pour l'addition.

Comme il est commutatif (on dit aussi abélien), c'est-à-dire que a+b=b+a pour tous entiers a,b, ses sous-groupes sont normaux.

On dit qu'un sous groupe H d'un groupe G est normal si pour tout gÎ G on a gH=Hg. Il s'ensuit que l'ensemble quotient G/H des classes gH, gÎ G est naturellement muni d'une structure de groupe qui fait de la surjection naturelle g|® gH un morphisme de groupes.

On a donc les quotients

, qui sont des groupes abéliens, finis à n éléments pour n¹0; on les appelle groupes cycliques. Le graphe de Cayley de

et {1,-1} est le cycle à n sommets.

On peut faire le produit direct de deux groupes G₁ et G₂, c'est le groupe dont l'ensemble G₁× G₂ est le produit des ensembles G₁ et G₂, et l'opération est donnée par (a₁,a₂)*(b₁,b₂)=(a₁*b₁,a₂*b₂) pour tous a₁,b₁ de G₁ et a₂,b₂ de G₂.

Si S₁ et S₂ sont des parties de G₁ et G₂ respectivement, on obtient avec les parties de G₁× G₂

e₁× S₂È S₁× e₂ la somme cartésienne
S₁× S₂ le produit cartésien
e₁× S₂È S₁× e₂È S₁× S₂ le produit fort
S₁× S₂ la composition

des graphes de Cayley attachés à G₁,S₁ et G₂,S₂.

Une construction plus générale, le produit semi-direct . On a un groupe G et une opération

de H sur G par automorphismes (ce qui veut dire que pour chaque hÎ H l'application g|® h

g est un automorphisme de G. Alors on définit le groupe G

H dont l'ensemble est G× H et l'opération est définie par (g₁,h₁)*(g₂,h₂)=(g₁*h₁

g₂, h₁*h₂). Alors la projection naturelle sur H est un morphisme de groupes, de noyau G× 1,qui est un sous-groupe normal de G

H et qui est isomorphe à G.

Parmi les produits semi-directs, notons celui où H est le groupe des automorphismes de G, avec son opération naturelle. Notons aussi le produit en couronne G

H, produit semi-direct de G^H et H, avec l'opération de H sur G^H donnée par (h

g)(i)=g(hi) pour toute application g:H® G (autrement dit gÎ G^H).

2.2.1 Exemples

Le théorème des restes chinois Si m et n sont premiers entre eux, le morphisme naturel de groupes et même d'anneaux

/mn

/m×

est un isomorphisme.

Le produit semi-direct de

et de

attaché à 0

x=x et 1

x= -x est isomorphe à

₃, le groupe des permutations d'un ensemble à 3 éléments assimilés aux 3 éléments du groupe

par (x,y)|® (z|® x+y

z).

Les groupes à 10 éléments et leurs graphes de Cayley de degré 3 De tels groupes ont 4+5t éléments d'ordre 5 et un nombre impair d'éléments 1+2s d'ordre 2. Donc 1+4+5t+1+2s=10. Donc t=0. Si un élément a d'ordre 5 commute avec un élément b d'ordre 2, il y a un élément d'ordre 10, ab, et alors le groupe est cyclique. Sinon, on doit avoir bab=a^-1, et on a le groupe dihédral, qui est produit semi-direct de

et de

; il y a alors 5 éléments d'ordre 2.

Pour former un graphe de degré 3, avec le groupe cyclique, on doit prendre l'élément d'ordre 2, et soit un élément d'ordre 5 et son inverse, (ce qui donne le 1.6.b), soit un élément d'ordre 10 et son inverse, (ce qui donne le 1.6.c). Pour le groupe dihédral, on doit prendre soit un élément d'ordre 2, et un élément d'ordre 5 et son inverse, (ce qui donne le le graphe 1.6.b), soit 3 éléments d'ordre 2 (ce qui donne le graphe 1.6.c).

Le graphe orienté de Cayley Cay(G,S) n'est en général pas isomorphe à Cay(G,S^-1), comme le montre l'exemple suivant G est le produit semi-direct du groupe additif

et du sous-groupe à 3 éléments {1,2,4} du groupe multiplicatif de l'anneau

, avec l'opération naturelle (x,m)*(y,n)=(x+my,mn), et la partie S={(1,1),(0,2),(2,2),(4,2)} Le graphe induit sur voisinage sortant du neutre, pour Cay(G,S) et pour Cay(G,S^-1) est dessiné sur la figure 2.2.

Figure 2.2 : Voisinages de l'origine