29 - Vocabulaire des graphes

1 - Vocabulaire commun des cours de NSI

⇩ ⇧ ⤊

Les graphes sont des objets mathématiques très utilisés, notamment en informatique.

Ils se prêtent très bien à la modélisation d'un nombre important de problèmes, notamment ceux impliquant de grands nombres de relations entre différentes entités :

• Relations sociales : relations entre des individus
• Réseaux routiers : relations entre des croisements (carrefours, ronds-points, échangeurs d'autoroute)
• Réseaux Internet : relations entre des routeurs
• Plan du Web : relations entre les sites Web (liens)
• Automates : relations entre les états de l'automate
• Bases de données : relation entre les tables.
• Gestion de projets : relation entre les différentes parties du projet
• ...

2 - Graphe non orienté et graphe orienté

⇩ ⇧ ⤊

1 - Généralités sur les graphes

Un graphe G est constitué :

• d’un ensemble fini S de points appelés sommets.

• les sommets des graphes sont l'équivalent des noeuds des arbres : ils ont une étiquette et des données rattachées.
• Sur l'exemple, les étiquettes des sommets sont a, b, c, d, e et f.
• De façon plus formelle, on peut définir l'ensemble S de cete façon :  S = {a, b, c, d, e, f} 
S étant un ensemble de sommets, les sommets sont nécessairement tous distincts.
• d’un ensemble fini A de relations nommés soit arêtes, soit arcs, qui relient deux sommets qu'on nomme les extrémités.
• Les arêtes sont les relations d'un graphe non orienté.

• Les arcs sont les relations d'un graphe orienté.

• Un graphe est connexe lorsqu'on peut atteindre n'importe quel sommet depuis n'importe quel sommet.

Le graphe G non orienté ci-dessus est connexe.

Le graphe G orienté ci-dessus n'est pas connexe car partant de f ou de e on ne peut pas atteindre n'importe quel autre sommet.

• Un graphe est donc bien une structure relationnelle car il renseigne sur les relations entre ces sommets. On utilise parfois une notation mathématique montrant qu'un graphe est un couple composé de l'ensemble S des sommets et de l'ensemble A des relations entre les sommets :

G = (S, A)

2 - Graphes non orientés

Si le graphe est non-orienté, la relation entre deux sommets se nomme une arête

• L'arête a-b permet de se déplacer aussi bien de a vers b que de b vers a
• Dans un graphe simple non orienté (définition donné plus loin), on représente une arête a-b comme un ensemble {a,b} pour indiquer {a,b} est bien équivalent à {b,a}.
• L'ensemble S des arêtes du graphe de l'exemple est un ensemble d'ensembles :

S = { {a,b}, (a,c), {b,c} {a,d}, {d,f}, {d,e} }

• des sommets reliés par une arête sont dits adjacents ou voisins

Sur le graphe de l'exemple, les sommets a et b sont adjacents. Par contre, a et e ne sont pas adjacents.

• des arêtes menant au même sommet sont dites adjacentes

Sur le graphe de l'exemple {a,b} et {b,c} sont deux arêtes adjacentes car les deux mènent à un sommet commun c.

• Boucle : IMPOSSIBLE de façon rigoureuse dans un graphe simple non-orienté.
• Il s'agit d'une sorte d'arête partant d'un sommet et revenant directement à ce sommet.

• Cela n'est pas possible rigoureusement dans un graphe non orienté car il faudrait écrire {b,b} pour décrire la boucle. Or, un même élément ne peut apparaître deux fois dans un ensemble.
• Un graphe non orienté contenant une boucle est donc une variante d'un graphe non orienté qui ne respecte pas exactement les notations vues ci-dessus.
• Arêtes multiples : IMPOSSIBLE dans un graphe simple non orienté.
• Il s'agit de plusieurs arêtes ayant les mêmes extrémités et permettant donc de passer d'un sommet à l'autre par plusieurs chemins directs.

• Sur l'exemple, a et d sont en relation à travers deux arêtes distinctes. Cela pourrait schématiser deux salles reliées par deux portes différentes.
• Cela n'est pas possible dans un graphe simple non orienté puisqu'on ne décrit une arête que par ses extrémités ({a,d} par exemple). Il faudrait ici écrire E = { ... {a,d},{a,d} ... }. Or, on ne peut pas placer deux fois une même élément dans un ensemble.
• Définition : graphe simple non orienté
• Il s'agit d'un graphe non orienté qui ne possède ni boucle, ni arêtes multiples.
• En NSI,graphe non orienté signifie de façon implicite graphe simple non orienté.

3 - Graphe orienté

Si le graphe est orienté, la relation entre deux sommets se nomme un arc (moyen mnémotechnique : il y a une flèche, arc et flèche).

• il existe un "sens de circulation" : il est possible qu'on puisse aller de a vers b sans pouvoir aller de b vers a (typique de la rue à sens unique)
• on représente un arc avec la notation (a,d) pour indiquer a vers d. S'agissant d'un couple (un 2-uplet), l'arc (a,d) est différent de l'arc (d,a).

• Boucle : possible avec un graphe orienté
• Il s'agit d'un arc partant d'un sommet et revenant directement au même sommet.

• Les boucles sont possibles dans un graphe simple orienté car on peut écrire le couple (b, b) par exemple.
• Arcs multiples : IMPOSSIBLE dans un graphe simple orienté
• Il s'agit de plusieurs arcs ayant la même extrémité initiale et la même extrémité finale permettant donc de passer d'un sommet à l'autre par plusieurs chemins directs.

• Sur l'exemple, on voit qu'il existe deux "arêtes multiples" permettant d'aller de a vers d.
• Cela n'est pas possible dans un graphe simple puisqu'on peut voir qu'il faudrait utiliser une notation de ce type pour décrire l'ensemble des arcs (or un ensemble ne peut pas contenir deux fois le même élément)

A = {... (a,d),(a,d) ...}

• Les arcs multiples ne seront pas étudiés cette année.
• Définition : Graphe simple orienté
• Il s'agit d'un graphe orienté pouvant contenir des boucles mais pas d'arcs multiples.

• Notez bien ici que les deux arcs entre a et d ne sont pas les mêmes : nous avons (a,d) et (d,a). Il ne s'agit donc pas d'arcs multiples.

3 - Chemin

⇩ ⇧ ⤊

L'étude du cheminement dans un graphe est fondamentale et définir clairement le vocabulaire lié permet de catégoriser facilement le problème à résoudre.

4 - Cheminement dans le graphe orienté

• Chemin : un parcours du graphe suivant une suite précise de sommets adjacents et d'arcs adjacents.
• Exemple : d-(d-a)-a-(a,b)-b-(b,c)-c.
  Dans un graphe simple, on peut donc décrire ce chemin comme
• une suite d'arcs : (d-a)-(a,b)-(b,c)
• une suite de sommets : d-a-b-c



• Boucle : circuit constitué d'un seul arc qui part d'un sommet et y revient.
• Cycle
• Chemin comportant plus d'un arc et dont le sommet d'arrivée est le sommet de départ (on part de A et on revient à A).
• Si le "cycle" ne comporte qu'un arc, on parlera plutôt de boucle.
• Exemple : (d-a)-(a,b)-(b,c)-(c,a)-(a,d) par exemple.



• Acyclique.
• Un graphe orienté qui ne possède pas de cycle simple est dit acyclique.
• Chemin simple
• Définition : un chemin simple est un cheminement où on emprunte un arc donné qu'une fois au maximum.
• Le chemin et le cycle précédent sont bien des chemins simples.

Cliquez sur l'image pour lancer l'animation

Lors d'un chemin simple, on ferme donc progressivement l'accès futur des arcs utilisés.

• Un chemin simple passant par tous les arcs d'un graphe donné est un chemin eulérien. On notera que dans un chemin eulérien on peut emprunter plusieurs fois un même sommet.
• Le chemin dabcad n'est pas un cycle eulérien puisqu'on n'emprunte pas tous les arcs disponibles.
• Chemin élémentaire
• Définition : un cheminement élémentaire est un cheminement qui ne passe qu'une seule fois par un sommet donné.
• Le chemin dabcad précédent n'est pas élémentaire puisqu'on passe plusieurs fois par le sommet a ou le sommet d.

Lors d'un chemin élémentaire, on ferme donc progressivement l'accès futur des sommets déjà visités.

• Un chemin élémentaire passant par tous les sommets d'un graphe donné est un chemin hamiltonien.

5 - Cheminement dans le graphe non orienté

On retrouve les mêmes définitions en remplaçant simplement les arcs par les arêtes. Mais vous allez voir que les chemins obtenus ne sont néanmoins pas les mêmes.

• Chemin : suite d'arêtes adjacentes successives.
• Activation des deux arcs équivalents à une arête
• Dans le cadre d'un chemin simple sur un graphe non orienté, l'utilisation d'une arête bloque ensuite l'accès aux deux arcs équivalents même si on décide de représenter le graphe non orienté par son graphe orienté "équivalent" ! Exemple sur le graphe ci-dessous où on pourrait se dire que représenter le graphe du bas comme un graphe orienté revient juste à remplacer chaque arête par deux arcs.

• Et bien non :

Si le graphe est non orienté, on bloque l'arête {a,b} ou les deux arcs équivalents (a,b) et (b,a).

Si le graphe était vraiment orienté, se déplacer de a vers b ne bloque que (a,b). On pourrait encore emprunter (b,a).

• Cycle
• Chemin (de plus d'une arête) dont les deux extrémités sont identiques (on part de A et on revient à A).



• Acyclique
• Un graphe non orienté qui ne possède pas de cycle est dit acyclique.
• Chemin simple :
• Définition : chemin où on emprunte une arête donnée une fois au maximum.



Lors d'un chemin simple, on ferme donc progressivement l'accès futur des arêtes utilisées. Le chemin dabca est un chemin simple.

• Un chemin simple passant par tous les arêtes d'un graphe donné est un chemin eulérien. On notera que dans un chemin eulérien on peut emprunter plusieurs fois un même sommet.
• Chemin élémentaire
• Définition : un cheminement élémentaire est un cheminement qui ne passe qu'une seule fois par un sommet donné.
• Le chemin dabca précédent n'est pas élémentaire puisqu'on passe plusieurs fois par le sommet a.

Lors d'un chemin élémentaire, on ferme donc progressivement l'accès futur des sommets déjà visités.

• Un chemin élémentaire passant par tous les sommets d'un graphe donné est un chemin hamiltonien.

4 - Traduction

⇩ ⇧ ⤊

5 - FAQ : vocabulaire plus détaillé

⇩ ⇧ ⤊

Attention, ces mots ne devraient normalement pas se trouver dans les sujets de NSI. Je ne les donne que pour que vous puissiez comprendre les documents trouvés sur le Web lors de vos recherches, notamment pour l'épreuve du grand oral.

Le vocabulaire associé aux deux types de graphes

Ordre d'un graphe ?

Degré d'un sommet ?