Cours relativement hermétique : bien vouloir faire beaucoup d’exercices
Motivation :
Modéliser les interactions pouvant exister entre des personnes, des objets, des villes...
Situation problème :
La figure ci-dessous représente les relations d’amitié existant entre les élèves d’une classe : KENFACK, LOWE, POUWO, VIPAROU, MAGUE et ALINOUO.
Qui a le plus d’amis et qui est le solitaire de la classe?
- La théorie des graphes
- C’est la discipline mathématique et informatique qui étudie les graphes.
Cette théorie permet de représenter un ensemble complexe d’objets en exprimant les relations entre les éléments; Elle trouve ses applications dans tous les domaines liés à la notion de réseau (réseau social, réseau informatique, télécommunications, etc.)
I. Généralités sur les graphes
I.1 Notion de graphe
- Les graphes
- Ce sont des modèles abstraits de dessins de réseaux reliant des objets.
Ces modèles sont constitués par la donnée de sommets (aussi appelés nœuds ou points, en référence aux polyèdres), et d'arêtes (aussi appelées liens ou lignes) entre ces sommets ; ces arêtes sont parfois non-symétriques (graphes orientés) et sont appelées des flèches ou des arcs.
Un graphe fini \(G\) est constitué d’un ensemble fini \(V(G)\) dont les éléments sont appelés sommets et d’un ensemble \(E(G)\) disjoint de \(V(G)\) dont les éléments sont appelés arêtes, tels qu’à chaque arête \(a \in E(G)\) est associé une paire \(\{ u,v\} \) de sommets éléments de \(V(G)\). Le cas échéant, les sommets \(u\) et \(v\) sont appelés extrémités de \(a\).
Pour représenter graphiquement un graphe l’on représente les sommets par des points et les arêtes par des lignes (pas nécessairement droites) connectant les extrémités des arêtes.
La figure ci-dessus est une représentation graphique d’un graphe \(G\) avec :
• 1, 2, 3, 4, 5 et 6, les sommets;
• {1; 2}, {2; 3}, {3; 4} {3; 5} et {4; 5}, les arêtes.
I.2 Quelques définitions
- Ordre d’un graphe
- C’est le nombre de sommets de ce graphe.
Notre exemple précèdent a 6 sommets donc, il est d’ordre 6.
Deux sommets sont dits adjacents s’ils sont reliés par une arête.
Pour notre exemple précèdent, nous avons les sommets adjacents suivants : 1 et 2, 2 et 3, 3 et 4 3 et 5, 4 et 5
Un sommet est dit isolé lorsqu’aucune arête ne le relie aux autres sommets.
Pour notre exemple précèdent, 6 est un sommet isolé.
L'ordre d'un graphe |V| est son nombre de sommets.
La taille d'un graphe est |E|, son nombre d'arêtes.
Le degré ou la valence d'un sommet est le nombre d'arêtes incidentes à ce sommet, où une boucle compte double.
II. Les types de graphes
Un graphe est dit simple lorsque au plus une arête relie deux sommets et s’il n’y a pas de boucle sur un sommet. Dans le cas contraire on parle de multi-graphe.
Un graphe simple est dit complet si chaque sommet du graphe est relié à tous les autres sommets.
Un graphe est dit biparti si son ensemble de sommets peut être divisé en deux sous-ensembles disjoints \({S_1}\) et \({S_2}\) tels que chaque arête ait une extrémité dans \({S_1}\) et l'autre dans \({S_2}\).
Un graphe biparti permet notamment de représenter une relation binaire.
Un graphe orienté fini ou digraphe est un graphe dont les arêtes ont une orientation.
Elles sont alors représentées par des arcs en forme de flèche, tel que chaque arc est défini par une paire ordonnée de sommets.
- Une boucle
- C’est une arête d'un graphe ayant pour extrémités le même sommet.
Les boucles sont notamment interdites dans les graphes simples, mais elles sont autorisées dans les multigraphes.
III. Degré d’un sommet dans un graphe
Soit G un graphe, on appelle degré du sommet v et on note \(d(v)\), le nombre d’arêtes incidentes à ce sommet.
Une boucle sur un sommet compte double.
On appelle taille d’un graphe le nombre de ses arêtes.
Propriété (Lemme des poignées de mains)
Dans tout graphe G, la somme des degrés de tous les sommets est égale au double du nombre de ses arêtes.
\(\sum\limits_{v \in V(G)} {{d_G}(v) = } \) \(2\left| {E(G)} \right|\)
Où \(\left| {E(G)} \right|\) représente la taille du graphe ou encore le nombre de ses arêtes.
Conséquence : Dans un graphe simple G, le nombre de sommets de degré impair est pair.
La séquence de degré d’un graphe est la suite décroissante constituée des degrés de ses sommets.
Une suite décroissante d’entiers naturels est dite graphique s’il existe un graphe ayant cette suite pour séquence de degré.
Le lemme des poignées de mains reste valable pour les multigraphes avec boucles en convenant qu’une boucle contribue pour 2 dans le calcui du degré d’un sommet.
