Mathématiques Expertes Terminale
Mes Pages
Nombres complexes
Ch. 1
Nombres complexes, point de vue algébrique
Ch. 2
Nombres complexes, point de vue géométrique
Arithmétique
Ch. 3
Divisibilité dans Z
Ch. 4
PGCD et applications
Ch. 5
Nombres premiers
Graphes et matrices
Ch. 6
Calcul matriciel et applications aux graphes
Ch. 7
Suites et matrices
Annexes
Cahier d'algorithmique et de programmation
Chapitre 6
Cours 2
Les graphes
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
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.
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.
Faites défiler pour voir la suite.
Exemple
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.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
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.
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.
Faites défiler pour voir la suite.
Exemples
1. Le graphe ci‑dessous est complet : tous ses sommets sont deux à deux adjacents.
2. Le graphe ci‑dessous n'est pas complet : les sommets \text{A} et \text{B}, par exemple, ne sont pas adjacents.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
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.
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.
Faites défiler pour voir la suite.
Exemples
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.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
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.
Faites défiler pour voir la suite.
Exemples
1. Un graphe connexe :
2. Un graphe non connexe : on ne peut
pas relier \text{R} et \text{B} par une chaîne.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
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.
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.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
- 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.
Faites défiler pour voir la suite.
Une erreur sur la page ? Une idée à proposer ?
Nos manuels sont collaboratifs, n'hésitez pas à nous en faire part.
j'ai une idée !
Oups, une coquille
