Fiche de cours

Graphes : définitions, propriétés

Lycée > Terminale > Mathématiques > Graphes : définitions, propriétés

Fiche de cours
Quiz et exercices
Vidéos et podcasts

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

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.
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 i^e ligne et de la j^e 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.

146401

Évalue ce cours !

Note 4.1 / 5. Nombre de vote(s) : 134

Des quiz et exercices pour mieux assimiler sa leçon

La plateforme de soutien scolaire en ligne myMaxicours propose des quiz et exercices en accompagnement de chaque fiche de cours. Les exercices permettent de vérifier si la leçon est bien comprise ou s’il reste encore des notions à revoir.

S’abonner

Des exercices variés pour ne pas s’ennuyer

Les exercices se déclinent sous toutes leurs formes sur myMaxicours ! Selon la matière et la classe étudiées, retrouvez des dictées, des mots à relier ou encore des phrases à compléter, mais aussi des textes à trous et bien d’autres formats !

Dans les classes de primaire, l’accent est mis sur des exercices illustrés très ludiques pour motiver les plus jeunes.

S’abonner

Des quiz pour une évaluation en direct

Les quiz et exercices permettent d’avoir un retour immédiat sur la bonne compréhension du cours. Une fois toutes les réponses communiquées, le résultat s’affiche à l’écran et permet à l’élève de se situer immédiatement.

myMaxicours offre des solutions efficaces de révision grâce aux fiches de cours et aux exercices associés. L’élève se rassure pour le prochain examen en testant ses connaissances au préalable.

S’abonner

Des vidéos et des podcasts pour apprendre différemment

Certains élèves ont une mémoire visuelle quand d’autres ont plutôt une mémoire auditive. myMaxicours s’adapte à tous les enfants et adolescents pour leur proposer un apprentissage serein et efficace.

Découvrez de nombreuses vidéos et podcasts en complément des fiches de cours et des exercices pour une année scolaire au top !

S’abonner

Des podcasts pour les révisions

La plateforme de soutien scolaire en ligne myMaxicours propose des podcasts de révision pour toutes les classes à examen : troisième, première et terminale.

Les ados peuvent écouter les différents cours afin de mieux les mémoriser en préparation de leurs examens. Des fiches de cours de différentes matières sont disponibles en podcasts ainsi qu’une préparation au grand oral avec de nombreux conseils pratiques.

S’abonner

Des vidéos de cours pour comprendre en image

Des vidéos de cours illustrent les notions principales à retenir et complètent les fiches de cours. De quoi réviser sa prochaine évaluation ou son prochain examen en toute confiance !

S’abonner

Profs en ligne

Découvrez le soutien scolaire en ligne avec myMaxicours

Plongez dans l'univers de myMaxicours et découvrez une approche innovante du soutien scolaire en ligne, conçue pour captiver et éduquer les élèves de CP à la terminale. Notre plateforme se distingue par une riche sélection de contenus interactifs et ludiques, élaborés pour stimuler la concentration et la motivation à travers des parcours d'apprentissage adaptés à chaque tranche d'âge. Chez myMaxicours, nous croyons en une éducation où chaque élève trouve sa place, progresse à son rythme et développe sa confiance en soi dans un environnement bienveillant.

Profitez d'un accès direct à nos Profs en ligne pour une assistance personnalisée, ou explorez nos exercices et corrigés pour renforcer vos connaissances. Notre assistance scolaire en ligne est conçue pour vous accompagner à chaque étape de votre parcours éducatif, tandis que nos vidéos et fiches de cours offrent des explications claires et concises sur une multitude de sujets. Avec myMaxicours, avancez sereinement sur le chemin de la réussite scolaire, armé des meilleurs outils et du soutien de professionnels dédiés à votre épanouissement académique.

EXERCE-TOI EN T'ABONNANT