Chargement de l'audio en cours
Plus

Plus

2. Les graphes
P.183
Mode édition
Ajouter

Ajouter

Terminer

Terminer

COURS 2


2
Les graphes





Définitions
Un graphe est une représentation composée de sommets (des points) reliés par des arêtes (segments).
Un graphe orienté est un graphe dont les arêtes sont munies d’un sens de parcours.
L’ordre d’un graphe est le nombre de sommets de ce graphe.
Le degré d’un sommet est le nombre d’arêtes incidentes à ce sommet, sans tenir compte de leur éventuel sens de parcours.

Exemple

Le graphe ci‑contre est d’ordre 5.
Les sommets K\text{K} et L\text{L} sont de degré 3.
Les sommets M1\mathrm{M}_{1}, M2\mathrm{M}_{2} et M3\mathrm{M}_{3} sont de degré 2.

Graphe

Définitions
Deux sommets sont adjacents lorsqu’ils sont reliés par au moins une arête.
Un graphe est complet lorsque tous ses sommets sont deux à deux adjacents.

Exemples

1. Le graphe ci‑dessous est complet : tous ses sommets sont deux à deux adjacents.
graphe 1

2. Le graphe ci‑dessous n’est pas complet : les sommets A\text{A} et B\text{B}, par exemple, ne sont pas adjacents.
graphe 2

Définitions
Pour un graphe non orienté, une chaîne est une suite d’arêtes consécutives reliant deux sommets (éventuellement confondus).
La longueur d’une chaîne est le nombre d’arêtes la composant.
Pour un graphe orienté, un chemin est une suite d’arêtes consécutives reliant deux sommets (éventuellement confondus) en tenant compte du sens de parcours des arêtes.

Exemples
1. Sur le graphe ci-contre, A−E−I−G−H\mathrm{A}-\mathrm{E}-\mathrm{I}-\mathrm{G}-\mathrm{H} est une chaîne de longueur 4.

2. De même, A−C−B−F−D−C−A\mathrm{A}-\mathrm{C}-\mathrm{B}- \mathrm{F}-\mathrm{D}- \mathrm{C}- \mathrm{A} est une chaîne de longueur 6.

Graphe

Définition
Un graphe non orienté est connexe lorsque chaque couple de ses sommets peut être relié par une chaîne.

Exemples

1. Un graphe connexe :
Graphe 1

2. Un graphe non connexe : on ne peut pas relier R\text{R} et B\text{B} par une chaîne.
Graphe 2

Application et méthode - 4

Énoncé

On considère le graphe ci‑contre.
Le graphe est‑il complet ? Connexe ? Justifier les réponses.

Graphe

Solution


Les sommets A\text{A} et B\text{B}, par exemple, ne sont pas adjacents donc ce graphe n’est pas complet.
La chaîne A−C−D−E−G−B−F\mathrm{A}-\mathrm{C}-\mathrm{D}-\mathrm{E}-\mathrm{G}-\mathrm{B}-\mathrm{F} passe par tous les sommets donc ce graphe est connexe.

Pour s'entraîner : exercices 33 et 34 p. 191

Méthode

  • Le graphe est complet si chaque sommet est relié à tous les autres.
  • Le graphe est connexe si on peut trouver une chaîne passant par tous les sommets.


Utilisation des cookies
En poursuivant votre navigation sans modifier vos paramètres, vous acceptez l'utilisation des cookies permettant le bon fonctionnement du service.
Pour plus d’informations, cliquez ici.