M211 : Mathématiques discrètes

Université des Sciences et Technologies de LilleU.F.R. de Mathématiques Pures et Appliquées

M211 : Mathématiques discrètes

Notes de cours par Clément Boulonne

L2 Mathématiques 2007 - 2008

Table des matières

1 Ensembles 31.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Relation d’équivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.3 Cardinalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

1.3.1 Ensembles finies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3.2 Ensembles infinis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

1.4 Résumé sur la combinatoire (Voir Feuille TD) . . . . . . . . . . . . . . . . . . . 71.5 Bĳections et groupes de permutations . . . . . . . . . . . . . . . . . . . . . . . . 8

1.5.1 Représentations des permutations . . . . . . . . . . . . . . . . . . . . . . 8

2 Graphes et arbres 92.1 Introduction des graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.2 Premières définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.3 Exemples de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.4 Etude de graphes planaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.4.1 Démonstration du théorème d’Euler . . . . . . . . . . . . . . . . . . . . . 152.4.2 Quelques astuces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

2.5 Homomorphismes de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.5.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182.5.2 Lien entre groupes et graphes . . . . . . . . . . . . . . . . . . . . . . . . 202.5.3 Lien entre graphes et groupes . . . . . . . . . . . . . . . . . . . . . . . . 22

2.6 [TD] Modélisation de jeux combinatoires . . . . . . . . . . . . . . . . . . . . . . 232.6.1 Taquin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.7 Chemins dans un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242.8 Représentation matricielle pour les graphess . . . . . . . . . . . . . . . . . . . . 272.9 Rappel sur les graphes planaires . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3 Groupes 313.1 Introduction sur les groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 313.2 Actions de groupes - Exemples de groupes . . . . . . . . . . . . . . . . . . . . . 323.3 Sous-groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.4 Homomorphisme de groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353.5 Groupe quotient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

3.5.1 Quotient d’un espace vectoriel . . . . . . . . . . . . . . . . . . . . . . . . 373.5.2 Quotient de groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

3.6 Homomorphismes non-triviaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

2

Chapitre 1

Ensembles

1.1 IntroductionParadoxe de Russel Soit X l’ensemble de tous les ensembles qui ne se contiennt pas.

Est-ce que x ∈ X ? Les membres de cet ensemble n’appartiennent pas à eux-mêmes, iln’appartient pas à lui-même. Est-ce que x 6∈ X, il a la propriété requise pour appartenir àlui-même. Donc tout cela amène à des contradictions.

Définition 1.1.1. On note X ⊃ Y si Y est un sous-ensemble de X et X % Y si Y est unsous-ensemble propre de X (c’est-à-dire contenu dans X mais distinct de X).

Définition 1.1.2. X, Y deux ensembles alors :

X ∪ Y = {a; a ∈ X ou a ∈ Y }

X ∩ Y = {a; a ∈ X et a ∈ Y }

Définition 1.1.3. X, Y deux ensemble alors :

X × Y = {(x, y), x ∈ X, y ∈ Y }

Définition 1.1.4. f : X → Y est une application de X dans Y . Elle est :• injective si pour x, y ∈ X, f(x) = f(y)⇒ x = y• surjective si chaque y ∈ Y est de la forme f(x) pour au moins un x ∈ X.• bĳective si elle est injective et surjective.

1.2 Relation d’équivalenceDéfinition 1.2.1. Soit X un ensemble alors :

r : X ×X → {vrai, faux}

r est une relation entre éléments de X (on la note aussi ∼).

Proposition 1.2.1. Si :1. a ∼ b⇒ b ∼ a

2. a ∼ a

3. a ∼ b et b ∼ c⇒ a ∼ c.

3

4 Chapitre 1. Ensembles

∼ est appelée alors relation d’équivalene. En terme de booléens :1. r(a, a) = vrai2. r(a, b) = vrai⇒ r(b, a) = vrai3. r(a, b) = vrai et r(b, c) = vrai⇒ r(a, c) = vrai

Définition 1.2.2. Soit X ensemble et ∼ est une relation d’équivalence alors X/ ∼ est l’en-semble des classes d’équivalence ou l’ensemble quotient.Exemple 1.2.1. PacMan est un jeu vidéo où on prend le contrôle d’une boule en forme depart de pizza et qui a pour but de récupérer de la nourriture en évitant les fantômes qui rodentdans un ensemble (ici un carré). Quand on est à l’extermité de l’ensemble, PacMan revient àl’autre extremité opposé du carré.

Soit X : [0, 1]→ [0, 1]. On définit une relation d’équivalence ∼ tel que :

∼:

(x, y) ∼ (x, y) si 0 < x < 1 et 0 < y < 1(x, 1) ∼ (x, 1)(x, 1) ∼ (x, 0)(x, 0) ∼ (x, 0)(0, y) ∼ (0, y)(0, y) ∼ (1, y)(1, y) ∼ (1, y)

Alors X/ ∼ est un tore.

Fig. 1.1 – Ensemble et ensemble quotient pour PacMan

Exemple 1.2.2. Soit X un cercle. Si a ∈◦X, a ∼ a. Si a et b ∈ X\

◦X. X/ ∼ est une sphère.

Fig. 1.2 – Ensemble et ensemble quotient pour le cercle

Exemple 1.2.3. Soit X : [−1, 1]× [−1, 1] et soit ∼ tel que :(x, y) ∼ (x, y) si x 6= {−1, 1}

(−1, y) ∼ (−1, y)(−1, y) ∼ (1, y)(1, y) ∼ (−1,−y)

si x = {−1, 1}

Chapitre 1. Ensembles 5

Fig. 1.3 – Ensemble et ensemble quotient dans l’Exemple 1.1.3.

alors X/ ∼ est un ruban de Mobius.

Exemple 1.2.4. Soit X la sphère et ∼ tel que a ∼ a et a ∼ −a (a et −a deux points del’extremité du rayon de X) alors X/ ∼= RP 2 est appelé plan projectif.

1.3 Cardinalité

1.3.1 Ensembles finiesDéfinition 1.3.1. X est un ensemble fini s’il existe une fonction entre X et l’ensemble {1, ..., n}pour un certain n ∈ N.

Notation. Dans ce cas, on dira que card(X) = n.

Proposition 1.3.1. Si f : {1, ...,m} → {1, ..., n} est une injection.

Démonstration. Si m = 1 évident. Soit m fixé alors on va démontrer que si f : {1, ...,m +1} → {1, ..., n + 1} injectif (on notera f : {1, ...,m + 1} ↪→ {1, ..., n + 1} quand f est injectif).Soit g : {1, ...,m} → {1, ..., n}. Si f(i) 6= n + 1 alors g(i) = f(i) et si f(i) = n + 1 alorsg(i) = f(m+ 1).Remarque. g est une injection, cela implique que m ≤ n et m+ 1 ≤ n+ 1.

Corollaire. Il n’existe pas une bĳection entre un ensemble fini et un sous-ensemble propre.

Exemple 1.3.1. Il n’y a pas de bĳection entre N× et N×\{1}.

Définition 1.3.2. X est dénombrable s’il existe une bĳection entre X et N .

Exemple 1.3.2. Z = {...,−1, 0, 1, ...}. On introduit :

f : n→

f(n) = 2n si n > 0f(n) = 2|n|+ 1 si n ≤ 0

Exemple 1.3.3. Q+. On peut voir cette ensemble comme un tableau infini :

11

21

31 · · ·

12

22

32

42 · · ·

13

23

33

43 · · ·

... ... ... ...

On applique la “méthode de la pluie” pour trouver une bĳection de Q+ à N.


Fig. 1.4 – “Méthode de la pluie” pour trouver une bĳection de Q+ à N

1.3.2 Ensembles infinisExemple 1.3.4. 2N espace de fonctions f : N→ {0, 1} n’est pas dénombrable.

Démonstration. On utiise ce qu’on appelle l’argument de la diagonale de Cantor. Soit ak ∈{0, 1}

0 1 1 0 · · · 0 0 1 1 · · ·a1 a2 a3 · · · · · · · · · an

On démontre que 2N n’est pas dénombrable par l’absurde. On suppose que 2N est dénombrables.Soient des suites :

a11 a12 a13 a14 · · ·a21 a22 a23 a24 · · ·a31 a32 a33 a34 · · ·a41 a42 a43 a44 · · ·

. . .

(L1)

On construit une autre suite d’éléments (aii)i∈N tel que :

aii =

1 si aii = 00 si aii = 1

Cette suite n’est pas dans la litste (L1).

Exemple 1.3.5. [0, 1] n’est pas dénombrable.

Démonstration. Soient les nombres :

0, a11a12...a1n...

0, a21a22...a2n...

0, a31a32...a3n...

Mais on ne veut pas qu’à partir d’un certain rang les aij soient égaux.

0, a11a12a13...a1n...

0, a21a22a23...a2n...

0, a31a32a33...a3n...

Si : aii = 9 aii = 0aii 6= 9 aii = aii + 1

0, a11a22a33a44... n’appartient pas à la liste.

Chapitre 1. Ensembles 7

Définition 1.3.3. SI X ↪→ Y alors card(X) ≤ card(Y ).Theorème 1.3.2 (Schröder-Bernstein). S’il existe une injection X ↪→ Y et une injectionY ↪→ X alors il existe une bĳection X → Y .Démonstration. On va considérer deux pays : la France (F ) et l’Allemagne (A) et leshommes. On va construire une fonction telle qu’un homme d’un pays à un fils dans un autre.On note :

en Allemagne :

A∞ : généalogie infinieAA : généalogie finie en AllemagneAF : généalogie finie en France

en France :

F∞ : généalogie infinieFA : généalogie finie en AllemagneFF : généalogie finie en France

On a alors les propriétés suivantes :AA ∪ A∞ ∪ AF = A et FA ∪ F∞ ∪ FF = A

AA ∩ A∞ = ∅A∞ ∩ AF = ∅AA ∩ AF = ∅

et

FA ∩ F∞ = ∅F∞ ∩ FF = ∅FA ∩ FF = ∅

Soit f : F → A et g : A→ F , on a :f : F∞ → A∞ bĳectivef : FF → AF bĳectiveg : AA → FA bĳective

→ bĳection

Définition 1.3.4. Soit le carré ]0, 1[×]0, 1[ et l’intervalle ]0, 1[. On veut construire deux in-jections. La première t est celle qui va de l’intervalle au carré et l’autre s va du carré versl’intervalle.

t→(t,

12

)s : (0, x1x2x3, ...; 0, y1y2y3...) 7→ (0, x1y1x2y2...)

Par exemple s(0, 1; 0, 1)→ (0, 11).Démonstration. On montre que s est injectif. Si (0, x1y1x2y2x3y3...) = (0, x′1y′1x′2y′2...) alors(0, x1x2...; 0, y1y2...) = (0, x′1x′2; 0, y′1y′2).

1.4 Résumé sur la combinatoire (Voir Feuille TD)1. Si card(X) = n et card(Y ) = m alors :

card(X × Y ) = mn

2. Les nombres d’applications entre X et Y sont au nombre de mn

3. Le nombre d’injection entre X et Y sont au nombre de (m)n.4. Le nombre de sous-ensembles de X de cardinal k est Ckn = (n)k

k! = n!(n−k)!k! .

5. Le nombre de tous les sous-ensembles de X est 2n.6. (a+ b)n =

n∑k=0

Cknan−kbk.

7. Ckn = Ck−1n−1 + Ckn−1 avec Cnn = C0

n = 1.


1.5 Bĳections et groupes de permutationsDéfinition 1.5.1. Soit X un ensemble tel que card(X) = n alors on note Bĳ(X) l’ensemblede toutes les bĳections de X sur lui-même. On a alors : card(Bĳ(X)) = n!.

Définition 1.5.2. Si X = {1, ..., n}. Sn := Bĳ(X) alors Sn est le groupe des permutations à néléments.

1.5.1 Représentations des permutations1. (

1 2 3 · · · nσ(1) σ(2) σ(3) · · · σ(n)

)σ : {1, ..., n} → {1, ..., n}

Exemple 1.5.1. S3 = {1, 2, 3} → {1, 2, 3}(1 2 31 2 3

) (1 2 32 1 3

)(

1 2 33 2 1

) (1 2 31 3 2

)(

1 2 32 3 1

) (1 2 33 1 2

)

Il y a 6 éléments dans S3.2. Représentation d’un produit :(

1 2 33 2 1

)(1 2 33 1 2

)=

(1 2 32 1 3

)−→(

1 2 33 1 2

)(1 2 33 2 1

)=

(1 2 31 3 2

)−→(

1 2 31 3 2

)(1 2 33 1 2

)=

(1 2 33 2 1

)−→

−→ représente dans quel sens on fait la multiplication.

Chapitre 2

Graphes et arbres

Cours sur les graphes : http://www.apprendre-en-ligne.net/graphes

2.1 Introduction des graphesExemple 2.1.1. Ceci est un graphe.

Définition 2.1.1. Soient S un ensemble de "sommets" et A un ensemble d’"arrêtes". On définit :

α : A→ Sω : A→ S

2 fonctions

Tout cela définit un graphe orienté.

Exemple 2.1.2. Si y ∈ A, α(y), ω(y) se définit comme ceci.

Si z ∈ A, on peut avoir α(z) = ω(z)

9

http://www.apprendre-en-ligne.net/graphes

10 Chapitre 2. Graphes et arbres

Exemple 2.1.3. 1) On peut relier les capitales européennes pour construire un graphe.

2) Soit S examens et A : "deux examens sont liés si un étudiant prend les deux examens. Onpeut colorier les arrêtes tel qu’un jour représente une couleur.

3) Les ponts de Koningsberg :

Le problème est de passer sur les 7 ponts une et une seule fois en partant d’un sommetdonnée. On peut représenter par un graphe le problème :

Définition 2.1.2. Soit S des sommets. On considère (S × S,∼) et on dit que (a, b) ∼ (b, a) sia et b sont reliés. (S × S/ ∼) = Σ. Un ensemble (S,E) avec E ⊂ Σ est un graphe non orienté.

Chapitre 2. Graphes et arbres 11

Définition 2.1.3. Un graphe simple est un ensemble (S,E) tel que S sommets et E ⊂ ((S ×S\∆)/ ∼) avec ∆ = {(s, s), s ∈ S}.

2.2 Premières définitionsDéfinition 2.2.1. Soit S un ensemble des sommets et A un ensemble d’arrêtes et f : A→ S×Salors la donnée de ces structures peut définir un graphe.

Exemple 2.2.1. On a S = {u, v, w, x, y} et A = {1, 2, 3, 4, 5}

f(1) = (w,w)f(2) = (w, u)f(3) = (v, x)f(4) = (x, y)f(5) = (y, x)

Remarque. Selon cette définition :1) On peut avoir des boucles.2) Les arrêtes qui ne sont pas des boucles ne sont pas orientés.3) On peut avoir une multitude d’arrêtes entre deux sommets.

Définition 2.2.2. Soit S un ensemble et Π : S × S → {0, 1}. On dit que x ∈ S est adjaçant ày ∈ S ⇔ Π(x, y) = 1.

Définition 2.2.3. Si ∀x ∈ S, Π(x, y) = Π(y, x) et Π(x, x) = 0 alors on a un graphe simple.

2.3 Exemples de graphesExemple 2.3.1 (Ponts de Koningsberg). Peut-on faie une promenade où on passerait par les7 ponts une et une seule fois enn revenant par le point de de départ ?


Définition 2.3.1. Un circuit eulérien est un circuit qui contient toutes les arrêtes une seulefois.

Problème. Si Γ est un graphe, admet-il un circuit eulérien ?

Ici le problème des ponts de Koningsberg ne peut se résoudre car il n’existe pas de chemineulérien (il n’existe pas plus de deux sommets de degré1 impair).

Exemple 2.3.2. Peut-on passer par un et un seul sommet en revenant par le point de départ ?

Définition 2.3.2. Un circuit hamiltonien est un circuit qui contient tous les sommets une seulefois.

Problème. Si Γ est un graphe, admet-il un chemin hamiltonien ?

Définition 2.3.3. Un graphe simple est dit planaire si il peut être représenté sur le plan defaçon à ce que les arrêtes ne se coupent pas.

Problème. Si Γ est un graphe, déterminer s’il est planaire.

On peut représenter le graphe sur une sphère puis sur un plan grâce à la projection stéréogra-phique.

1Le degré d’un sommet est le nombre d’arrêtes admettant le sommet pour extrémité


Theorème 2.3.1 (Euler). Si Γ est planaire alors :

s− a+ f = 2

avec• s : nombre de sommets• a : nombre d’arrêtes• f : nombre de faces

Exemple 2.3.3 (Les graphes Kn, Kn,m). Les graphes Kn sont les graphes complets à n som-mets.

Les graphes Km,n sont les graphes bipartits complets.

Problème. Peut-on dessiner les graphes bipartits sans avoir d’intersections ?

On peut représenter ce graphe dans un tore en representant le croisement par un pont.

Exemple 2.3.4. Dans la figure suivante, on a la propriété suivante :

so− sa+ p = 2

avec :• so = nombre de sommets• se = nombre de selles• p = nombre de puits


Exemple 2.3.5. Soit S un ensemble d’examens et A étudiants en mathématiques. Soit f :S × S → {0, 1} tel que f(x, y) = 1 si et seulement si il y a au moins un étudiant qui présentex et y. Soit

X = {lundi,mardi,mercredi, jeudi, vendredi, samedi, dimanche}

et D : S → X. On voudrait avoir si x est adjaçant à y alors D(x) 6= D(y).Définition 2.3.4. Soit Γ un graphe, un coloriage de Γ à n couleurs est une application :

c : P → {1, ..., n}

tel que si x est adjaçant à y alors :c(x) 6= c(y)

Problème. a) Si Γ est un graphe, quel est le nombre minimal de couleurs avec lequel il peutêtre coloriée.

b) Comment le faire de façon efficace ?

Exemple 2.3.6 (Arbres).Définition 2.3.5. Un arbre est un graphe simple connexe sans circuits.

Définition 2.3.6. Γ est connexe si deux sommets quelconques peuvent être réliés par unchemin.Proposition 2.3.2. Γ est un arbre si s− a = 1 avec :• s = nombre de sommets• a = nombre d’arretes


2.4 Etude de graphes planairesDans cette section, tous les graphes sont connexes et simples.

2.4.1 Démonstration du théorème d’EulerRappel (Théorème 2.3.1). Si Γ est planaire2 alors :

s− a+ f = 2

avec :• s : nombre de sommets.• a : nombre d’arrêtes.• f : nombre de faces.

Démonstration. On note les arrêtes bleues T1 et les arrêtes rouges T2. Pour Γ :

• sT1 = sΓ• sT2 = fΓ• aT1 + aT2 = aΓ• sT1 − aT1 + aT2 − aT2 = 2

2.4.2 Quelques astuces1. Si Γ est un graphe quelconque, on peut former le graphe bipartite sommets-arrêtes.

2. Si Γ est un graphe planaire, on a une autre représentation planaire, le graphe faces-arrêtes :2c’est-à-dire representé sur un plan sans intersections d’arrêtes


Proposition 2.4.1. Si Γ est planaire alors 2a ≥ 3f .

Démonstration. On regarde le graphe faces-arrêtes :1. Chaque arrête appartient à une ou deux faces (a ≤ 2a).3

2. Chaque face a au moins 3 arrêtes pour bord (a ≤ 3f)Donc : 2a ≥ 3f .

Proposition 2.4.2. K5 n’est pas planaire.

Démonstration. s = 5, a = 10, f = 7 (par le théorème d’Euler) mais 2 × 10 � 3 × 7.CONTRADICTION !

Proposition 2.4.3. K3,3 n’est pas planaire.

Démonstration.Remarque. On ne peut pas avoir de faces triangulaires ⇒ 2a ≥ 4f .

Mais a = 9 et f = 5 et 2× 9 ≤ 5× 4. CONTRADICTION !

Proposition 2.4.4. Si Γ est planaire, il y a au moins un sommet de degré 5.

Définition 2.4.1. Le degré d’un sommet est le nombre d’arrêtes partant et venant de cesommet.

Démonstration. Par contradiction, on suppose qu’on a que chaque sommet a un degré ≥ 6.On a alors :• a ≥ 6• a = 2a

Les deux inégalités 1) et 2) sont incompatibles :1) 2a ≥ 6s2) 2a ≥ 4f ⇒ 4a ≥ 6f (2′)On addition (1) + (2′) :

6a ≥ 6(s+ f)⇒ a ≥ 5 + f ≥ 0 ≤ s− a+ f = 2

CONTRADICTION !

Proposition 2.4.5. Si Γ est planaire, il peut être coloriée avec six couleurs.

Démonstration. Par reccurence sur le nombre de sommets. Pour un graphe planaire à unsommet, on peut le colorier avec 6 couleurs. On suppose pour un graphe planaire à n sommetsqu’on peut le colorier avec 6 couleurs. Soit un graphe avec n+1 sommets (x le (n+1)ème sommet).Par hypothèse, on peut colorier Γ\{x} avec six couleurs. Les voisins de x sont coloriés par lescouleurs c1, c2, c3, c4, c5 (au pire) donc on peut choisir c6.

3a = nombre d’arcs


[Annexe] Caractérisation des graphes planaires

Theorème 2.4.6 (Kuratowski). Un graphe est planaire si et seulement si il ne contient pas degraphes de type K3,3 et de type K5.

Proposition 2.4.7. Soit Γ un graphe simple. On peut colorier Γ en deux couleurs si et seule-ment si Γ n’a pas de cycles impaires.

Démonstration. Si Γ a un cycle impair, on ne peut pas colorier le graphe en deux couleurs.Si Γ n’a pas de cycles impaires, on prend un sommet x quelconque. Si x est blanc alors les

voisins de x sont noirs. On peut alors colorier les voisins des voisins de x en blanc. Ainsi desuite !

Méthode de coloriage des graphes - Polynôme chromatique

On définit le polynôme chromatique ZΓ(q, v) de la manière suivante :1) si Γ a un sommet alors ZΓ(q, v) = q.2) si Γ a un point isolé alors ZxΓ(q, v) = qZΓ(q, v)3) si on a :

On a alors :Zr1 = Zr2 + vZr3

Exemple 2.4.1. Soient :

alors :Zr1(q, v) = Zr2(q, v) + vZr3q, v = qZr3(q, v) + vq = q2 + vq


alors :Zr1(q, v) = Zr2(q, v) + vZr2(q, v) = (1 + v)Zr2(q, v)



alors :

Zr1(q, v) = Zr2(q, v) + vZr5(q, v) = Zr3(q, v) + vZr3(q, v) + vZr3(q, v) + v2Zr4(q, v)

= q2 + vq + vq2 + v2q + v(q2 + vq) + v2(Zr6(q, v) + vZr6(q, v)) = (1 + 2v)(q2 + vq) + v2q + v3q

Theorème 2.4.8. Si k ∈ N alors ZΓ(k,−1) est le nombre de façons de colorier Γ avec kcouleurs.

Remarque. S’il n’y a pas d’arrêtes et on a n sommets :

ZΓ(q,−1) = qn

Dans ce cas, le théorème est trivialement vérifié.

2.5 Homomorphismes de graphes

2.5.1 GénéralitésExemple 2.5.1. Soient les graphes suivants :

et f une application S1 → S2, g : A1 → A2 définie comme suivant :

f(s1) = σ1 g(a1) = α1f(s2) = σ g(a2) = α2f(s3) = σ2 g(a3) = α1


Définition 2.5.1. Soient G1 = (S1, A1) avec i1 : A1 → S1×S1 et G2 = (S2, A2) avec i2 : A2 →S2 × S2 deux graphes. Un homomorphisme (S1, A1) et (S2, A2) est une paire d’applications :

f : S1 → S2

g : A1 → A2

tel que le diagramme suivant est commutatif4 :

Démonstration. On reprend les graphes de l’Exemple 2.5.1.. Pour a1 :

a1 −→i1

(s1, s2) −−→f×f

(σ1, σ2)

a1 −→g

(α1) −→i2

(α1, α2)

Pour a2 :a2 −→i1

(s2, s3) −−→f×f

(σ1, σ2)

a2 −→gα2 −→

i2(σ1, σ2)

Pour a3 :a3 −→i1

(s1, s3) −−→f×f

(σ1, σ2)

a3 −→gα1 −→

i2(σ1, σ2)

Définition 2.5.2. G1 = (S1, A1) et G2 = (S2, A2) sont isomorphes s’il existe un homomor-phisme (f, g) dont f : S1 → S2 et g : A1 → A2 sont des bĳections.

Définition 2.5.3 (Version graphe non orienté). Une paire d’applications :

f : S1 → S2

g : A1 → A2

est un homomorphisme de graphes (non-orientés) si pour toute paire de sommets, x, y ∈ S1 etarrête a ∈ A1 joignant x et y, l’arrête g(a) joint f(x) et f(y). Si f et g sont des bĳections alorsles graphes (non-orientés) sont isomorphes.

Exemple 2.5.2. Le graphe d’un cube est isomorphe à sa représentation planaire.4c’est-à-dire qu’on peut partir d’une partie à une autre de deux façons (dans ce diagramme, on peut aller de

A1 à S2 × S2 en passant par (i1, f1 × f1) et (g, i2)). On note un diagramme commutatif en plaçant � au milieudu diagramme.


2.5.2 Lien entre groupes et graphesDéfinition 2.5.4. Un automorphisme d’un graphe est un isomorphisme de graphe sur lui-même.

Exemple 2.5.3. Soit le graphe suivant :

f : S → S définie par : f(s1) = s2

f(s2) = s3

f(s3) = s4

f(s4) = s1

et g : A→ A définie par : g(a1) = a2

g(a2) = a3

g(a3) = a4

g(a4) = a1

(f, g) est un automorphisme de graphes.

Proposition 2.5.1. L’ensemble d’automorphismes d’un graphe (avec la loi de composition) estun groupe.

Remarque. On peut écrire la définition d’homomorphisme de groupes avec des diagrammescommutatifs.


Dans le diagramme, on a : f(g1 ∗ g2) = f(g1) ◦ f(g2). On a aussi f(eG) = eH et le diagrammecommute.Démonstration (Cas orienté). Soit (S,A) un graphe, (f1, g1), (f2, g2) deux automorphismesc’est-à-dire :

f1 : S → Sf2 : S → S

}bĳections

g1 : A→ Ag2 : A→ A

}bĳections

et :

sont deux diagrammes commutatifs. On considère (f1 ◦ f2, g1 ◦ g2). il faut vérifier que f1 ◦ f2 estune bĳection g1 ◦ g2 est une bĳection (immédiat car une composition d’une bĳection est unebĳection) et que :

soit commutatif. On a :

Remarque. 1) Le diagramme (1) est la "composition" de deux diagrammes dans (2).2) Faire le chemin rouge ou faire le chemin bleu fait le même que le chemin vert.


2.5.3 Lien entre graphes et groupes

Définition 2.5.5. Soit G un groupe et soit X ⊂ G un sous-ensemble. X engendre 5 G si toutg ∈ G est un produit (de nombre fini) d’éléments de X.

Exemple 2.5.4. Dans les exemples suivants : X engendre G :

1) G = Z5 et X = {1}

2) G = Z5 et X = {2}

3) G = Z5 et X = {1, 2}

4) G = S3, X = {(12), (13), (23)}

Exemple 2.5.5 (Graphe de Cayley). On étudie les graphes de Cayley associés aux ensemblesgénérateurs et aux groupes qui sont engendrés par ces ensembles.

1) G = Z5, X = {1}

2) G = Z5 et X = {2}

3) G = Z5 et X = {1, 2}

5On dit que X est un ensemble générateur de G


4) G = S3, X = {(12), (13), (23)}

5) G = Z2 × Z2, X = {(1, 0), (0, 1)}

Définition 2.5.6. G groupe et X ⊂ G ensemble générateur. On peut associer S = G, A =X ×X et i : A→ S tel que i(g, x) = g(xg). Un tel graphe est (S,A) est un graphe de Cayleyassocié à (G,X).

2.6 [TD] Modélisation de jeux combinatoires

2.6.1 TaquinAu début, le taquin ressemble à un maillage 4× 4 (le 16 représente la case vide.


On appelera Γ ce type de graphe.

Définition 2.6.1. Une numérotation de Γ est une bĳection {1, ..., 16} → SΓ

Définition 2.6.2. Deux numérotations f et g sont adjaçantes si g−1 ◦ f est une permutationde la forme (x, 16) avec 1 ≤ x ≤ 15.

Définition 2.6.3. Le graphe du jeu est l’ensemble des numérotations possibles.

Définition 2.6.4. Une position légale est une numérotation dont le 16 est en bas à droite deΓ.

Remarque. Un jeu est un chemin sur le graphe du jeu.

Theorème 2.6.1. 1) Le sous-graphe du jeu engendré par les positions légales a deux compo-santes connexes.

2) La composante connexe qui contient la numérotation standard consiste de toutes les permu-tations paires de 15 éléments.

Remarque. Pour facilier le problème, on peut considérer un maillage 2× 2.

Définition 2.6.5. Une permutation est paire si elle est produit de transpositions paires.

2.7 Chemins dans un grapheDéfinition 2.7.1. Une promenade sur un graphe Γ est une séquence (a1s1, a2s2, ..., , ansn) avec :• si : sommets• ai : arrêtes qui joignent si−1 et si

Exemple 2.7.1. Exemple de promenade :


Remarque. Pour une promenade aléatoire (les probabilités sur chaque arrête est 1/ deg s), onest presque sûr de revenir au point de départ.

Définition 2.7.2. 1) Un chemin est une promenade dont tous les sommets sont distincts.2) Un cycle est une promenade dont tous les sommets sont distincts sauf le premier et le chemin

qui coïncide

Définition 2.7.3. Un graphe est connexe si chaque paire de sommets peut être joint par unchemin.

Définition 2.7.4. Un arbre est un graphe connexe sans cycles.

Theorème 2.7.1. Si Γ est un arbre, deux sommets quelconques distincts sont liés par un seulchemin.

Démonstration. Il y a au moins un chemin (connexité). On suppose qu’il y a deux cheminsqui relient deux sommets distincts quelconque sur un arbre. Soient P , P ′ ces deux cheminsreliant x et y. Soit u un sommet dans les chemins P et P ′ tel que les successeurs par P etP ′ sont différents. Soit v le premier sommet après u tel que les successeurs par P et P ′ sontidentiques. Mais ceci est impossible car un arbre est un grape sans cycle.

Problème des ponts de Koningsberg

Peut-on se promener en ville en revenant à notre destination de départ en passant par les 7ponts ?


Définition 2.7.5. Un circuit eulérien sur un graphe Γ est un circuit qui passe par chaquearrête une fois.

Définition 2.7.6. La matrice d’incidence associé à un graphe Γ est la matrice :

a1 a2 · · · ak

s1s2...sn

. .

... .

. .... .

· · · · · · mij · · ·. .

... .

avec :

mij =

0 si si 6∈ aj1 si si ∈ aj2 si aj est une boucle sur si

Définition 2.7.7. On définit l’ordre de si :

Ord(si) =k∑j=1

mij

Theorème 2.7.2 (Euler).n∑i=1

Ord(si) = 2a

avec a = le nombre d’arrêtes.

Démonstration. Les deux quantités sont égales à∑i,j

mij.

Theorème 2.7.3. Si Γ est un arbre, Γ a au moins deux sommets d’ordre 1.

Remarque. Si Γ est un arbre :s = a+ 1

Démonstration. ∑Ord(si) = 2× a = 2× s− 2 < 2s

⇒ Il y a au moins deux sommets d’ordre 1.

Theorème 2.7.4. Un graphe connexe admet un circuit eulérien si et seulement si l’ordre dechaque sommet est pair.


Démonstration. (⇒) 1) si x n’est pas un point de départ, on compte +1 si on arriveen x et −1 si on part de x. A la fin du circuit, le compteur doit être égal à 0 ⇒ lenombre d’arrêtes incidentes à x est pair.

2) si x est le point de départ, même argument.(⇐) Preuve par réccurence

1) Trivial pour le cas d’un graphe à un sommet.2) On suppose que G est un graphe tel que :

a) tous les sommets ont un ordre pairb) Si G′ un sous-graphe de G, (G′ ⊂ G) et tous les sommets de G′ sont d’ordre

pair alors G′ admet un circuit eulérien.Comme G est connexe et tous les sommets sont d’ordre pair alors G n’est pas unarbre donc il existe un ou des cycles. Soit C un cycle dans G, on considère G\C,c’est-à-dire G\AC 6

G\C =⋃Gi Gi connexe

L’ordre de chaque sommet de Gi est pair. Donc tous les Gi ont des circuits eulériens.Donc : G a un circuit eulérien car G = ⋃

Gi ∩ C. Pour le construire, on commencepar x1 ∈ C. Quitte à renuméroter les Gi, on prend x1 ∈ G1. On fait le circuit eulériensur G1 et on revient à x. On continue dans C vers x2 .Si x2 ∈ G1, on va sur x3, sinonsi x2 ∈ G2 on fait le circuit eulérien sur G2. Ainsi de suite...

2.8 Représentation matricielle pour les graphessDéfinition 2.8.1. Soit Γ = (S,A) un graphe orienté (boucles permises). La matrice d’incidencede Γ est :

a1 · · · ams1...sn

mij

tel que :

mij =

0 si si 6∈ aj1 si si ∈ aj2 si aj est une boucle pour si

Définition 2.8.2. Soit Γ = (S,A) un graphe non orienté (boucles permises). La matriced’adjacence de Γ est :

s1 · · · sns1...sn

mij

tel que :

mij =

0 si (si, sj) n’existe pas1 si (si, sj) existe

Exemple 2.8.1. Soit le graphe qui modélise les ponts de Koningsberg :6AC représente les arrêtes du sous-graphe C


Sa matrice d’adjacence est :

s1 s2 s3 s4s1s2s3s4

0 1 0 11 0 1 10 1 0 11 1 1 0

Exemple 2.8.2. Soit le graphe planaire d’un cube :

Sa matrice d’adjacence est :

M =

A B C D E F G HA 0 1 0 1 1 0 0 0B 1 0 1 0 0 1 0 0C 0 1 0 1 0 0 1 0D 1 0 1 0 0 0 0 1E 1 0 0 0 0 1 0 1F 0 1 0 0 1 0 1 0G 0 0 1 0 0 1 0 1H 0 0 0 1 1 0 1 0


On calcule ensuite M2 :

M2 =

A B C D E F G HA 3 0 2 0 0 2 0 2B 0 3 0 2 2 0 2 0C 2 0 3 0 0 2 0 2D 0 2 0 3 2 0 2 0E 0 2 0 2 3 0 2 0F 2 0 2 0 0 3 0 2G 0 2 0 2 2 0 3 0H 2 0 2 0 0 2 0 3

Ce qui nous amène à énoncer le théorème suivant :

Theorème 2.8.1. Si A est la matrice d’adjacence de Γ alors les coeficients aij de An est lenombre de chemin de longueur n qui lient si à sj.

Démonstration.m

(2)ij =

n∑k=1

mikmkj

On a que mikmkj = 1 ⇔ on a un chemin de longueur 2 qu lient si à sj. Par ce raisonnement,m

(2)ij = nombre de chemins de longueur 2 qui lie si avec sj. On veut montrer le théorème par

réccurence. Soit alors :

m(p+1)ij =

n∑k=1

m(p)ik mkj =

0 s’il n’existe pas de chemin de longueur p+ 1 qui lie si à sj1 sinon

On a ainsi que m(p+1)ij est le nombre total de chemin de longueur p+1 car m(p)

ik donne le nombrede chemins possibles de longueur p.

2.9 Rappel sur les graphes planairesTheorème 2.9.1 (Euler). Un graphe simple dessiné (ou plongé) sur le plan sans que les arrêtesse croisent est un graphe planaire :

s− a+ f = 2 7

Question 2.9.1. Peut-on dessiner sur la sphère un graphe simple avec 7 sommets et 16 arrêtessans que les arrêtes se croisent ?

Theorème 2.9.2. Si Γ est planaire, 2a ≥ 3f . On a alors K5 n’est pas planaire.

On a aussi que K3,3 n’est pas planaire. En faisant le graphe bipartit faces-arrêtes, on trouveles relations suivants :• a ≥ 3f• a ≤ 2a Pour K3,3, on a : 2a ≥ 4f

Pour notre problème sur la sphère (voir Question précédente) :• s = 7

7s : nombre de sommets, a : nombre d’arrêtes, f : nombre de faces, a : nombre d’arcs


• a = 16• f = 11

mais 32 ≥ 33. On peut comparer une sphère à un plan en projettant chaque point de la sphèrepar projection stéréographique.

Autre problème : plonger K3,3 sur le tore.

Chapitre 3

Groupes

3.1 Introduction sur les groupesSoit X un ensemble. On note Bĳ(X) l’ensemble des bĳections de X dans X. Si f et g sont

des bĳections alors f ◦ g est une bĳection.

Bĳ(X)× Bĳ(X)→ Bĳ(X)

avec les propriétés suivantes :1. Associativité :

f ◦ (g ◦ h) = (f ◦ g) ◦ h

2. Il existe une bĳection e (la bĳection identité) telle que :

f ◦ e = e ◦ f = f

3. Pour chaque bĳection f , il existe un inverse f−1 telle que :

f ◦ f−1 = f−1 ◦ f = e

Définition 3.1.1. Un ensemble G muni d’une application binaire ∗ : G × G → G avec lespropriétés 1., 2., 3..

Exemple 3.1.1 (Concept de symétrie). La propriété de symétrie est une propriété de groupe.Ici, on dit que le cercle est plus symétrique que le carré car il existe plus de transformationsqui préserve le cercle que de transformations qui préserve le carré.

Fig. 3.1 – On dit que le cercle est plus symétrique que le carré car il existe plus de transfor-mations qui préserve le cercle que de transformations qui préserve le carré.

31

32 Chapitre 3. Groupes

3.2 Actions de groupes - Exemples de groupesDéfinition 3.2.1. Une action d’un groupe G sur un ensemble X est une application :

µ : G×X → X

avec les propriétés suivantes :1. µ(e, x) = x∀x ∈ X2. µ(f, µ(g, x)) = µ(f ∗ g, x)

Exemple 3.2.1. Soit G les matrices inversibles n × n. On a que G est un groupe. Soit X lesmatrices n× n. Soit A ∈ G et B ∈ X. Soit µ une application telle que µ(A,B) = ABA−1. Onmontre alors que µ est une action de groupe :

1. évident2. µ(A1, µ(A2, B)) = µ(A1, A2BA

−12 ) = A1(A2BA

−12 )A−1

1 = A1A2B(A1A2)−1 = µ(A1.A2, B).

Exemple 3.2.2. Une autre action de groupes peut être les transformations euclidiennes duplan.

Exemple 3.2.3 (Exemples de groupes). 1. (Bĳ(X), ◦)2. Les matrices inversibles n× n sur R (ou C) avec le produit des matrices.3. (Z2,+) avec Z2 = {0, 1}

+ 0 10 0 11 1 0

table d’un groupe

4. (Zn,+) avec Zn = {0, 1, ..., n} = Z/ ∼ avec x ∼ y si x − y est divisible par n. On vamontrer en TD que Zn est un groupe.Exemple : Z5 : 3 + 4 = 2[5]

+ 0 1 2 3 40 0 1 2 3 41 1 2 3 4 02 2 3 4 0 13 3 4 0 1 24 4 0 1 2 3

(Zp\{0}, .), p premier.3.4 ≡ 2[5]2.4 ≡ 3[5]

On va montrer que ceci est un groupe. Mais il sera plus difficile de montrer l’existence del’élément inverse.

En effet, si p n’est pas premier, on n’a pas un groupe (Z4\{0} n’est pas un groupe car2.2 = 0). Par exemple, on recherche les inverses dans Z11 de 7, 5, 3 :

7.8 ≡ 1[11]

5.9 ≡ 1[11]3.4 ≡ 1[11]

Chapitre 3. Groupes 33

Theorème 3.2.1 (Petit théorème de Fermat). Soit a entier et p premier alors on a :

ap ≡ a[p]

Remarque. L’inverse de a ∈ Zp est ap−2.

Exemple 3.2.4. 311 ≡ 3[11]⇒ 310 ≡ 1[11]⇒ 3.39 ≡ 1[11]

Démonstration (Voir TD). Si a n’est pas premier avec p, comme p est un nombre premier,alors a est un multiplie de p, donc a et ap ont le même reste nul dans la division par p doncap ≡ a[p]. Supposons donc a premier avec p, donc a n’est pas multiple de p. Démontrons d’abordle résultat suivant :

(a+ 1)p ≡ ap + 1[p]

La formule du binôme de Newton donne :

(a+ 1)p =p∑k=0

Cpkak = ap + 1 +

p−1∑k+1

Cpkak

avec Cpk = p(p− 1)...(p− k + 1)k! donc k!Cpk = p(p− 1)...(p− k + 1). p divise k!Cpk or p premier

avec k! donc p divise Cpk . Donc p divise (a+ 1)p − ap − 1 par conséquent :

(a+ 1)p − ap − 1 ≡ 0[p]⇒ (a+ 1)p ≡ ap + 1[p]

Il ne suffit plus que démontrer par réccurence que ap ≡ a[p] en utilisant la propriété précédente.Supposons que l’on a : ap ≡ a[p] pour un certain rang a et démontrons que l’on a alors :(a+ 1)p ≡ a+ 1[p]. On a :

(a+ 1)p ≡ ap + 1p[p]

puisque p est premier. Or ap ≡ a(p) donc ap + 1 ≡ a+ 1[p] donc (a+ 1)p ≡ a+ 1[p].Démonstration. PGCD(a, p) = 1⇒ ∃(x, y) ∈ Z2, xa+ yp = 1⇒ xa ≡ 1[p]. Donc x = a−1

Les ensembles suivants sont des groupes :• (R,+), (R\{0}, .)• (Z,+)• (C,+), (C\{0}, .)• (Q,+), (Q\{0}, .)• Soit V un espace vectoriel alors (V,+) est un groupe

Les groupes de tresses.

La multiplication est définit comme suivant :

La tresse identité :


La tresse inverse :

Démonstration. On peut voir ces dessins comme un groupe. Voir TD

Définition 3.2.2 (Orbite). Si x ∈ X, l’orbite de x (par rapport à l’actionà est l’ensemble :

{µ(g, x), g ∈ G}

Theorème 3.2.2. Deux orbites différentes sont disjointes. C’est-à-dire que si θ(x) ∩ θ(y) 6= ∅alors θ(x) = θ(y).

3.3 Sous-groupesDéfinition 3.3.1. H ⊂ G est un sous-groupe si et seulement si :

1. h1 ∗ h2 ∈ H si h1, h2 ∈ H2. h−1 ∈ H si h ∈ H.

Remarque. 1. eG ∈ H2. (H, ∗) est lui-même groupe.

Exemple 3.3.1. (G, ∗) = R,+), Q ⊂ R est un sous-groupe.• pq

+ mn∈ Q

• −mn∈ Q.

Exemple 3.3.2. (G, ∗) = GL(n,R) : matrices inversibles, n × n avec coefficients réels. H ={A ∈ GL(n,R), detA = 1} est un sous-groupe.

Définition 3.3.2 (Ordre d’un groupe). L’ordre d’un groupe est le nombre d’éléments dans legroupe. Soit G ce groupe alors on note Ord(G) l’ordre de G.

Theorème 3.3.1 (Théorème de Lagrange). L’ordre d’un sous-groupe divise l’ordre d’un groupe.

Rappel (Orbite). µ : G×X → X, orbite de x ∈ X : θ(x) = {µ(g, x) : g ⊂ G} ⊂ X.Si θ(x) ∩ θ(y) 6= ∅ alors θ(x) = θ(y).

Notation. H < G : H est un sous-groupe de G.

Définition 3.3.3. Si H < G, on a l’action :

H ×G→ G(h× g) 7→ h ∗ g

Démonstration (Théorème de Lagrange). (1) Les orbites de cette action ont toutes le mêmenombre d’éléments = card(H).


(2) Soit g ∈ G, θ(g) = {h× g, h ∈ H}. On trouve une bĳection entre θ(g) et H.

θ(g)→ Hf 7→ f ∗ g−1

⇒ card(θ(g)) = card(H). On a G =⋃g∈G

θ(g).

G :

g1 · · · · · · · · · · · · → θ(g1)g2 · · · · · · · · · · · · → θ(g2)... ...... ...gn · · · · · · · · · · · · → θ(gn)

,

θ(gi1)θ(gi2)...θ(gin)

disjoints

k⋃j=1

θ(gij) = G θ(gij) 6= θ(gin) si j 6= n

Or card(gi1) = card(H)

· · · · · · θ(gi1) · · · · · ·...

· · · · · · θ(gik) · · · · · ·︸︷︷︸card(H)

k

card(H)× k = card(G).

Application 3.3.1. Si Ord(G) = p premier et H < G⇒ H = {e} ou G.

3.4 Homomorphisme de groupesDéfinition 3.4.1. SOient (G, ∗) et (K, ◦) deux groupes, une application :

f : G→ K

est un homomorphisme si :1) f(g1 ∗ g2) = f(g1) ◦ f(g2)2) f(g−1) = (f(g))−1

Remarque. (1) + (2)⇒ f(eG) = eK

Définition 3.4.2. f : G→ K est un isomorphisme s’il est un homomorphisme bĳectif.

Remarque. Dans ce cas, l’application inverse :

K → G

est aussi un homomorphisme.


Exemple 3.4.1.

Z2 :0 1

0 0 11 1 0

G :a b

a a bb b a

Alors G est isomorphe à Z2 :

f : G→ Z(a, b) 7→ (0, 1)

est un isomorphisme.

Exemple 3.4.2. f : G→ K homomorphisme.

Ker f : {g ∈ G, f(g) = eK}

Proposition 3.4.1. Si f : G→ K homomorphisme :• Ker f < G• Im f < K

Démonstration. 1. Ker f < G. Soient g1, g2 ∈ Ker f :

f(g1 ∗ g2) = f(g1) ◦ f(g2) = eK ◦ eK = eK

f(g−11 ) = f(g1)−1 = e−1

K = eK

2. Im f < K : k1, k2 ∈ Im f ⇒ ∃g1, g2 ∈ G, f(g1) = k1 et f(g2) = k2.

k1 ∗ k2 = f(g1 ∗ g2) = f(g1) ◦ f(g2)

k ∈ Im f ⇒ ∃g ∈ G, f(g) = k

k−1 = f(g)−1 = f(g−1)

Application 3.4.1. Si Ord(G) = p premier et

f : G→ K homomorphisme

Que peut-on dire sur f ?1. f est une injection.2. f envoie tout G sur eK .

Proposition 3.4.2. f : G→ K homomorphisme. Ker f = {eG} ⇔ f est injective.

Démonstration. Si f est injective, la préimage (ensemble des antécédents) de eK a tout auplus un élément. Mais eG est un antécédent alors Ker f = {eG}.

Supposons que Ker f = {eG} et f(g1) = f(g2). Il faut prouver que g1 = g2.

f(g1) ◦ f(g2)−1 = eK = f(g1) ◦ f(g2)−1 = f(g1 ∗ g−12 )

⇒ g1 ∗ g−12 = eG ⇒ g1 = g2.

Proposition 3.4.3. H < G, f : G → K homomorphisme. L’image de H par f = {f(h), h ∈H} est un sous-groupe de K.


Exemple 3.4.3.

Z22 :

+ (0, 0) (1, 0) (0, 1) (1, 1)(0, 0) (0, 0) (1, 0) (0, 1) (1, 1)(1, 0) (1, 0) (0, 0) (1, 1) (0, 1)(0, 1) (0, 1) (1, 1) (0, 0) (1, 0)(1, 1) (1, 1) (0, 1) (1, 0) (0, 0)

Z4 :

+ 0 1 2 30 0 1 2 31 1 2 3 02 2 3 0 13 3 0 1 2

Z22 n’est pas isomorphe à Z4 car il n’existe pas de sous-groupe d’ordre 2 pour Z4.

Définition 3.4.3. Soit G un groupe, g ∈ G, < g >= {gk, k ∈ Z} ⊂ G. < g > est unsous-groupe (commutatif) engendré par G.

Notation. Ord(< g >) = ordre de l’élément g.Démonstration. On peut voir gk comme g ◦ g ◦ ... ◦ g︸︷︷︸

k fois

. Donc :

– gk − gm = gk+m ∈< g >– (gk)−1 = g−k ∈< g >.

3.5 Groupe quotient

3.5.1 Quotient d’un espace vectorielDéfinition 3.5.1. Soit V un espace vectoriel et W < V un sous-espace. Soient ~x, ~y ∈ V , on ditque ~x ∼ ~y ⇔ ~x−~y ∈ W . L’idée est d’associer une relation d’équivalence dans V au sous-espaceW .

Fig. 3.2 – x ∼ y

Notation. Classe d’équivalence de x : [x] = x+W

Proposition 3.5.1. On peut munir l’espace V/W = V/ ∼ d’une structure d’espace vectorielde façon naturelle.

Définition 3.5.2. Soit ~x ∈ V et λ ∈ K alors :

λ[~x] := [λ~x]


Démonstration. Soit ~w ∈ W , il faut vérifier que λ[~x + ~w](= λ[~x]) = [λ~x + λw](= [λ~x]). Orλ~w ∈ W donc on a bien l’égalité.

Définition 3.5.3. Soient ~x, ~y ∈ V , on a ainsi :

[~x] + [~y] = [~x+ ~y]

Démonstration. On monte que ([~x + ~y] =)[~x + ~w1] + [~y + ~w2] = [~x + ~w1 + ~y + ~w2] avec~w1, ~w2 ∈ W . Mais ~w1 + ~w2 ∈ W donc l’égalité est vérifiée.

Proposition 3.5.2. On peut vérifier que V/W = V/ ∼ a une propriété d’espace vectoriel.

3.5.2 Quotient de groupesDéfinition 3.5.4. Soit (G, ∗) un groupe et H < G. On note g1 ∗ g2 si g−1

2 ∗ g1 ∈ H.

Démonstration. 1. g ∼ g car g−1 ∗ g = e ∈ H2. g1 ∼ g2 ⇒ g2 ∼ g1 ? Si g1 ∼ g2 alors g−1

2 ∗ g1 ∈ H mais (g−12 ∗ g1︸︷︷︸∈H

)−1

︸︷︷︸∈H

= g−11 ∗ g2︸︷︷︸∈H

3. g1 ∼ g2 et g2 ∼ g3 ⇒ g1 ∼ g3 ? Si on note a = g−12 ∗ g1 ∈ H et b = g−1

3 ∗ g2 ∈ H alorsb︸︷︷︸∈H

∗ a︸︷︷︸∈H︸︷︷︸

∈H

= g−13 ∗ g2 ∗ g−1

2 ∗ g1 = g−13 ∗ g1 ∈ H.

Notation. [g] = gH car g−12 ∗ g1 = h ∈ H ⇔ g1 = g2h.

Définition 3.5.5. On appelle G/ ∼= G/H classe latérale.

Définition 3.5.6. H < G est un sous-groupe distingué (ou sous-groupe normal (in english :normal subgroup)) si ∀g ∈ G et ∀h ∈ H, g−1hg ∈ H.

Remarque. Si (G, ∗) est un groupe commutatif (ou abélien) alors tout sous-groupe de G estdistingué.

Exemple 3.5.1. Z < R est un sous-groupe distingué.

Notation. H C G : H est un sous-groupe distingué.

Exemple 3.5.2. Soit G = S3 (groupes de 3-permutations) et H < G tel que :

H ={e =

(1 2 31 2 3

), h =

(1 2 32 1 3

)}

ON montre que H 6C G. On a que ∀g ∈ G, g−1 ∗ e ∗ g=e ∗ g−1 ∗ g = e ∈ H mais si on prend :

g =(

1 2 32 3 1

)g−1

(1 2 33 1 2

)

g−1 ∗ h ∗ g =(

1 2 33 1 2

)(1 2 32 1 3

)(1 2 32 3 1

)=(

1 2 31 3 2

)6∈ H

Remarque. Pour montrer qu’un sous-groupe est distingué, on n’uitlise pas la Définition 3.5.6,on verra des théorèmes particuliers.


Proposition 3.5.3. Si (G, ∗) groupe et H C G, on peut munir G/H d’une structure de groupede façon naturelle. Cela veut dire que si g1, g2 ∈ G alors :

[g1] ◦ [g2] = [g1 ∗ g2]

Démonstration. Si h1, h2 ∈ H :

|g1 ∗ h1](= [g1]) ◦ [g2 ∗ h2](= [g2]) = [g1 ∗ h1 ∗ g2 ∗ h2] ?= [g1 ∗ g2]

Il faut vérifier qu’il existe h ∈ H tel que

g1 ∗ g2 ∗ h = g1 ∗ h1 ∗ g2 ∗ h2 (3.1)

D’après la Définition 3.5.6, on a que H C G si ∀g ∈ G,∀h ∈ H, on a g−1hg = h′

g−1hg = gh′ ⇔ hg = gh′

(3.1) = g1 ∗ g2 ∗ h′1 ∗ h2 = g1 ∗ g2 ∗ hOn a donc vérifier que l’opération de la Proposition 3.5.3 est bien définie. On montre en suiteles propriétés de groupe :

1. ([g1] ◦ [g2]) ◦ [g3] = [g1 ∗ g2] ◦ [g3] = [(g1 ∗ g2) ∗ g3] = [g1 ∗ (g2 ∗ g3)] = [g1] ◦ ([g2] ◦ [g3])2. [e] ◦ [g] = [e ∗ g] = [g] et [g] ◦ [e] = [g ∗ e] = [g]3. [g]−1 = [g−1] ? [g]−1 ◦ [g] = [g−1] ◦ [g] = [g−1 ∗ g] = [e].

Theorème 3.5.4. H < G est distingué si et seulement si il est le noyau d’un homomorphismede groupes :

f : G→ K

Ker f = {g ∈ G | f(g) = eK}

Démonstration. A) Soit f : G → K un homomorphisme et H := Ker f = {g ∈ G | f(g) =eK}1) On montre alors que H est un sous-groupe : c’est-à-dire si h1, h2 ∈ H, i lfaut montrer

que h1 ∗ h2 ∈ H et que h−1 ∈ H.

f(h1 ∗ h2) = f(h1) ∗ f(h2) = eK ∗ eK = eK

Donc h1 ∗ h2 ∈ Ker f = H et :

f(h−1) = f(h)−1 = e−1K = eK

Donc h−1 ∈ H. Donc H < G.2) H est distingué : soit

g ∈ G, h ∈ H f(g−1 ∗ h ∗ h) = f(g−1) ∗ f(h) ∗ f(g) = f(g−1) ∗ eK ∗ f(g)= eK ∗ f(g−1) ∗ f(g) = eK

B) Soit H C G, K = G/H alors il existe une application :

f : G → G/Hg 7→ [g]

On vérifie que f est un homomorphisme est que Ker f = H.


1) f(g1 ∗ g2) ?= f(g1) ◦ f(g2)

f(g1 ∗ g2) = [g1 ∗ g2] = [g1] ◦ [g2] = f(g1) ◦ f(g2)

f(g−1) ?= f(g)−1

f(g−1) = [g−1] = [g]−1 = f(g)−1

2) Ker f = {g | f(g) = eK}. Cela veut dire que [g] = [e]. Mais e ∼ g si et seulement sig−1e ∈ H ⇔ g−1 ∈ H ⇒ g ∈ H.

Exemple 3.5.3. Soit B3 le groupe de 3-tresses et S3 le groupe de 3-permutations alors :

f : B3 → S3

est un homomorphisme et :

Ker f = groupe de tresses colorée

Fig. 3.3 – Exemple d’opérations dans B3 le groupe de 3-tresses

Exemple 3.5.4. Soit H < G, on appelle indice de H (dans G), le nombre de classes latérales.

Exemple 3.5.5. (G, ∗) groupe, S ⊂ G sous-enseble. On dit que S engendre G si :1. Le plus petit sous-groupe de G contient S.2. Le sous-groupe fermé par tous les éléments g1 ◦ ... ◦ gn ou gi ou g−1

i ∈ S.1. et 2. sont équivalents.

3.6 Homomorphismes non-triviauxPour répondre à la question : "Quand est-ce que deux groupes sont isomorphismes ?", il faut

classifier les groupes et remarquer des propriétés sur le groupeoù il faut trouver son isomorphe.

Groupes cycliques Les groupes cycliques sont les groupes (Zn,+) = {0, ..., n − 1} dontl’addition des éléments se fait modulo n.

Proposition 3.6.1. Soit (G,+) un groupe d’ordre n, G est isomorphe à Zn si et seulement siil contient un élément d’ordre n.

Si g ∈ G est d’ordre n, l’application :

e 7→ 0, g 7→ 1, g2 7→ 2

ou plus généralement,∀k ∈ 1, ..., n− 1, gk 7→ k


Proposition 3.6.2. Si Ord(G) = 4, G est isomorphe à Z4 ou à Z2 × Z2

Démonstration. On applique le théorème de Lagrange sur l’ordre d’un élément d’un groupe.Soit il existe un élément d’ordre 4 donc G serait isomorphe à Z4 ou sinon d’ordre 2 (isomorpheà Z2 × Z2).Proposition 3.6.3. Si Ord(G) est un nombre premier ⇒ G est cyclique.

Si f : G→ H est un isomorphisme et g ∈ G d’ordre n alors on peut montrer que f(g) ∈ Hest d’ordre n.Définition 3.6.1. L’homomorphisme trivial entre deux groupes G et H est l’application quienvoie tous les éléments de G sur eH .

Existe-il un homomorphisme non trivial entre :1) Z4 → Z6

2) Z4 → Z5

3) Z4 → S3

4) Z6 → S6

5) S3 → Z6

1) Z4 −→fZ6 : il existe un homomorphisme non-trivial. On prend l’élément 1 dans Z4, il est

d’ordre 4. On cherche alors des éléments d’ordre 1, 2 ou 4 dans Z6. Il n’existe pas deséléments d’ordre 4 dans Z6. Si on prend un élément d’ordre 1, on a un homomorphismetrivial. Soit un élément d’ordre 2 dans Z6 (cela correspond au 3 car 3 + 3 = 0). On a alorsl’homomorphisme non-trivial suivant :

f :

0→ 01→ 32→ 03→ 3

et on vérifie que f(a+ b) = f(a) + f(b).Question 3.6.1. Existe-il un homomorphisme injectif de Z4 à Z6 ?

2) Z4 → Z5. Si g ∈ Z4, g4 = e ⇒ f(g)4 = e mais le seul élément de Z5 qui vérifie cela, est 0.f(g) = 0. Tout est envoyé sur 0 donc l’homomorphisme est trivial.Proposition 3.6.4. Il existe un homomorphisme non-trivial entre Za → Zb si PGCD(a, b) 6=1.

3) Z6 → S3


On peut vérifier que f est un homomorphisme.

Documents

M211 : Mathématiques discrètes