Théorie des graphes

Concept de graphe

Notre point de départ est la définition suivante:

Graphe orienté
Un graphe orienté G est une relation binaire sur un ensemble S, c'est-à-dire un ensemble G⊂SxS.

Remarques:

  1. S peut être infini, si S est fini alors on parle d'un graphe fini
  2. on note le graphe orienté G, ou G(S)
  3. les éléments de S sont appelés les sommets (ou noeuds) du graphe
  4. les couples de la relation sont appelés les arêtes (ou arcs) du graphe
  5. certains auteurs réservent le terme arête pour le cas non-orienté et arc pour le cas orienté, nous ne feront pas cette distinction
  6. dans le cas d'un graphe fini, on le représente souvent graphiquement pas un ensemble de points, les sommets, et des flèches pour les couples de la relation

Notons qu'il n'est pas suffisant de connaître l'ensemble des couples du graphe, il faut aussi l'ensemble des sommets S car certain sommets peuvent ne pas apparaître dans la relation.

Quelques exemples de graphes orientés finis

Pour chacun des exemples ci-dessous, on trouve une représentation ensembliste de la ralation, suivit d'une représentation graphique obtenu avec le logiciel Graphviz. C'est un outil de référence pour la représentation des graphes, il a été utilisé avec les paramètres: "dot -Tpng -o G1.png G1.dot". Cette instruction lit la définition du graphe dans le fichier texte G1.dot, et crée la représentation graphique en format png dans le fichier G1.png. Les liens suivants vous permetterons de récupérer la définition des graphes ci-dessous en format Graphviz: G1, G2.

G1({a,b,c,d}) = { (a,b), (b,c) }
G2({1,2,3,4}) = { (1,2), (1,1), (2,1), (3,2), (4,4) }

Définitions

Taille d'un graphe
C'est le nombre d'arêtes du graphe.
Ordre d'un graphe
C'est le nombre de sommets du graphe.
Chaîne
C'est une suite, ou liste, d'arêtes dans laquelle chacune à une extrémité commune avec l'arête précédente ainsi qu'avec la suivante. Le nombre d'arêtes est la longueur de la chaîne.
Chemin
C'est une chaîne dans laquelle la fin d'une arête est le début de la prochaine.
Cycle
C'est une chaîne dans laquelle une des extrémités de la dernière arête est commune avec une des extrémités de la première arête.
Circuit
C'est un cycle dans lequel la fin d'une arête est le début de la prochaine.
Sommets et arêtes adjacents
Deux sommets sont adjacents si ils ont une arête en commun. De même, deux arêtes sont adjacentes si elles ont un sommet en commun.
Voisinage d'un sommet x
C'est l'ensemble des sommets adjacents au sommet x, pour un graphe donné G, on le note ΓG(x). Le degré, ou valence, d'un somment est la cardinalité de ΓG(x). Si pour un sommet x on a ΓG(x)=∅, on dit qu'il est isolé.
Connexe
Un graphe est dit connexe si il existe au moins une chaîne entre tout couple de sommets distincts.
Sous-graphe
C'est un sous-ensemble de G.

Rappelons qu'une arête est caractérisée par un couple de la relation (x,y), où x est le début de l'arête et y la fin. Une chaîne est une suite de couples. Par exemple, ( (a,b), (b,c) ) est un couple de couples représentant une chaîne de G1. Afin de simplifier l'écriture, on utilise souvent une notation faisant intervenir seulement les sommets de la chaîne: ( a,b,c ). Dans ce cas, il est essentiel de savoir s'il s'agit d'une chaîne ou d'un chemin car on a perdu l'orientation des arêtes.

Quelques exemples d'application de ces définitions aux graphes ci-dessus:

Quelques cas particuliers de graphe

Graphe non-orienté
Si la relation binaire définissant le graphe est symétrique, on dit que le graphe est non-orienté. Puisque pour chaque arête (x,y) ou a aussi l'arête (y,x), on remplace les doubles flèches par un segment de droite entre les sommets.
Arbre
C'est un graphe non-orienté qui est connexe et sans cycle.
Forêt
C'est un graphe non-orienté et sans cycle.

Exemples de graphe

Voir Wikipédia: théorie des graphes.

Application des graphes

Les graphes sont très utilisés en pratique pour toute sorte de raisons. Dans la majorité des cas ont leurs ajoute des informations supplémentaires. Par exemple, des valeurs portées par les arêtes, que l'on appelle généralement des poids.

On utilise souvent un graphe simplement pour représenter visuellement des relations entre des concepts.

Les arbres représentent une des plus importante structure de données de l'informatique.

On utilise les graphes orientés pour représenter un flux de matériel dans un système. Par exemple, un graphe de flux peut représenter le flux de matière première dans un aluminerie. On l'utilise pour créer des outils de simulation du fonctionnement de l'usine afin d'optimiser le design et l'opération.

Si on associe un état à chacun des noeuds d'un graphe, les arêtes représentent les transition possible entre les états. Dans ce cas, on utilise souvent des poids pour représenter la probabilité d'une transition d'un état vers un autre. Ce graphe représente un cas particulier de processus Markovien.

Les arbres

Une forêt est simplement un graphe non-orienté et sans cycle. Si le graphe est connexe, c'est un arbre. Cette définition des arbres est aussi appelé "arbre libre" car aucun noeud ne joue le rôle de racine.

La figure ci-dessus montre tous les arbres libres d'ordres 1 à 6. Notons qu'un arbre d'ordre n est toujours de taille n-1. De plus, tout graphe connecté, non-orienté d'ordre n et de taille n-1 est toujours un arbre.

La figure ci-dessus montre une application des arbres libres: la représentation des molécules des hydrocarbones saturés.

Dans plusieurs domaine, comme l'informatique, un des noeuds de l'arbre joue le rôle de racine. Dans ce cas, le graphe s'étends en branches autour de la racine et les noeuds aux extrémités sont appelés les feuilles.

Un arbre avec une racine peut être représenté sous la forme d'un graphe orienté avec toutes les arêtes s'éloignant de la racine. Par exemple, si on considère l'arbre ci-dessous comme un graphe sur l'ensemble {1,2,3,4,5,6,7,8}. La relation correspondante est donné par les couples {(1,2),(1,4),(1,5),(5,3),(5,6),(5,7),(5,8)}.

Remarquons qu'un tel arbre représente une relation anti-symétrique, irréflexive et non-transitive.