Skip to content

SnowCode

Introduction sur la théorie des graphes

Première partie du cours sur la théorie des graphes, où on va voir les premières notions de graphes.

Premières définitions sur les graphes

Un graphe fini est défini comme un ensemble de sommets (vertices) et un ensemble d'arêtes (edges).

Chaque arête est définie comme une paire non ordonnée de sommets. Les sommets dans une arête sont appelé des extrémités.

Si deux sommets sont reliés par une arête on dit qu'ils sont adjacents et ont dit que l'arête est incidente.

Le nombre de sommets définit l'ordre du graphe. Ainsi un graphe de 3 sommets, sera ainsi définit comme un graphe d'ordre 3.

Représentations graphiques d'un graphe

Si on souhaite définir un graphe sans qu'aucune de ses arêtes ne se croise, on dit que le graphe est planaire.

Il est important de savoir qu'un graphe est un concept théorique, il y a donc une infinité de représentations graphiques possibles pour un même graphe.

Voici par exemple un même graphe avec deux représentations. Le fait que dans la deuxième représentation, aucune arête ne se touche indique que le graphe est planaire.

Représentation d'un graphe non planaire à côté du même graphe en représentation planaire

Types de graphes

Un graphe simple est un graphe où maximum une arête relie deux sommets et où il n'y a pas de boucles sur un sommet.

A l'inverse il y a le multigraphe qui est un graphe où il peut y avoir plusieurs arêtes entre deux même sommets et où une arête peut relier un sommet à lui-même.

Pour les graphes il existe la notation p-graphep représente le nombre d'arête maximum entre deux sommets. Par exemple si il y a au plus deux arêtes entre deux sommets, on dira que c'est un 2-graphe.

Le plus souvent on étudira des 1-graphe.

Exemple d'un 2-graphe multigraphe, d'un 1-graphe et d'un 1-graphe simple

Un graphe est pondéré si des valeurs sont associées aux arêtes. La valeur associée à une arête est appellée le poids de l'arête.

Exemple de graphe pondéré représnetant la distance entre les chefs-lieu de Belgique

Connectivités des graphes

Un graphe est dit connexe lorsqu'il est possible de trouver un chemin pour relier n'importe quel sommet à n'importe quel autre sommet. En d'autres termes cela signifie que tous les sommets sont connectés d'une manirèe ou d'une autre.

A l'inverse un graphe non connexe peut être décomposé en composantes connexes.

Une arête est appellée un pont si sa suppression augmente le nombre de composantes connexes du graphe.

Exemple de graphe non connexe

Le graphe ci-dessus est un graphe non-connexe car il est impossible de relier 6 à 1 par exemple car 5 et 6 forme un groupe à part du graphe.

Si sur le graphe ci-dessus, on supprime l'arête reliant 2 et 3, 2 se retrouve déconnecté du reste, par conséquent le nombre de composantes connexes augmente. Il en va de même pour l'arête 5 à 6. Ces deux arêtes sont donc des ponts dans le graphe.

Graphes complets et biparti

Un graphe est dit complet si chaque sommet du graphe est relié directement à tous les autres sommets.

Exemple de graphe complet

Un graphe complet est souvent représenté avec la notation K ainsi un graphe complet K5 signifie qu'il s'agit d'un graphe complet à 5 sommets.

Un graphe est dit biparti si ses sommets peuvent être divisés en deux ensembles de sorte que les sommets d'un ensemble n'ont d'arrête que vers des sommets de l'autre ensemble.

Exemple de graphe biparti

Le graphe ci-dessus est biparti car les sommets 1, 3 et 5 ne sont pas reliés entre eux mais mais on des liens vers des sommets de l'ensemble 2 et 4. Il en va de même pour 2 et 4 qui sont liés aux sommets de l'ensemble 2,3,5 mais pas entre eux.

Enfin il existe les graphes biparti complèts lorsque chaque sommet de chaque ensemble est connecté à tous les sommets de l'autre ensemble.