Graphes : définitions, propriétés
- Fiche de cours
- Quiz
- Profs en ligne
- Videos
- Application mobile
Objectif(s)
Connaître le vocabulaire des graphes : sommets, sommets
adjacents, arêtes, degré d’un sommet,
ordre d’un graphe, chaîne, longueur d’une
chaîne, graphe complet, graphe connexe, chaîne
eulérienne, matrice d’adjacence associée
à un graphe.
Toutes les définitions sont à connaître.
Certaines seront plus souvent utilisées dans le cours
« Recherche du plus court chemin » ou dans le
cours « Graphe probabiliste à 2 ou 3 sommets
».
1. Définitions
► Graphe, sommet, arête
► Boucle
► Sommets adjacents
► Graphe simple
► Degré d’un sommet
Le nombre d’arêtes étant 4, la somme est bien le double du nombre total d’arêtes.
• Pour le graphe 2, le degré de chaque sommet est A(2), B(2), C(3) car la boucle correspond à deux liaisons, D(0), E(2), F(1), la somme vaut 2 + 2 + 3 + 0 + 2 + 1 = 10.
Le nombre d’arêtes étant 5, la somme est bien le double du nombre total d’arêtes.
Dans ces cas simples, le calcul n’a que peu d’intérêt. Avec des graphes plus compliqués, cela peut être utile.
► Ordre d’un graphe
► Sous graphe
► Graphe complet
Le graphe 1 n’est pas complet car par exemple B et C ne sont pas reliés.
► Graphe orienté
Attention, rien n’oblige à « circuler » sur le graphe (aller obligatoirement d’un point à un autre).
► Matrice associée à un graphe d’ordre n
Pour graphe 4, on numérote les sommets dans l’ordre alphabétique, 1 pour A, 2 pour B, 3 pour C et 4 pour D.
Pour la 1ère ligne, A n’est pas en relation avec lui-même (pas de boucle), donc 1ère ligne, 1ère colonne on met 0.
Pour les colonnes suivantes (toujours en 1ère ligne), le graphe est simple, complet et A est adjacent à chaque autre sommet une seule fois. D’où les 1 qui complètent la ligne.
Un graphe est un schéma contenant des
points nommés sommets, reliés ou non par
des segments appelés arêtes.
Graphe 1
|
A est un sommet, le segment [AB] est une
arête reliant A à B (ou B à
A). D est un sommet isolé, non relié à un autre sommet. |
► Boucle
Une boucle est une arête reliant deux fois
le même sommet.
Graphe 2
|
Dans graphe 2, C est muni d’une boucle. |
► Sommets adjacents
Deux sommets sont adjacents lorsqu’ils sont
reliés par une arête.
Dans l’exemple précédent (Graphe
2), A et B sont adjacents, A et E ne le sont pas.► Graphe simple
Un graphe est simple s’il ne comporte aucune
boucle et que deux arêtes ne relient jamais la
même paire de sommets.
Le graphe 1 est simple, le graphe 2 ne l’est
pas.► Degré d’un sommet
Le degré d’un sommet est égal
au nombre d’arêtes qui le relient aux autres
sommets.
Dans l’exemple précédent, A est
de degré 2, B de degré 2, D de degré
0.
Propriété :
La somme des degrés de tous les sommets d’un graphe est égal au double du nombre total d’arêtes.
• Pour le graphe 1, le degré de
chaque sommet est A(2), B(2), C(1), D(0), E(2), F(1), la
somme vaut 2 + 2 + 1 + 0 + 2 + 1 = 8.La somme des degrés de tous les sommets d’un graphe est égal au double du nombre total d’arêtes.
Le nombre d’arêtes étant 4, la somme est bien le double du nombre total d’arêtes.
• Pour le graphe 2, le degré de chaque sommet est A(2), B(2), C(3) car la boucle correspond à deux liaisons, D(0), E(2), F(1), la somme vaut 2 + 2 + 3 + 0 + 2 + 1 = 10.
Le nombre d’arêtes étant 5, la somme est bien le double du nombre total d’arêtes.
Dans ces cas simples, le calcul n’a que peu d’intérêt. Avec des graphes plus compliqués, cela peut être utile.
► Ordre d’un graphe
C’est le nombre total de sommets.
Les graphes 1 et 2 sont d’ordre 6.► Sous graphe
Un sous graphe d’un autre graphe est
un graphe composé de certains de ses sommets avec
toutes les arêtes qui les relient.
 Graphe 3 |
Graphe 3 est un sous graphe du graphe 2. |
► Graphe complet
Un graphe est complet si tous les sommets sont
adjacents les uns avec les autres.
Graphe 4
|
Ci-contre, graphe 4 est un graphe complet d’ordre 4. |
Le graphe 1 n’est pas complet car par exemple B et C ne sont pas reliés.
► Graphe orienté
Un graphe orienté est un graphe dont les
arêtes sont orientées. Elles ont une origine
et une extrémité. Elles ne peuvent
être parcourues que dans un sens.
Attention, rien n’oblige à « circuler » sur le graphe (aller obligatoirement d’un point à un autre).
► Matrice associée à un graphe d’ordre n
La matrice associée de n lignes et n
colonnes est la matrice où le terme à
l’intersection de la ie ligne et de la
je colonne est égal au nombre
d’arêtes reliant les sommets i et j.
Pour graphe 4, on numérote les sommets dans l’ordre alphabétique, 1 pour A, 2 pour B, 3 pour C et 4 pour D.
Pour la 1ère ligne, A n’est pas en relation avec lui-même (pas de boucle), donc 1ère ligne, 1ère colonne on met 0.
Pour les colonnes suivantes (toujours en 1ère ligne), le graphe est simple, complet et A est adjacent à chaque autre sommet une seule fois. D’où les 1 qui complètent la ligne.
2. Exemples d’utilisations
a. Les ponts de Königsberg
|
La ville de Königsberg (aujourd’hui
Kaliningrad en Russie) sur la rivière
Pregolia (Pregolya) comporte deux îles.
Sept ponts relient les îles entre elles ou
aux rives. Les habitants se posaient la question de savoir s’il existait une promenade permettant de passer une fois et une seule sur chaque pont pour revenir au point de départ. Euler résolut par la négative ce problème. La cause en est que de chaque île et de chaque rive partent un nombre impair de ponts. |
|
La modélisation de ce problème
(graphe ci-contre) a l’intérêt
de se généraliser, c'est l'un des
points de départ de la théorie des
graphes. Pour que l’on puisse faire une promenade ramenant le promeneur au point de départ, il faudrait que le nombre de ponts pour chaque île et chaque rive soit pair. Si on enlève la contrainte de revenir au point de départ, il faudrait que deux des sommets au plus (le départ et l’arrivée) aient un nombre impair de ponts. Le problème des sept ponts de Königsberg est l’exemple type de graphe eulérien. |
b. Le problème du voyageur de commerce
L'énoncé du problème du voyageur de
commerce est simple : étant donné n villes
(que l’on représentera par des points) et
les chemins (routes pouvant être uniques ou
multiples, affectées de longueurs ou non)
séparant chaque ville, trouver un chemin de
longueur totale minimale qui passe exactement une fois
(seulement) par chaque ville et revienne au point de
départ.
Pour 3 ou 4 villes c’est facile mais le total des possibilités peut être supérieur à 360 000 trajets différents pour 10 villes !
Pour le graphe ci-dessus, plusieurs chemins sont possibles.
• Par exemple : A - 3 - B - 2 - D - 4 - C - 5 - E - 4 - F - 3 - A, la longueur totale est égale à 21.
• Le plus court, il est possible de changer certaines parties du parcours sans en changer la longueur : A - 2 - D - 2 - B - 3 - C - 5 - E - 4 - F - 3 - A, la longueur totale est égale à 19.
Pour 3 ou 4 villes c’est facile mais le total des possibilités peut être supérieur à 360 000 trajets différents pour 10 villes !
Pour le graphe ci-dessus, plusieurs chemins sont possibles.
• Par exemple : A - 3 - B - 2 - D - 4 - C - 5 - E - 4 - F - 3 - A, la longueur totale est égale à 21.
• Le plus court, il est possible de changer certaines parties du parcours sans en changer la longueur : A - 2 - D - 2 - B - 3 - C - 5 - E - 4 - F - 3 - A, la longueur totale est égale à 19.
Comment as-tu trouvé ce cours ?
Évalue ce cours !
Vous avez obtenu75%de bonnes réponses !
Recevez l'intégralité des bonnes réponses ainsi que les rappels de cours associés :
Fiches de cours les plus recherchées
Mathématiques
Recherche du plus court chemin
Mathématiques
Graphe probabiliste à 2 ou 3 sommets
Mathématiques
Détermination de primitives
Mathématiques
Intervalles de fluctuation
Mathématiques
Prise de décision, estimation
Mathématiques
Suites numériques : limite finie ou infinie
Mathématiques
Suites numériques : limites et comparaison
Mathématiques
Suites numériques : opérations sur les limites
Mathématiques
Suites numériques : comportement à l'infini de (qn), avec q un réel.
Mathématiques
Suites numériques : suites majorées, minorées, bornées
Fermer
Accédez gratuitement à
