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.

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Exemple

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

Le zoom est accessible dans la version Premium.

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

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.

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Exemples

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

Le zoom est accessible dans la version Premium.

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

Le zoom est accessible dans la version Premium.

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

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.

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Exemples

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

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

Le zoom est accessible dans la version Premium.

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Définition

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

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Exemples

1. Un graphe connexe :

Le zoom est accessible dans la version Premium.

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

Le zoom est accessible dans la version Premium.

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Application et méthode - 4

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Énoncé

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

Le zoom est accessible dans la version Premium.

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

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.

Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.

Solution

Les sommets \text{A} et \text{B}, par exemple, ne sont pas adjacents donc ce graphe n'est pas complet.
La chaîne \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

p. 191

Une erreur sur la page ? Une idée à proposer ?

Nos manuels sont collaboratifs, n'hésitez pas à nous en faire part.

Oups, une coquille

j'ai une idée !

Nous préparons votre pageNous vous offrons 5 essais

Yolène

Émilie

Jean-Paul

Fatima

Sarah

Utilisation des cookies

Lors de votre navigation sur ce site, des cookies nécessaires au bon fonctionnement et exemptés de consentement sont déposés.