Sommets, arêtes et vocabulaire

Un modèle universel de relations

Un graphe est une structure qui relie des objets entre eux. Chaque objet est un sommet (ou noeud), et chaque lien entre deux sommets est une arête. C'est tout — et pourtant ce modèle décrit une quantité stupéfiante de situations :

Situation	Sommets	Arêtes
Réseau social	les personnes	« est ami avec »
Carte routière	les villes	les routes
Le Web	les pages	les liens hypertextes
Métro	les stations	les tronçons de ligne

Contrairement à un arbre, un graphe n'a ni racine ni hiérarchie : n'importe quel sommet peut être relié à n'importe quel autre, et il peut même y avoir des cycles (des boucles).

        (A)------(B)
         |      / |
         |    /   |
         |  /     |
        (C)------(D)
                  |
                 (E)

Ici A, B, C, D forment un cycle : on peut partir de A et y revenir sans repasser deux fois par la même arête.

Orienté ou non orienté

Une arête peut être à double sens (non orientée) ou à sens unique (orientée, dessinée avec une flèche).

   Non oriente :  A --- B      (l'amitié est réciproque)

   Oriente :      A --> B      (A suit B sur un réseau,
                               mais pas forcément l'inverse)

Un plan de métro est non orienté (les rames vont dans les deux sens) ; un réseau de « qui suit qui » est orienté.

Pondéré : quand les arêtes ont un poids

Souvent, une arête porte un poids : une distance, un temps, un coût. On parle de graphe pondéré.

        (A)--4--(B)
         |      /
         6    2
         |  /
        (C)

Trouver le plus court chemin de A à B dans un tel graphe (par A-B = 4, ou par A-C-B = 6+2 = 8 ?) est l'un des grands problèmes de l'informatique.

Le vocabulaire à retenir

• Degré d'un sommet : le nombre d'arêtes qui y touchent. Dans le premier schéma, B a un degré de 3 (relié à A, C, D).
• Voisins d'un sommet : les sommets directement reliés à lui.
• Chemin : une suite d'arêtes menant d'un sommet à un autre.
• Cycle : un chemin qui revient à son point de départ.

En résumé

Un graphe relie des sommets par des arêtes. Il peut être orienté (à sens unique) ou non, pondéré (arêtes avec un poids) ou non. Sa liberté totale — cycles autorisés, aucune hiérarchie — en fait le modèle de presque tous les réseaux : routes, amitiés, pages web.