Données Graphes Voc.

Identification

Infoforall

31 - Vocabulaire des graphes


Page qui reprend l'essentiel des notions à comprendre.

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
  • ...
Rappel : Vocabulaire vue dans l'activité précédente

Dans le rappel ci-dessous, les mots de vocabulaire à connaître pour l'épreuve sont surlignés. Les autres mots ne sont fournis qu'à titre de culture générale et de façon à comprendre certaines lectures que vous allez peut-être trouver sur le Web (lors de la préparation du Grand Oral par exemple).

Les graphes orientés et non orientés sont parfois munis d'un vocabulaire spécifique pour les distinguer : nous n'utiliserons pas ces termes ici. Voir la FAQ si vous rencontrez un terme "étrange" dans vos lectures.

Les termes à connaître sont :

  • Structure relationnelle
  • Graphe orienté et graphe non orienté
  • Sommet
  • Arc et Arête
  • Chemin
  • Cycle

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

Un graphe est constitué :

  • d’un ensemble fini S de points appelés sommets,
    • les sommes d'un graphe
    • ils 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} 
  • d’un ensemble fini A de relations qui relient deux sommets qu'on nomme les extrémités.
    • Les arêtes sont les relations d'un graphe non orienté.
    • les arêtes d'un graphe
    • Les arcs sont les relations d'un graphe orienté.
    • les arcs d'un graphe
  • 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 des deux ensembles précédents : G = (S, A)

2 - Graphes non orientés

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

les arêtes d'un graphe
  • on peut se déplacer aussi bien de a vers b que de b vers a
  • on peut représenter rigoureusement une arête a-b comme un ensemble {a,b} pour indiquer que l'ensemble {a,b} est bien équivalent à l'ensemble {b,a}
  • on représente néanmoins parfois une arête comme un couple (a,b), mais, pour un graphe non orienté, les relations sont symétriques : (a,b) = (b,a). Ce n'est pas le cas d'un couple (a,b) quelconque pour lequel (a,b) n'est pas nécessairement identique à (b,a).
  • des sommets reliés par une arête sont dits adjacents ou voisins (a et b par exemple).
  • des arêtes menant au même sommet sont dites adjacentes ( {a,b} et {b,c} ).
  • Boucle : il s'agit d'une sorte d'arête partant d'un sommet et revenant directement à ce sommet.
    • exemple de boucle
    • Cela n'est pas possible dans un graphe simple non orienté puisqu'on ne peut pas écrire {b,b} par exemple : 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 : 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.
    • exemple de double liaison
    • sur l'exemple, on voit qu'il existe deux "arêtes multiples" reliant les sommets a et d. Cela pourrait schématiser deux salles reliées par deux portes différentes.
    • Cela n'est pas possible dans un graphe simple puisqu'on ne décrit une arête qui par ses extrémités ({a,d} ici). Or, on ne peut pas placer deux fois cette arêt dans l'ensemble E des arêtes : E = { {a,d},{a,d} } n'est pas une notation correcte.
    • Ce type de graphes ne sera pas étudié cette année.
  • Graphe simple non orienté : il s'agit d'un graphe non orienté qui ne possède ni boucle, ni arêtes multiples.
    • exemple de graphe simple

3 - Graphe orienté

Si le graphe est orienté, la relation entre deux sommets se nomme un arc.

les arcs d'un graphe
  • 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 (ou 2-uplet), l'arc (a,d) est différent de l'arc (d,a).
  • exemple d'arc
  • Boucle : il s'agit d'un arc partant d'un sommet et revenant directement au même sommet.
    • exemple de boucle
    • Les boucles sont possibles dans un graphe simple orienté car on peut écrire le couple (b, b) par exemple.
  • Arcs multiples : 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.
    • exemple de double arc
    • 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 ne peut pas écrire la même arête (a,d) deux fois dans l'ensemble E des arcs : E = { (a,d),(a,d) } n'est pas une notation correcte.
    • Ils ne seront pas étudiés cette année.
  • Graphe simple orienté : il s'agit d'une graphe orienté pouvant contenir des boucles mais pas d'arcs multiples.
    • exemple de graphe simple orienté
    • 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.

4 - Cheminement dans le graphe

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.

Cheminement dans un graphe orienté

  • Chemin : un parcours suivant une suite précise de sommets et d'arcs adjacents.
    • Exemple : d-(d-a)-a-(a,b)-b-(b,c)-c.
      On peut donc également décrire ce chemin comme
      • une suite d'arcs : (d-a)-(a,b)-(b,c)
      • une suite de sommets : d-a-b-c
      exemple de chemin
      Cliquez sur l'image pour lancer l'animation du chemin
  • Boucle : circuit constitué d'un seul arc (on part de b et on revient à b en un coup par exemple).
    • exemple de bouclage
      Cliquez sur l'image pour lancer l'animation de la boucle
  • Cycle : chemin dont les deux extrémités sont identiques (on part de A et on revient à A). Remarque : 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.
    • exemple de circuit
      Cliquez sur l'image pour lancer l'animation du cycle
  • Simple : un cheminement est dit simple s'il ne passe qu'une seule fois par un arc donné.
    • Le chemin et le cycle précédent sont bien des cheminements simples.
    • Cliquez sur l'image pour lancer l'animation

        exemple de circuit simple
      Cliquez sur l'image pour lancer l'animation du cycle simple

      Lorsqu'on suit le principe de chemin simple, on voit donc qu'on active puis bloque progressivement l'utilisation des arcs utilisés.

    • Un graphe orienté qui ne possède pas de cycle simple est dit acyclique.

Cheminement dans un graphe non orienté

    On retrouve les mêmes définitions en remplaçant simplement les arcs par les arêtes : chemin, cycle (et événtuellement boucle).

  • Chemin : suite d'arêtes adjacentes successives.
    • Chemin simple dans un graphe non orienté : attention, dans le cadre d'un chemin simple, l'utilisation d'une arête bloque ensuite l'accès aux deux arcs équivalents !
    • chemin simple sur un graphe non orienté
    • Exemple de chemin simple dans le graphe non orienté :
    • Chemin simple dans un graphe non orienté : on ne parvient pas à faire un cycle simple.

      exemple de chemin simple dans un graphe non orienté
      Cliquez sur l'image pour lancer l'animation du chemin simple sur un graphe non orienté

      Chemin simple dans le graphe orienté de la partie précédente : on parvient à faire un cycle simple.

      exemple de circuit simple
      Cliquez sur l'image pour lancer l'animation du chemin simple sur un graphe orienté
  • Cycle : chemin (de plus d'une arête) dont les deux extrémités sont identiques (on part de A et on revient à A)..
    • exemple de cycle
      Cliquez sur l'image pour lancer l'animation du cycle
    • Un graphe non orienté qui ne possède pas de cycle simple est dit acyclique.
    En anglais
    • Vertex pour sommet
    • Edge pour arête

    Ceux qui utilisent Blender devraient reconnaître ces termes.

    2 - 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.

    Le vocabulaire associé aux deux types de graphes

    On utilise parfois des termes différents. Ce vocabulaire spécifique n'est pas à connaître pour la NSI : je n'en parle ici que pour que vous puissiez comprendre les pages ou livres que vous allez trouver sur le sujet.

    Attention : cette classification n'est pas standardisée, le mot est faible. Il est donc possible qu'un terme non orienté soit utilisé dans un contexte orienté, ou l'inverse...

    Conclusion : ne voyez pas dans le tableau ci-dessous comme une référence !

    Terme courant Graphe orienté Graphe non orienté
    Nom anglais Directed graph, digraph Undirected graphs
    Sommet
    (vertex)
    sommet (vertex), noeud (node), point (point) Sommet (vertex), noeud (node), point (point)
    Arête
    (edge)
    Arc (arc), flèche (arrow), ligne (line), lien (link) Arête (edge), flèche (arrow), ligne (line), lien (link)
    Chemin
    (walk)
    Chemin (directed walk) Chaîne (undirected walk)
    Chemin simple
    (trail)
    Chemin simple (directed trail) Chaîne simple (undirected trail)
    Chemin élémentaire
    (path)
    Chemin élementaire (path) Chaîne élémentaire (path)
    Boucle (loop) Boucle (loop) Boucle (loop)

    Chemin simple : on ne rencontre au maximum chaque arête qu'une unique fois.

    Cas particulier : un chemin Eulérien est une chemin qui passe une fois uniquement par toutes les arêtes du graphe.

    Chemin élémentaire : on ne rencontre au maximum chaque sommet qu'une unique fois.

    Cas particulier : un chemin Hamiltonien est une chemin qui passe une fois uniquement par tous les sommets du graphe.

    Ordre d'un graphe ?

  • L'ordre d'un graphe correspond à son nombre de sommets.
  • Ici, on obtient 6.

    Il s'agit de l'équivalent de la taille d'un arbre.

    Degré d'un sommet ?

    Pour un graphe non orienté

  • le degré d'un sommet est le nombre d'arêtes issues de ce sommet
    • Exemple : le degré de a est 3, le degré de f est 1.
    • exemple de degrés

    Pour un graphe orienté

  • le degré entrant d'un sommet est le nombre d'arcs entrant vers le sommet
  • le degré sortant d'un sommet est le nombre d'arcs sortant du sommet
  • Activité publiée le 08 04 2021
    Dernière modification : 08 04 2021
    Auteur : ows. h.