Signaler un problème
S'inscrire et continuer à apprendre
Tu n'as pas encore de compte ? Créer un compte
Économise 38%
11,99 € / Mois
Économise 38%
7,42 € / Mois
Aperçu des chapitres
Objectifs d'apprentissage
Objectifs
Mathématiques
Mon livre
Mathématiques + expertes
Mathématiques
Résumé
Un graphe est un ensemble fini d’éléments (les points), appelé sommets, reliés entre eux par des arêtes (les segments).
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. |
| |
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é |
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.
| |
Graphe connexe. | Graphe non connexe. On peut par exemple construire une chaîne de longueur 2 de E à C. |
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 n×n.
Dans un graphe non orienté, la valeur du coefficient ai,j de la matrice est 1 si le sommet I est adjacent au sommet j. Sinon, le coefficient est 0.
| 010101010 | |
Dans un graphe orienté, la valeur du coefficient ai,j de la matrice est 1 si une arête part du sommet I (ligne) et va vers le sommet j (colonne). Sinon, le coefficient est 0.
| 001110100 | |
Note : Dans le cas d’un graphe non orienté, la matrice adjacente est symétrique, c’est-à-dire que le coefficient ai,j est toujours égal au coefficient aj,i. Cependant, dans un graphe orienté, il est possible que les deux coefficients ne soient pas égaux.
Un graphe est un ensemble fini d’éléments (les points), appelé sommets, reliés entre eux par des arêtes (les segments).
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. |
| |
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é |
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.
| |
Graphe connexe. | Graphe non connexe. On peut par exemple construire une chaîne de longueur 2 de E à C. |
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 n×n.
Dans un graphe non orienté, la valeur du coefficient ai,j de la matrice est 1 si le sommet I est adjacent au sommet j. Sinon, le coefficient est 0.
| 010101010 | |
Dans un graphe orienté, la valeur du coefficient ai,j de la matrice est 1 si une arête part du sommet I (ligne) et va vers le sommet j (colonne). Sinon, le coefficient est 0.
| 001110100 | |
Note : Dans le cas d’un graphe non orienté, la matrice adjacente est symétrique, c’est-à-dire que le coefficient ai,j est toujours égal au coefficient aj,i. Cependant, dans un graphe orienté, il est possible que les deux coefficients ne soient pas égaux.
FAQs
Question : Qu'est-ce qu'un graphe complet ?
Réponse : Un graphe est complet lorsque chacun de ses sommets est relié à tous les autres.
Question : Quel est le degré d'un sommet ?
Réponse : Le degré d’un sommet est le nombre d’arrêtes qui le relient aux autres sommets.
Question : Qu'est-ce qu'un graphe ?
Réponse : Un graphe est un ensemble fini d’éléments (les points), appelé sommets, reliés entre eux par des arêtes (les segments).
Théorie
Exercices
© 2020 – 2023 evulpo AG
Protection des données
Nous et des tiers, tels que nos partenaires publicitaires et nos prestataires de services, utilisons des cookies et des technologies similaires pour fournir nos services, aider à personnaliser le contenu et mesurer les annonces. En cliquant sur "Accepter les cookies" ou en autorisant uniquement le cookie nécessaire via "Seulement le nécessaire", tu acceptes cette pratique (pour en savoir plus, consulte notre Politique de confidentialité). Politique de confidentialité