Leçon 1 sur 5
Graphes, sommets, arêtes et représentations
Je sais définir un graphe (orienté ou non), calculer des degrés, appliquer le lemme des poignées de main et représenter un graphe par un dessin, une matrice d'adjacence ou des listes d'adjacence.
- 1 h
- 4 exercices corrigés
- QCM de 5 questions
À la fin de la leçon, vous saurez :
- Définir graphe simple, multigraphe, graphe orienté, ordre et taille
- Calculer les degrés et démontrer le lemme des poignées de main
- Reconnaître les graphes complets, bipartis et les sous-graphes
- Passer d'une représentation à une autre (dessin, matrice d'adjacence, listes)
Avant de commencer : Ensembles, couples, sommes finies ; raisonnement par récurrence et par l'absurde.
1Je découvre
Une coopérative de transport veut relier six villes de Guinée par des lignes de minibus directes : Conakry, Kindia, Mamou, Labé, Kankan et Boké. Le responsable dessine sur une feuille six points et trace un trait entre deux villes chaque fois qu'une ligne directe existe. Peu importe la longueur réelle de la route ou la forme du trait : ce qui compte, c'est qui est relié à qui.
Il veut savoir : combien de lignes partent de chaque ville ? Peut-on organiser les lignes pour que chaque ville en ait exactement trois ? Comment enregistrer ces informations dans un tableur pour qu'un programme les exploite ?
Ce dessin de points et de traits est un graphe. La même structure sert à modéliser un réseau routier, un réseau électrique, des amitiés sur un réseau social ou des tâches qui dépendent les unes des autres.
Qu'est-ce qu'un graphe, comment le décrire et quelles propriétés simples peut-on démontrer sur ses degrés ?
2Je comprends
1. Définitions
Un graphe non orienté G = (S, A) est la donnée :
- d'un ensemble fini non vide S de sommets (ou nœuds) ;
- d'un ensemble A d'arêtes, chaque arête reliant deux sommets, notée {x, y} ou xy.
- L'ordre du graphe est le nombre de sommets n = |S| ; sa taille est le nombre d'arêtes m = |A|.
- Deux sommets reliés par une arête sont adjacents (ou voisins) ; l'arête est incidente à ces sommets.
- Une boucle relie un sommet à lui-même ; des arêtes multiples relient la même paire de sommets plusieurs fois.
- Un graphe simple n'a ni boucle ni arête multiple. Sinon, on parle de multigraphe. Sauf mention contraire, les graphes de ce cours sont simples.
Un graphe orienté est formé de sommets et d'arcs : un arc est un couple (x, y) allant de x (origine) vers y (extrémité). Exemple : des rues à sens unique dans le centre de Kankan.
2. Degrés et lemme des poignées de main
Le degré d'un sommet x, noté d(x), est le nombre d'arêtes incidentes à x (une boucle compte pour 2). Un sommet de degré 0 est isolé.
Lemme des poignées de main. Dans tout graphe non orienté,
Σx ∈ S d(x) = 2m.
Démonstration : chaque arête {x, y} est comptée exactement deux fois dans la somme des degrés, une fois dans d(x) et une fois dans d(y).
Corollaire. Dans tout graphe, le nombre de sommets de degré impair est pair.
Démonstration : la somme des degrés est paire ; la somme des degrés pairs est paire ; donc la somme des degrés impairs est paire, ce qui impose un nombre pair de termes impairs.
Application : peut-on organiser des lignes de minibus entre 5 villes pour que chaque ville ait exactement 3 lignes ? La somme des degrés serait 5 × 3 = 15, impaire : impossible.
Dans un graphe orienté, on distingue le degré sortant d^+(x) (arcs qui partent de x) et le degré entrant d^-(x) (arcs qui arrivent en x). On a :
Σx d^+(x) = Σx d^-(x) = m.
3. Familles de graphes à connaître
| Graphe | Définition | Nombre d'arêtes |
|---|---|---|
| Graphe complet Kn | tous les sommets sont deux à deux adjacents | n(n-1)2 |
| Chaîne (graphe chemin) Pn | n sommets alignés, reliés successivement | n - 1 |
| Cycle Cn (n ≥ 3) | n sommets reliés en boucle | n |
| Graphe biparti | S se partage en deux ensembles X et Y, chaque arête relie un sommet de X à un sommet de Y | variable |
| Biparti complet Kp,q | tout sommet de X (p sommets) est relié à tout sommet de Y (q sommets) | pq |
*Justification pour Kn* : chaque sommet a degré n - 1, donc Σ d(x) = n(n-1) = 2m.
Un graphe est régulier de degré k si tous ses sommets ont le même degré k. Kn est (n-1)-régulier ; Cn est 2-régulier.
Exemple de graphe biparti : des étudiants X et des cours Y, avec une arête quand l'étudiant suit le cours.
4. Sous-graphes
- Un sous-graphe de G s'obtient en gardant une partie des sommets et une partie des arêtes entre ces sommets.
- Un sous-graphe induit par un ensemble S' de sommets garde toutes les arêtes de G entre sommets de S'.
- Un graphe partiel garde tous les sommets mais seulement une partie des arêtes.
5. Représentations
Le dessin : utile pour comprendre, mais un même graphe peut avoir des dessins très différents. Deux graphes qui ne diffèrent que par le nom des sommets sont dits isomorphes.
La matrice d'adjacence : on numérote les sommets de 1 à n ; le coefficient aij vaut 1 si i et j sont adjacents, 0 sinon. Pour un graphe non orienté, la matrice est symétrique ; pour un graphe simple, sa diagonale est nulle ; la somme de la ligne i est le degré de i.
Exemple : sommets 1 = Conakry, 2 = Kindia, 3 = Mamou, 4 = Labé ; arêtes 12, 23, 34, 13.
| 1 | 2 | 3 | 4 | |
|---|---|---|---|---|
| 1 | 0 | 1 | 1 | 0 |
| 2 | 1 | 0 | 1 | 0 |
| 3 | 1 | 1 | 0 | 1 |
| 4 | 0 | 0 | 1 | 0 |
Degrés (sommes des lignes) : 2, 2, 3, 1 ; total 8 = 2 × 4 arêtes.
Les listes d'adjacence : pour chaque sommet, la liste de ses voisins.
1 : 2, 3
2 : 1, 3
3 : 1, 2, 4
4 : 3Comparaison. La matrice occupe n2 cases et permet de tester en une opération si deux sommets sont adjacents. Les listes occupent une place proportionnelle à n + m : elles sont préférables pour les grands graphes creux (peu d'arêtes), comme un réseau routier.
3Je retiens
Je retiens
Un graphe G = (S, A) : des sommets et des arêtes ; ordre n = nombre de sommets, taille m = nombre d'arêtes.
Graphe simple : ni boucle ni arête multiple ; graphe orienté : des arcs (couples).
Lemme des poignées de main : la somme des degrés vaut 2m ; le nombre de sommets de degré impair est pair.
Le graphe complet Kn a n(n−1)/2 arêtes ; le biparti complet K(p,q) en a pq ; le cycle Cn en a n.
Sous-graphe induit : toutes les arêtes entre les sommets gardés ; graphe partiel : tous les sommets, une partie des arêtes.
Matrice d'adjacence : symétrique pour un graphe non orienté, somme de la ligne = degré.
Listes d'adjacence : plus économiques pour les grands graphes creux.
4Erreurs fréquentes
- Oublier qu'une boucle compte pour 2 dans le degré.
- Écrire que Kn a n(n−1) arêtes : chaque arête serait comptée deux fois ; la bonne valeur est n(n−1)/2.
- Croire qu'un graphe est défini par son dessin : deux dessins différents peuvent représenter le même graphe.
- Confondre sous-graphe induit et graphe partiel.
- Construire une matrice d'adjacence non symétrique pour un graphe non orienté.
5Je m’exerce
1Exercice 1
(Questions de cours) a) Énoncez et démontrez le lemme des poignées de main. b) Combien d'arêtes a K7 ? K3,4 ? C9 ?
Voir le corrigéCacher le corrigé
a) Énoncé : Σx ∈ S d(x) = 2m. Démonstration : chaque arête {x,y} contribue pour 1 au degré de x et pour 1 au degré de y, donc pour 2 à la somme ; la somme vaut donc 2m.
b) K7 : 7 × 62 = 21 arêtes. K3,4 : 3 × 4 = 12 arêtes. C9 : 9 arêtes.
2Exercice 2
Lors d'une réunion de 9 délégués d'amphithéâtre, chacun affirme avoir serré la main d'exactement 5 autres délégués. Est-ce possible ? Et si chacun en a serré exactement 4 ?
Voir le corrigéCacher le corrigé
On modélise : sommets = délégués, arêtes = poignées de main. Avec degré 5 pour les 9 sommets : somme des degrés = 45, impaire. Or elle doit valoir 2m, paire : impossible.
Avec degré 4 : somme = 36 = 2m, donc m = 18. Ce n'est pas interdit par le lemme ; et un tel graphe existe : placez les 9 délégués en cercle et reliez chacun à ses deux voisins de chaque côté (graphe 4-régulier). Possible.
3Exercice 3
On considère le graphe de sommets a, b, c, d, e et d'arêtes ab, ac, bc, cd, de, eb. a) Dessinez-le et donnez les degrés. b) Écrivez sa matrice d'adjacence et ses listes d'adjacence. c) Le graphe est-il biparti ? Justifiez.
Voir le corrigéCacher le corrigé
a) Degrés : d(a) = 2 (b, c), d(b) = 3 (a, c, e), d(c) = 3 (a, b, d), d(d) = 2 (c, e), d(e) = 2 (d, b). Somme = 12 = 2 × 6 : cohérent.
b) Matrice (ordre a, b, c, d, e) :
| a | b | c | d | e | |
|---|---|---|---|---|---|
| a | 0 | 1 | 1 | 0 | 0 |
| b | 1 | 0 | 1 | 0 | 1 |
| c | 1 | 1 | 0 | 1 | 0 |
| d | 0 | 0 | 1 | 0 | 1 |
| e | 0 | 1 | 0 | 1 | 0 |
Listes : a : b, c ; b : a, c, e ; c : a, b, d ; d : c, e ; e : b, d.
c) Non : a, b, c forment un triangle. Dans un graphe biparti, deux sommets adjacents sont dans des parties différentes ; avec trois sommets deux à deux adjacents, deux d'entre eux seraient forcément dans la même partie. Contradiction.
4Exercice 4
(Type examen) a) Montrez que dans tout graphe simple d'ordre n ≥ 2, il existe deux sommets de même degré. b) Un graphe simple a 15 arêtes et tous ses sommets sont de degré 3. Combien a-t-il de sommets ? c) Un graphe simple d'ordre 6 peut-il avoir 16 arêtes ?
Voir le corrigéCacher le corrigé
a) Dans un graphe simple d'ordre n, les degrés possibles sont 0, 1, …, n-1, soit n valeurs. Mais 0 et n-1 ne peuvent pas apparaître ensemble : un sommet de degré n-1 est relié à tous les autres, donc aucun n'est isolé. Les n sommets prennent donc leurs degrés parmi au plus n - 1 valeurs. Par le principe des tiroirs, deux sommets ont le même degré.
b) Σ d(x) = 3n = 2 × 15 = 30, donc n = 10 sommets.
c) Un graphe simple d'ordre 6 a au plus 6 × 52 = 15 arêtes (graphe complet K6). 16 arêtes est donc impossible.
Cherchez d’abord seul, sur votre cahier, puis ouvrez le corrigé pour comparer.
6Je vérifie
Choisissez une réponse pour chaque question : la correction s’affiche aussitôt.
Karamö, votre enseignant
Il a lu cette leçon. Posez-lui votre question : il vous répond ici.
Connectez-vous pour poser vos questions à Karamö.
Avec un compte Kharandi gratuit, vous cochez les leçons terminées et vous suivez votre progression, cours par cours.