Matrices : graphes
Choisir une leçon
Mon livre
Select an option
Variables aléatoires
Suites
Calcul intégral
Primitive et équation différentielle
Dérivation
Vidéo Explicative
Résumés
Matrices : graphes
Graphes
Définition
Un graphe est un ensemble fini d’éléments (les points), appelé sommets, reliés entre eux par des arêtes (les segments).
Notions
ORDRE | L’ordre d’un graphe est son nombre de sommets. |
DEGRÉ | Le degré d’un sommet est le nombre d’arrêtes qui le relient aux autres sommets. |
ADJACENTS | Deux sommets sont adjacents s’ils sont reliés par une arête. |
COMPLET | Un graphe est complet lorsque chacun de ses sommets est relié à tous les autres. |
ORIENTÉ | Dans un graphe orienté, les arêtes ont un sens. On représente généralement un tel graphe avec des flèches sur les arêtes. |
Exemples
 |  |
| Graphe d’ordre 4. Le sommet A est de degré 2 et est adjacent aux sommets B et C. | Graphe complet d’ordre 5. |
 |  |
| Graphe orienté | Graphe non orienté |
Chaînes
Définition
Une suite d’arêtes consécutives forme une chaîne. Sa longueur est le nombre d’arêtes qui la composent. Si le sommet de départ est le même que celui d’arrivée, on dit que la chaîne est fermée.
S’il est possible de relier n’importe quelle paire de sommets du graphe par une chaîne, on dit que le graphe est connexe.
Exemples
 |  |
| Graphe connexe. | Graphe non connexe. On peut par exemple construire une chaîne de longueur 2 de E à C. |
Matrice d’adjacence
Chaque ligne et chaque colonne de la matrice d’adjacence représente un sommet du graphe. Pour un graphe d’ordre n, la matrice d’adjacence est une matrice carrée .
Dans un graphe non orienté, la valeur du coefficient de la matrice est 1 si le sommet est adjacent au sommet . Sinon, le coefficient est 0.
| |  |
Dans un graphe orienté, la valeur du coefficient de la matrice est 1 si une arête part du sommet (ligne) et va vers le sommet (colonne). Sinon, le coefficient est 0.
Exemple
| |  |
Note : Dans le cas d’un graphe non orienté, la matrice adjacente est symétrique, c’est-à-dire que le coefficient est toujours égal au coefficient . Cependant, dans un graphe orienté, il est possible que les deux coefficients ne soient pas égaux.
Questions fréquemment posées sur les crédits
Qu'est-ce qu'un graphe complet ?
Un graphe est complet lorsque chacun de ses sommets est relié à tous les autres.
Quel est le degré d'un sommet ?
Le degré d’un sommet est le nombre d’arrêtes qui le relient aux autres sommets.
Qu'est-ce qu'un graphe ?
Un graphe est un ensemble fini d’éléments (les points), appelé sommets, reliés entre eux par des arêtes (les segments).