M211: Mathématiques Discrètes

Université des Sciences et Technologies de Lille
U.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 3
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Relation d’équivalence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Cardinalité . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.1 Ensembles finies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.3.2 Ensembles infinis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Résumé sur la combinatoire (Voir Feuille TD) . . . . . . . . . . . . . . . . . . . 7
1.5 Bĳections et groupes de permutations . . . . . . . . . . . . . . . . . . . . . . . . 8
1.5.1 Représentations des permutations . . . . . . . . . . . . . . . . . . . . . . 8
2 Graphes et arbres 9
2.1 Introduction des graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.2 Premières définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.3 Exemples de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.4 Etude de graphes planaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4.1 Démonstration du théorème d’Euler . . . . . . . . . . . . . . . . . . . . . 15
2.4.2 Quelques astuces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.5 Homomorphismes de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.5.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.5.2 Lien entre groupes et graphes . . . . . . . . . . . . . . . . . . . . . . . . 20
2.5.3 Lien entre graphes et groupes . . . . . . . . . . . . . . . . . . . . . . . . 22
2.6 [TD] Modélisation de jeux combinatoires . . . . . . . . . . . . . . . . . . . . . . 23
2.6.1 Taquin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.7 Chemins dans un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
2.8 Représentation matricielle pour les graphess . . . . . . . . . . . . . . . . . . . . 27
2.9 Rappel sur les graphes planaires . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3 Groupes 31
3.1 Introduction sur les groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 Actions de groupes - Exemples de groupes . . . . . . . . . . . . . . . . . . . . . 32
3.3 Sous-groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.4 Homomorphisme de groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.5 Groupe quotient . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.5.1 Quotient d’un espace vectoriel . . . . . . . . . . . . . . . . . . . . . . . . 37
3.5.2 Quotient de groupes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.6 Homomorphismes non-triviaux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40
2
Chapitre 1
Ensembles
1.1 Introduction
Paradoxe 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, il
n’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 un

sous-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’équivalence

Dé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) = vrai
2. r(a, b) = vrai ⇒ r(b, a) = vrai
3. 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 de
part de pizza et qui a pour but de récupérer de la nourriture en évitant les fantômes qui rodent
dans 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) si x = {−1, 1}


(1, y) ∼ (−1, −y)

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 de

l’extremité du rayon de X) alors X/ ∼= RP 2 est appelé plan projectif.
1.3 Cardinalité
1.3.1 Ensembles finies
Dé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 alors
g(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) = 2n si n > 0
f :n→
f (n) = 2|n| + 1 si n ≤ 0
Exemple 1.3.3. Q+ . On peut voir cette ensemble comme un tableau infini :

1 2 3
1 1 1
···
1 2 3 4
2 2 2 2
···
1 2 3 4
3 3 3 3
···
.. .. .. ..
. . . .
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 infinis

Exemple 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 · · · (L1 )
a41 a42 a43 a44 · · ·
...
On construit une autre suite d’éléments (aii )i∈N tel que :


1 si aii = 0
aii =
0 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, a11 a12 ...a1n ...
0, a21 a22 ...a2n ...

0, a31 a32 ...a3n ...
Mais on ne veut pas qu’à partir d’un certain rang les aij soient égaux.
0, a11 a12 a13 ...a1n ...
0, a21 a22 a23 ...a2n ...

0, a31 a32 a33 ...a3n ...
Si : 
a
ii =9 aii = 0
aii 6= 9 aii = aii + 1
0, a11 a22 a33 a44 ... 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 injection
Y ,→ 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 les
hommes. On va construire une fonction telle qu’un homme d’un pays à un fils dans un autre.
On note : 
A∞ : généalogie infinie


en Allemagne : AA : généalogie finie en Allemagne



AF : généalogie finie en France


: généalogie infinie
F∞
en France : FA : généalogie finie en Allemagne



FF : 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∞ = ∅ F A

 ∩ F∞ = ∅

A∞ ∩ AF = ∅ et F∞ ∩ FF = ∅

 

AA ∩ AF = ∅ 
FA ∩ FF = ∅
Soit f : F → A et g : A → F , on a :

f

 : F∞ → A∞ bĳective
f : FF → AF bĳective → bĳection



g : AA → FA bĳective
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é vers
l’intervalle.
1

t → t,
2
s : (0, x1 x2 x3 , ...; 0, y1 y2 y3 ...) 7→ (0, x1 y1 x2 y2 ...)
Par exemple s(0, 1; 0, 1) → (0, 11).
Démonstration. On montre que s est injectif. Si (0, x1 y1 x2 y2 x3 y3 ...) = (0, x01 y10 x02 y20 ...) alors
(0, x1 x2 ...; 0, y1 y2 ...) = (0, x01 x02 ; 0, y10 y20 ).
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 Cnk = (n)
k!
k
= n!
(n−k)!k!
.
n
5. Le nombre de tous les sous-ensembles de X est 2 .
n
6. (a + b)n = Cnk an−k bk .
X
k=0
k−1
7. Cnk = Cn−1 k
+ Cn−1 avec Cnn = Cn0 = 1.
1.5 Bĳections et groupes de permutations

Définition 1.5.1. Soit X un ensemble tel que card(X) = n alors on note Bĳ(X) l’ensemble
de 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 permutations

1. !
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 3 1 2 3
1 2 3 2 1 3
! !
1 2 3 1 2 3
3 2 1 1 3 2
! !
1 2 3 1 2 3
2 3 1 3 1 2
Il y a 6 éléments dans S3 .
2. Représentation d’un produit :
! ! !
1 2 3 1 2 3 1 2 3
=
3 2 1 3 1 2 2 1 3
−→
! ! !
1 2 3 1 2 3 1 2 3
=
3 1 2 3 2 1 1 3 2
−→
! ! !
1 2 3 1 2 3 1 2 3
=
1 3 2 3 1 2 3 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 graphes

Exemple 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
2 fonctions
ω:A→S
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
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. On
peut 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 sommet
donné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) si
a 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éfinitions

Définition 2.2.1. Soit S un ensemble des sommets et A un ensemble d’arrêtes et f : A → S ×S
alors 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 graphes

Exemple 2.3.1 (Ponts de Koningsberg). Peut-on faie une promenade où on passerait par les
7 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 seule
fois.
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 chemin
eulé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 seule
fois.
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 de
faç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.
1
Le 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ésente
x 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 un
chemin.
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 planaires

Dans cette section, tous les graphes sont connexes et simples.
2.4.1 Démonstration du théorème d’Euler

Rappel (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 astuces

1. 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 :

2
c’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 ce
sommet.
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 ≥ 6s
2) 2a ≥ 4f ⇒ 4a ≥ 6f (20 )
On addition (1) + (20 ) :
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 à un
sommet, on peut le colorier avec 6 couleurs. On suppose pour un graphe planaire à n sommets
qu’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 les
couleurs c1 , c2 , c3 , c4 , c5 (au pire) donc on peut choisir c6 .
3
a = 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 de
graphes 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 de
suite !
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) + vZr3 q, v = qZr3 (q, v) + vq = q 2 + 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) + v 2 Zr4 (q, v)
= q 2 + vq + vq 2 + v 2 q + v(q 2 + vq) + v 2 (Zr6 (q, v) + vZr6 (q, v)) = (1 + 2v)(q 2 + vq) + v 2 q + v 3 q
Theorème 2.4.8. Si k ∈ N alors ZΓ (k, −1) est le nombre de façons de colorier Γ avec k
couleurs.
Remarque. S’il n’y a pas d’arrêtes et on a n sommets :
ZΓ (q, −1) = q n
Dans ce cas, le théorème est trivialement vérifié.
2.5 Homomorphismes de graphes

2.5.1 Généralités
Exemple 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 ) = α1
f (s2 ) = σ g(a2 ) = α2
f (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 −
→ (s1 , s2 ) −−→ (σ1 , σ2 )
i1 f ×f
a1 →
−
g
(α1 ) −
→ (α1 , α2 )
i2
Pour a2 :
a2 −
→ (s2 , s3 ) −−→ (σ1 , σ2 )
i1 f ×f
a2 →
− α2 −
→ (σ1 , σ2 )
g i2
Pour a3 :
a3 −
→ (s1 , s3 ) −−→ (σ1 , σ2 )
i1 f ×f
a3 →
− α1 −
→ (σ1 , σ2 )
g i2
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 et
arrê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 alors
les graphes (non-orientés) sont isomorphes.
Exemple 2.5.2. Le graphe d’un cube est isomorphe à sa représentation planaire.

4
c’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 milieu
du diagramme.
2.5.2 Lien entre groupes et graphes

Dé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 (s )
2 = s3





f (s3 ) = s4


f (s4 ) = s1
et g : A → A définie par : 


g(a1 ) = a2

g(a )
2 = 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) est
un groupe.
Remarque. On peut écrire la définition d’homomorphisme de groupes avec des diagrammes
commutatifs.
Dans le diagramme, on a : f (g1 ∗ g2 ) = f (g1 ) ◦ f (g2 ). On a aussi f (eG ) = eH et le diagramme

commute.
Démonstration (Cas orienté). Soit (S, A) un graphe, (f1 , g1 ), (f2 , g2 ) deux automorphismes
c’est-à-dire : )
f1 : S → S
bĳections
f2 : S → S
)
g1 : A → A
bĳections
g2 : A → A
et :
sont deux diagrammes commutatifs. On considère (f1 ◦ f2 , g1 ◦ g2 ). il faut vérifier que f1 ◦ f2 est
une bĳection g1 ◦ g2 est une bĳection (immédiat car une composition d’une bĳection est une
bĳ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

5
Définition 2.5.5. Soit G un groupe et soit X ⊂ G un sous-ensemble. X engendre G si tout
g ∈ 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 ensembles
gé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}
5
On 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 Cayley
associé à (G, X).
2.6 [TD] Modélisation de jeux combinatoires

2.6.1 Taquin
Au 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 permutation

de 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 graphe

Définition 2.7.1. Une promenade sur un graphe Γ est une séquence (a1 s1 , a2 s2 , ..., , an sn ) 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), on
est 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 un
chemin.
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 seul
chemin.
Démonstration. Il y a au moins un chemin (connexité). On suppose qu’il y a deux chemins
qui relient deux sommets distincts quelconque sur un arbre. Soient P , P 0 ces deux chemins
reliant x et y. Soit u un sommet dans les chemins P et P 0 tel que les successeurs par P et
P 0 sont différents. Soit v le premier sommet après u tel que les successeurs par P et P 0 sont
identiques. 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 7
ponts ?
Définition 2.7.5. Un circuit eulérien sur un graphe Γ est un circuit qui passe par chaque
arrête une fois.
Définition 2.7.6. La matrice d’incidence associé à un graphe Γ est la matrice :
a
 1
a2 · · · ak 
..
s1  . . . . 
s2  .. 
 . . . . 
..  
. · · · · · · mij · · ·
 
sn

.. 
. . . .
avec : 
0

 si si 6∈ aj
mij =

1 si si ∈ aj


2 si aj est une boucle sur si
Définition 2.7.7. On définit l’ordre de si :
k
X
Ord(si ) = mij
j=1
Theorème 2.7.2 (Euler).

n
X
Ord(si ) = 2a
i=1
avec a = le nombre d’arrêtes.

X
Démonstration. Les deux quantités sont égales à mij .
i,j
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. X
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 de

chaque sommet est pair.
Démonstration. (⇒) 1) si x n’est pas un point de départ, on compte +1 si on arrive

en x et −1 si on part de x. A la fin du circuit, le compteur doit être égal à 0 ⇒ le
nombre 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 pair
b) Si G0 un sous-graphe de G, (G0 ⊂ G) et tous les sommets de G0 sont d’ordre
pair alors G0 admet un circuit eulérien.
Comme G est connexe et tous les sommets sont d’ordre pair alors G n’est pas un
arbre 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 commence
S
par x1 ∈ C. Quitte à renuméroter les Gi , on prend x1 ∈ G1 . On fait le circuit eulérien

sur G1 et on revient à x. On continue dans C vers x2 .Si x2 ∈ G1 , on va sur x3 , sinon
si x2 ∈ G2 on fait le circuit eulérien sur G2 . Ainsi de suite...
2.8 Représentation matricielle pour les graphess

Définition 2.8.1. Soit Γ = (S, A) un graphe orienté (boucles permises). La matrice d’incidence
de Γ est :
a1 · · · am
s1
 
.. 
.  mij 

sn
tel que : 
0

 si si 6∈ aj
mij =

1 si si ∈ aj


2 si aj est une boucle pour si
Définition 2.8.2. Soit Γ = (S, A) un graphe non orienté (boucles permises). La matrice
d’adjacence de Γ est :
s1 · · · sn
s1
 
.. 
.  mij 

sn
tel que : 
0
si (si , sj ) n’existe pas
mij = 
1 si (si , sj ) existe
Exemple 2.8.1. Soit le graphe qui modélise les ponts de Koningsberg :
6
AC représente les arrêtes du sous-graphe C
Sa matrice d’adjacence est :
s s s s
 1 2 3 4
s1 0 1 0 1
s2 1 0 1 1
 
s3 0 1 0 1
 
s4 1 1 1 0
Exemple 2.8.2. Soit le graphe planaire d’un cube :
Sa matrice d’adjacence est :
A B C D E F G H
A 0 1 0 1 1 0 0 0
B 1 0 1 0 0 1 0 0
C 0 1 0 1 0 0 1 0
M= D 1 0 1 0 0 0 0 1
E 1 0 0 0 0 1 0 1
F 0 1 0 0 1 0 1 0
G 0 0 1 0 0 1 0 1
H 0 0 0 1 1 0 1 0
On calcule ensuite M 2 :
A B C D E F G H
A 3 0 2 0 0 2 0 2
B 0 3 0 2 2 0 2 0
C 2 0 3 0 0 2 0 2
M2 = D 0 2 0 3 2 0 2 0
E 0 2 0 2 3 0 2 0
F 2 0 2 0 0 3 0 2
G 0 2 0 2 2 0 3 0
H 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 le
nombre de chemin de longueur n qui lient si à sj .
Démonstration. n
(2) X
mij = mik mkj
k=1
On a que mik mkj = 1 ⇔ on a un chemin de longueur 2 qu lient si à sj . Par ce raisonnement,

(2)
mij = nombre de chemins de longueur 2 qui lie si avec sj . On veut montrer le théorème par
réccurence. Soit alors :

n 0
(p+1) X (p) s’il n’existe pas de chemin de longueur p + 1 qui lie si à sj
mij = mik mkj =
1 sinon
k=1
(p+1) (p)
On a ainsi que mij est le nombre total de chemin de longueur p + 1 car mik donne le nombre
de chemins possibles de longueur p.
2.9 Rappel sur les graphes planaires

Theorème 2.9.1 (Euler). Un graphe simple dessiné (ou plongé) sur le plan sans que les arrêtes
se croisent est un graphe planaire :
7
s−a+f =2
Question 2.9.1. Peut-on dessiner sur la sphère un graphe simple avec 7 sommets et 16 arrêtes
sans 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 trouve
les 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
7
s : 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ère
par projection stéréographique.
Autre problème : plonger K3,3 sur le tore.

Chapitre 3
Groupes
3.1 Introduction sur les groupes

Soit 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 les

proprié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 transformations
qui 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 groupes

Dé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 ∈ X
2. µ(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 les
matrices n × n. Soit A ∈ G et B ∈ X. Soit µ une application telle que µ(A, B) = ABA−1 . On
montre alors que µ est une action de groupe :
1. évident
2. µ(A1 , µ(A2 , B)) = µ(A1 , A2 BA−1 −1 −1
2 ) = A1 (A2 BA2 )A1 = A1 A2 B(A1 A2 )
−1
= µ(A1 .A2 , B).
Exemple 3.2.2. Une autre action de groupes peut être les transformations euclidiennes du
plan.
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 1
0 0 1 table d’un groupe
1 1 0
4. (Zn , +) avec Zn = {0, 1, ..., n} = Z/ ∼ avec x ∼ y si x − y est divisible par n. On va
montrer en TD que Zn est un groupe.
Exemple : Z5 : 3 + 4 = 2[5]
+ 0 1 2 3 4
0 0 1 2 3 4
1 1 2 3 4 0
2 2 3 4 0 1
3 3 4 0 1 2
4 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 de
l’élément inverse.
En effet, si p n’est pas premier, on n’a pas un groupe (Z4 \{0} n’est pas un groupe car
2.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 donc
ap ≡ a[p]. Supposons donc a premier avec p, donc a n’est pas multiple de p. Démontrons d’abord
le résultat suivant :
(a + 1)p ≡ ap + 1[p]
La formule du binôme de Newton donne :
p p−1
(a + 1)p = Ckp ak = ap + 1 + Ckp ak
X X
k=0 k+1
p(p − 1)...(p − k + 1)
avec Ckp = donc k!Ckp = p(p − 1)...(p − k + 1). p divise k!Ckp or p premier
k! p
avec k! donc p divise Ck . 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-groupes
Définition 3.3.1. H ⊂ G est un sous-groupe si et seulement si :
1. h1 ∗ h2 ∈ H si h1 , h2 ∈ H
2. h−1 ∈ H si h ∈ H.
Remarque. 1. eG ∈ H
2. (H, ∗) est lui-même groupe.
Exemple 3.3.1. (G, ∗) = R, +), Q ⊂ R est un sous-groupe.

• pq + m
n
∈Q
• −m n
∈ Q.
Exemple 3.3.2. (G, ∗) = GL(n, R) : matrices inversibles, n × n avec coefficients réels. H =

{A ∈ GL(n, R), det A = 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 le
groupe. 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ême
nombre d’éléments = card(H).
(2) Soit g ∈ G, θ(g) = {h × g, h ∈ H}. On trouve une bĳection entre θ(g) et H.
θ(g) → H
f 7→ f ∗ g −1
[
⇒ card(θ(g)) = card(H). On a G = θ(g).
g∈G
g1 · · · · · · · · · · · · → θ(g1 ) 
θ(gi1 )

g2 · · · · · · · · · · · · → θ(g2 ) 


.. .. θ(gi )

2
G: . . , . disjoints
.. .. 
 .
.
. .



θ(g )

in
gn · · · · · · · · · · · · → θ(gn )
k
[
θ(gij ) = G θ(gij ) 6= θ(gin ) si j 6= n
j=1
Or card(gi1 ) = card(H) 




······ θ(gi1 ) · · · · · ·




..

. k

······ θ(gik ) ······ 



| {z }



card(H)
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 groupes

Dé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.
0 1 a b
Z2 : 0 0 1 G: a a b
1 1 0 b b a
Alors G est isomorphe à Z2 :
G→Z
f:
(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 (g1−1 ) = 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 au

plus 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 ∗ g2−1 )
⇒ g1 ∗ g2−1 = 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.
+ (0, 0) (1, 0) (0, 1) (1, 1) + 0 1 2 3
(0, 0) (0, 0) (1, 0) (0, 1) (1, 1) 0 0 1 2 3
Z22 : (1, 0) (1, 0) (0, 0) (1, 1) (0, 1) Z4 : 1 1 2 3 0
(0, 1) (0, 1) (1, 1) (0, 0) (1, 0) 2 2 3 0 1
(1, 1) (1, 1) (0, 1) (1, 0) (0, 0) 3 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 >= {g k , k ∈ Z} ⊂ G. < g > est un
sous-groupe (commutatif) engendré par G.
Notation. Ord(< g >) = ordre de l’élément g.
Démonstration. On peut voir g k comme g ◦ g ◦ ... ◦ g . Donc :
| {z }
k fois
– g k − g m = g k+m ∈< g >
– (g k )−1 = g −k ∈< g >.
3.5 Groupe quotient

3.5.1 Quotient d’un espace vectoriel
Définition 3.5.1. Soit V un espace vectoriel et W < V un sous-espace. Soient ~x, ~y ∈ V , on dit
que ~x ∼ ~y ⇔ ~x − ~y ∈ W . L’idée est d’associer une relation d’équivalence dans V au sous-espace
W.
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 vectoriel
de 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 donc on a bien l’égalité.
λw
Définition 3.5.3. Soient ~x, ~y ∈ V , on a ainsi :
[~x] + [~y ] = [~x + ~y ]
Démonstration. On monte que ([~x + ~y ] =)[~x + w~1 ] + [~y + w~2 ] = [~x + w~1 + ~y + w~2 ] avec
w~1 , w~2 ∈ W . Mais w~1 + w~2 ∈ 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 groupes

Définition 3.5.4. Soit (G, ∗) un groupe et H < G. On note g1 ∗ g2 si g2−1 ∗ g1 ∈ H.
Démonstration. 1. g ∼ g car g −1 ∗ g = e ∈ H
2. g1 ∼ g2 ⇒ g2 ∼ g1 ? Si g1 ∼ g2 alors g2−1 ∗ g1 ∈ H mais (g2−1 ∗ g1 )−1 = g1−1 ∗ g2
| {z } | {z }
∈H ∈H
| {z }
∈H
3. g1 ∼ g2 et g2 ∼ g3 ⇒ g1 ∼ g3 ? Si on note a = g2−1 ∗ g1 ∈ H et b = g3−1 ∗ g2 ∈ H alors

a = g3−1 ∗ g2 ∗ g2−1 ∗ g1 = g3−1 ∗ g1 ∈ H.
b ∗ |{z}
|{z}
∈H ∈H
| {z }
∈H
Notation. [g] = gH car g2−1 ∗ g1 = h ∈ H ⇔ g1 = g2 h.

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 −1 hg ∈ H.
Remarque. Si (G, ∗) est un groupe commutatif (ou abélien) alors tout sous-groupe de G est
distingué.
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 :
( ! !)
1 2 3 1 2 3
H= e= ,h =
1 2 3 2 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 :

! !
1 2 3 −1 1 2 3
g= g
2 3 1 3 1 2
! ! ! !
−1 1 2 3 1 2 3 1 2 3 1 2 3
g ∗h∗g = = 6∈ H
3 1 2 2 1 3 2 3 1 1 3 2
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 groupe
de 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 −1 hg = h0
g −1 hg = gh0 ⇔ hg = gh0
(3.1) = g1 ∗ g2 ∗ h01 ∗ h2 = g1 ∗ g2 ∗ h
On a donc vérifier que l’opération de la Proposition 3.5.3 est bien définie. On montre en suite
les 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 homomorphisme
de 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−1

K = 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/H
g 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 si
g −1 e ∈ 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 gi−1 ∈ S.
1. et 2. sont équivalents.
3.6 Homomorphismes non-triviaux

Pour 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} dont
l’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 si

il contient un élément d’ordre n.
Si g ∈ G est d’ordre n, l’application :
e 7→ 0, g 7→ 1, g 2 7→ 2
ou plus généralement,
∀k ∈ 1, ..., n − 1, g k 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) ∈ H
est d’ordre n.
Définition 3.6.1. L’homomorphisme trivial entre deux groupes G et H est l’application qui
envoie 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 →
− Z6 : il existe un homomorphisme non-trivial. On prend l’élément 1 dans Z4 , il est
f
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 homomorphisme
trivial. Soit un élément d’ordre 2 dans Z6 (cela correspond au 3 car 3 + 3 = 0). On a alors
l’homomorphisme non-trivial suivant :
0→0
1→3
f:
2→0
3→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 , g 4 = 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.

M211: Mathématiques Discrètes

Transféré par

Droits d'auteur :

Formats disponibles

M211: Mathématiques Discrètes

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

M211: Mathématiques Discrètes

Transféré par

Droits d'auteur :

Formats disponibles

Université des Sciences et Technologies de Lille

U.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

Définition 1.1.1. On note X ⊃ Y si Y est un sous-ensemble de X et X % Y si Y est un

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

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

Définition 1.1.4. f : X → Y est une application de X dans Y . Elle est :

1.2 Relation d’équivalence

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

∼ est appelée alors relation d’équivalene. En terme de booléens :

Fig. 1.1 – Ensemble et ensemble quotient pour PacMan

Fig. 1.2 – Ensemble et ensemble quotient pour le cercle

Exemple 1.2.3. Soit X : [−1, 1] × [−1, 1] et soit ∼ tel que :

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 de

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 +

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 :

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

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 infinis

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

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

0, a11 a12 ...a1n ...

0, a21 a22 ...a2n ...

0, a11 a12 a13 ...a1n ...

0, a21 a22 a23 ...a2n ...

Définition 1.3.3. SI X ,→ Y alors card(X) ≤ card(Y ).

1.4 Résumé sur la combinatoire (Voir Feuille TD)

1.5 Bĳections et groupes de permutations

1.5.1 Représentations des permutations

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

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

2.1 Introduction des graphes

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

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)

2.2 Premières définitions

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

Remarque. Selon cette définition :

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 graphes

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

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

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

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

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 :

Exemple 2.3.5. Soit S un ensemble d’examens et A étudiants en mathématiques. Soit f :