Chapitre 1 Définitions

1.1 Groupes

Un groupe est un ensemble G muni d'une opération *, c'est-à-dire d'une application G× G® G, soit (x,y)|® x*y, qui a de plus les propriétés :

pour tous x,y,z dans G, on a (x*y)*z=x*(y*z)
il y a un élément neutre e qui vérifie pour x de G xe=ex=x
pour tout x de G, il y a un inverse y tel que x*y=y*x=e.

Pour des raisons d'économie et de légèreté de l'écriture, on ne met parfois aucun signe pour l'opération.

Un homomorphisme de groupes G® H est une application f:G® H telle que f(x*y)=f(x)*f(y) pour tous x,y de G. La première étoile est l'opération de G, la seconde celle de H.

Un isomorphisme de groupes G® H est un homomorphisme qui est en plus bijectif. L'application réciproque est alors, elle aussi, un isomorphisme de groupes.

Un sous-groupe d'un groupe G est une partie H d'un groupe G non-vide, stable par l'opération de G et par passage à l'inverse. La restriction de l'opération de G à H en fait un groupe.

Soit x un élément du groupe G. S'il existe des entiers n>0 tels que xⁿ=e, on appelle ordre de x le plus petit de ces entiers.

1.1.1 Exemples

Voici les tables des deux groupes non isomorphes à 4 éléments : la case à l'intersection de la ligne i et de la colonne j contient i*j

	0	1	2	3
0	0	1	2	3
1	1	2	3	0
2	2	3	0	1
3	3	0	1	2

	00	10	01	11
00	00	10	01	11
10	10	00	11	01
01	01	11	00	10
11	11	01	10	00

On reconnaît dans le premier cas l'addition des entiers modulo 4 et dans le deuxième l'addition dans (

)². Il est isomorphe au groupe des isométries dans le plan d'un rectangle non carré (voir 1.1). L'élément neutre 00 est associé à l'identité.

Figure 1.1 : Symétries du rectangle dans le plan

Les groupes ci-dessus ont des sous-groupes à 2 éléments, {0,2} pour le premier, {00,01} entre autres pour le second.

Pour en savoir plus: [137]

1.2 Groupe opérant sur un ensemble

On dit qu'on a une opération d'un groupe G sur un ensemble X quand on a une application G× X® X, soit (g,x)|® g

x qui vérifie en plus :

pour tous g,h dans G et x dans X, on a (g*h) x=g(h x)
l'élément neutre e vérifie pour tout x de X e x=x

Il revient au même de dire qu'on a un homomorphisme du groupe G dans le groupe des bijections de X sur lui-même, muni de la composition, cet homomorphisme étant h|® (x|® h

x).

Si xÎ X, l'orbite Gx de x par G (il faut bien sûr préciser l'opération en cas de doute) est l'ensemble des g

x, où g parcourt G. Le stabilisateur de x est la partie de G formée des h tels que h

x=x.

On constate que ``être dans la même orbite'' est une relation d'équivalence, dont l'ensemble des classes est noté X/G. Si G est fini, on a pour chaque x de X la relation |G|=|Gx||Stab_Gx|, et si X est fini aussi, le nombre d'orbites |X/G| satisfait

|G||X/G|=

gÎ G

|{x;gx=x}|.

Cette relation est le théorème de Burnside.

Ainsi, prendre une orbite est une façon de remplacer un objet ``groupe opérant sur un ensemble'' par un objet plus petit, avec le même groupe. Une autre ``simplification'' peut se produire: s'il existe une partition de X en parties X_i, iÎ I, telles que gX_i est un des X_j quel que soit gÎ G, on a une opération de G sur I déduite naturellement de celle de G. Cela devient intéressant quand X n'a qu'une orbite, et que la partition n'est pas triviale (i.e. I a plus d'un élément, et ses éléments contiennent plus d'un élément de X), et les parties s'appellent alors blocs d'imprimitivité. S'il n'y a pas de telle partition non-triviale, l'opération est dite primitive.

1.2.1 Exemples

Le groupe

_X des permutations de X est formé des bijections de X, avec la composition. Il a son opération naturelle sur X, à savoir (p,x)|® p(x).

Théorème de Lagrange
On considère un groupe fini G, l'ensemble X=G et l'opération d'un sous-groupe H de G sur X définie par (h,x)=h*x par restriction de l'opération de G. Alors on constate que les orbites ont toutes le même nombre d'éléments, qui est |H|, donc |H|·|G/H|=|G|.

En particulier, l'ordre de tout élément de G divise G.

Théorème de Cauchy
Soit G un groupe fini dont l'ordre est multiple du nombre premier p. On considère l'ensemble X des listes de p éléments de G indexées par

telles que g₁*g₂*··· g_p=e. Le groupe

opère dessus par m

(g₁,g₂,...,g_p)=g_m+1,g_m+2,...,g_p,g₁... g_m. Les orbites ont 1 ou p éléments. Les orbites à un élément sont de la forme a,a,...,a avec a^p=e. Il y en a, car e,e,..., e en est une et leur nombre est multiple de p car l'ensemble X a |G|^p-1 éléments et ce nombre est multiple de p. Donc il y a des éléments d'ordre p dans G.

Petit théorème de Fermat
On considère l'ensemble X des applications

|® {1,2,...,k}, qu'on interprète comme p emplacements et k couleurs. On fait agir

par (g,x)|® gx avec (gx)(m)=x(m-g). On regarde les orbites. Leur nombre est (k^p+(p-1) k)/p. Le terme k^p vient de l'élément 0 et chacun des p-1 autres éléements du groupe donne k car il ne préserve que les applications constantes. Ce nombre est entier, donc p divise k^p+(p-1)k, et donc aussi k^p-k pour tout entier k.

1.2.2 Variantes

Certains auteurs préfèrent que l'opération se fasse ``de l'autre côté'', c'est-à-dire que le résultat de l'opération de gh sur x soit celui de h sur le résultat de g appliqué à x, ce qui permet, en notant (g,x)|® x^g l'opération d'avoir (x^g)^h=x^(gh).

1.3 Graphes

Un graphe est formé d'un ensemble de sommets et d'un ensemble de paires de sommets, appelées les arêtes. Un graphe à 5 sommets et 6 arêtes est dessiné dans la figure 1.2.

Figure 1.2 : Un graphe à 5 sommets et 6 arêtes

Un graphe orienté est formé d'un ensemble de sommets et d'un ensemble de couples de sommets, appelés les arcs.

Sauf avis contraire, on ne considérera que des graphes ayant un ensemble fini de sommets et du coup un ensemble fini d'arêtes.

1.3.1 Distances

Un graphe est dit connexe si toute paire de sommets {x,y} est reliée par une suite d'arêtes {x_ix_i+1},0£ i<k avec x₀=x et x_k=y. La longueur de la plus courte suite d'arêtes connectant x à y s'appelle distance de x à y. Pour un graphe orienté, ce sera la plus courte suite d'arcs successifs allant de x vers y qui sera prise en compte (cette distance n'est plus alors symétrique, en ce sens que l'on n'a plus forcément d(x,y)=d(y,x) comme dans le cas non-orienté). Le diamètre d'un graphe est la plus grande des distances entre deux sommets de ce graphe. L'excentricité d'un sommet est la distance maximum de ce sommet aux autres sommets. Le rayon est la plus petite des excentricités. Dans le cas orienté, il faut distinguer excentricités entrante et sortante et, du coup, rayons entrant et sortant, mais le diamètre n'est pas sujet à ces différences.

Le diamètre du graphe de la figure 1.2 est 2.

Le graphe de la figure 1.3 a pour rayon sortant 2 (sommet a) et pour rayon entrant 3 (tous sommets sauf a), et le diamètre vaut 4 (aller de b à a).

Figure 1.3 : Un graphe à 5 sommets et 6 arêtes

1.3.2 Symétries des graphes

Un graphe peut avoir des symétries, pompeusement appelées automorphismes, ce sont les bijections de l'ensemble des sommets qui préservent l'ensemble des arêtes. Le graphe de la figure 1.2 a deux automorphismes, l'identité (pas bien surprenant) et la bijection qui échange 1 et 2 d'une part, 4 et 3 d'autre part et laisse 0 en place. Cette bijection échange les arêtes {01} et {02} d'une part, {14} et {23} d'autre part, et laisse en place {12} et {34}.

Ces automorphismes forment un groupe pour la composition. Par là il faut entendre que si a,b sont des automorphismes, ab en est un aussi (ab est défini par (ab)(u)=a(b(u)) pour tout sommet u), que l'identité I (définie par I(u)=u pour tout sommet u) est dans le groupe et vérifie aI=Ia=a pour tout automorphisme, que (ab)c=a(bc) et enfin que si a est un automorphisme, il y a un automorphisme a^-1 appelé l'inverse de a tel que aa^-1=a^-1a= I.

Il va de soi que si un automorphisme d'un graphe G envoie le sommet u sur le sommet v, alors il y a exactement autant d'arêtes incidentes à u qu'à v. Autrement dit, une condition nécessaire pour qu'il existe un automorphisme a de G tel que a(u)=v est que u et v aient le même degré. Mais cette condition n'est pas suffisante. Voir les sommets 0 et 3 dans la figure 1.2.

On dit qu'un graphe est sommet-transitif si pour tout couple de sommets il y a au moins un automorphisme qui envoie le premier sur le second. Ce n'est bien sûr pas le cas pour le graphe de la figure 1.2. Mais ce l'est pour le graphe de la figure 1.4.

Figure 1.4 : Un graphe sommet-transitif à 7 sommets

On dit que le graphe est arête-transitif si pour tout couple d'arêtes il y a au moins un isomorphisme qui envoie la première sur la seconde. Ce n'est le cas ni pour le graphe de la figure 1.2 ni celui de la figure 1.4. Ce l'est pour le graphe de la figure 1.5 qui n'est pourtant pas sommet-transitif.

Figure 1.5 : Un graphe arête-transitif à 5 sommets

Il va de soi que si le graphe est sommet-transitif, son diamètre se calcule en regardant la plus grande distance à partir d'un sommet donné.

1.3.3 Variantes

On peut aussi admettre des arêtes allant d'un sommet à lui-même, plusieurs arêtes joignant les deux mêmes sommets, plusieurs arêtes allant d'un même sommet de départ à un même sommet d'arrivée, etc. On parlera alors plutôt de multigraphes, de multidigraphes.

1.4 Graphes de Cayley

Un graphe de Cayley est un graphe obtenu à partir d'un groupe G, d'une partie S de G telle que eÏ S et aÎ SÛ a^-1Î S. Ses sommets sont les éléments de G, ses arêtes sont les paires {a,as} avec aÎ G et sÎ S. Le graphe obtenu à partir de G et S sera noté Cay(G,S).

Le graphe de la figure 1.4 est le graphe de Cayley attaché au groupe

et à la partie {1,2,5,6} de ce groupe.

Un graphe de Cayley est toujours sommet-transitif, car on remarque que l'application x|® hx (translation par h) envoie l'arête {x,xs} sur l'arête {hx,(hx)s} car h(xs)=(hx)s.

Mais un graphe sommet-transitif n'est pas toujours un graphe de Cayley.

Le fameux graphe de Petersen (figure 1.6a) n'est en effet isomorphe à aucun des deux graphes de degré 3 que l'on obtient avec les groupes d'ordre 10 (figure 1.6b,c).

Figure 1.6 : 3 graphes sommet-transitifs à 10 sommets

Cependant, si un graphe (V,E) est sommet-transitif, il existe un groupe G, un sous-groupe H, une partie S de G (qu'on peut exiger disjointe de H) et une application surjective f:G® V telle que

f(u)=f(v) si et seulement si uÎ vH
f(v) et f(u) sont adjacents si et seulement si uÎ vHS, c'est-à-dire s'il existe hÎ H et sÎ S tel que u=vhs

En effet, on peut prendre pour G le groupe des automorphismes de (V,E), pour H le stabilisateur d'un sommet a, et pour S l'ensemble des sÎ G tels que HaHs=Hb pour au moins un sommet b voisin de a. Alors l'application G/H® V définie par gH|® ga est un isomorphisme de graphes.

Si un sous-groupe A d'automorphismes de G vérifie AS=S, alors A induit un automorphisme de graphes de Cay(G,S). Si de plus l'opération de A sur S est transitive (c'est-à-dire, ne produit qu'une orbite), alors Cay(G,S) est arête-transitif.

1.4.1 Exemples

G est le groupe additif de

/13

, S={1,5,-1,-5}, A est le sous- groupe du groupe multiplicatif de

/13

engendré par 5. On a ainsi un graphe de Cayley arête-transitif (figure 1.7).

Figure 1.7 : Un graphe de Cayley arête-transitif à 13 sommets

Le graphe C₆ est le 6-cycle, c'est-à-dire le graphe de Cayley du groupe

avec la partie {1,5}. Son groupe d'automorphismes a 12 éléments, correspondant aux bijections a|® u a+b, avec uÎ{1,5} et bÎ

. Il y a une seule orbite, et deux partitions non triviales en blocs d'imprimitivité, à savoir {{0,2,4},{1,3,5}} et {{0,3},{1,4},{2,5}}.

Le groupe

₄ des permutations de l'ensemble {1,2,3,4} avec la partie {(12),(234),(243)} donne le graphe de la figure 1.8

Figure 1.8 : Un graphe de Cayley sur ₄

La connexité du graphe de Cayley Cay(G,S) équivaut au fait que S engendre G, en d'autre termes, que tout élément de G est produit d'éléments de S.

Il peut arriver que le graphe de Cayley ait plus de symétries que ne le laissait prévoir les automorphismes du groupe. Par exemple, le graphe de la figure 1.9 est défini à partir de trois symétries-points autour de trois points non alignés de (

)². Il y a 216 automorphismes, et pas seulement 108.

Figure 1.9 : Un graphe de Cayley très symétrique

1.4.2 Variantes

On peut autoriser e à faire partie de S (ce qui met une boucle en chaque sommet) ou renoncer à aÎ SÛ a^-1Î S, ce qui permet d'avoir des graphes orientés, etc.

On peut aussi représenter l'opération d'un graphe G sur un ensemble A, avec les arêtes a, s

a, où aÎ A et sÎ S, avec S une partie de G.

Si G admet un sous-groupe H, on peut construire deux choses :

On forme le graphe dont les sommets sont les classes Hg, et les arêtes (ou les arcs) sont les paires (ou les couples) [Hg,Hgs]. On trouve ainsi un graphe régulier de degré |S|, mais pas forcément sommet-transitif, qui peut contenir des boucles (si HÇ S¹ Ø) ou des arêtes multiples (si H× S® HS n'est pas injectif).

Plus généralement, on peut représenter l'opération d'un graphe G sur un ensemble A, avec les arêtes a, s^a, où aÎ A et sÎ S, avec S une partie de G (G opérant à droite sur A)
On forme le graphe dont les sommets sont les classes gH, et les arêtes (ou les arcs) sont les paires (ou les couples) [gH,gHsH]. On trouve ainsi un graphe régulier de degré |HSH|/|H|, sommet-transitif, qui peut contenir des boucles (si HÇ S¹ Ø) ou des arêtes multiples (si H× S® HS n'est pas injectif). Ce graphe est connexe si HÈ S engendre G.

Enfin, on peut ``décorer'' le graphe de Cayley, par exemple en marquant les arêtes provenant du même élément du groupe.

1.4.3 Exemples

Prenons le produit semi-direct G=

, avec l'opération (a,b)(a',b')=a+2^ba',b+b', puis S={(0,1),(1,1)}.

Le graphe orienté et ses projections sont visibles dans la figure 1.10

Figure 1.10 : Un graphe de Cayley sur le groupe /7/3 et ses projetés

Il ya des constructions voisines, certaines sont présentées par G. Gauyacq [76]. Essentiellemnt, on affaiblit la structure de groupe. On a encore une opération G× G® G. et une partie S de G. On forme le graphe avec pour sommets les éléments de G et pour arcs les (g,gs) avec gÎ G et sÎ S. La régularité des degrés sortants est acquise si |gS| ne dépend pas de g, celle des degrés entrants si x|® xs est bijective de G sur G, pour chaque sÎ S et la sommet-transitivité si x(yS)=(xy)S pour tous x,y de G et y® xy bijective de G sur G pour tout xÎ G.