Théorie des graphes

Problèmes et théories simples autour de la théorie des graphes :


Notions élémentaires

Un graphe G est défini par un couple (S,A) avec S un ensemble fini de sommets, et A un ensemble fini de couple de sommets (si, sj) dans S².

Dans un graphe orienté, les couples (si,sj) de A sont orientés, c’est-à-dire que si est le sommet initial et sj le sommet terminal. Graphiquement, ce couple est un arc du sommet si vers le sommet sj.

graph1

Dans un graphe non orienté, les couples (si,sj) ne sont pas orientés. Ainsi, (si,sj) est équivalent à écrire (sj,si). Graphiquement, ce couple est une arête entre les sommets si et sj.

graph2

Éléments de terminologie :

  • L’ordre d’un graphe est le nombre de ses sommets |S|.
  • Une boucle est un arc ou une arête (si, si).
  • Un graphe non orienté est dit simple s’il ne contient pas de boucle et s’il comporte au plus une arête entre tout couple de sommets. Sinon il s’agit d’un multi-graphe.
  • Un graphe orienté est dit élémentaire s’il ne contient pas de boucle.
  • Un graphe orienté est un p-graphe sil comporte au plus p arcs entre tout couple de sommets.
  • Un graphe partiel d’un graphe est le graphe obtenu en supprimant certains arcs (ou arêtes).
  • Un sous-graphe d’un graphe est le graphe obtenu en supprimant certains sommets et tous les arcs incidents aux sommets supprimés.
  • Un graphe est dit complet s’il possède une arête (si,sj) pour tout couple de sommets (ou deux arcs (si,sj) et (sj,si)). Un graphe simple complet à n sommets aura n(n-1)/2 arêtes.

Notions d’adjacence :

  • Dans un graphe non orienté, un sommet si est dit adjacent à un sommet sj s’il existe une arête entre si et sj. L’ensemble des sommets adjacents à un sommet si est définit par :
    • graph3
  • Dans un graphe orienté, on distingue les sommets successeurs (terminaux d’un arc) et prédécesseurs (initiaux d’un arc) :
    • graph4

Notions de degré d’un sommet :

  • Dans un graphe non orienté, le degré d’un sommet est le nombre d’arêtes incidentes à ce sommet. Dans le cas d’un graphe simple nous avons :
    • graph5
  • Dans un graphe orienté, le demi-degré extérieur d’un sommet est le nombre d’arcs partant de ce sommet. Dans un 1-graphe nous avons :
    • graph6
  • Dans un graphe orienté, le demi-degré intérieur d’un sommet est le nombre d’arcs arrivant de ce sommet. Dans un 1-graphe nous avons :
    • graph7

Représentation informatique

Il existe deux manières « académiques » de représenter un graphe de façon informatique : soit par une matrice d’adjacence, soit par des listes d’adjacence.

On suppose que les sommets de S sont numérotés de 1 à n. La matrice d’adjacence est une matrice M de taille n*n telle que M[i,j] = value si (i,j) dans A, M[i,j] = no value sinon. Dans le cadre de la présence de lien entre le sommet i et j, value = 1 et no value = 0. Dans le cadre de lien valué entre le sommet i et j, value = pondération et no value = infini. Dans un cadre non-orienté, la matrice sera symétrique du triangle supérieur droit. Ce type de codage demande O(|S|²) emplacements mémoire.

La représentation par listes d’adjacences consiste en un tableau T de n listes, une pour chaque sommet de S. Une liste chainée T[si] contient tous les éléments sj de S tels qu’il existe un lien (si, sj) dans A. C’est-à-dire la liste des successeurs de si. Si le graphe est valué, chaque maillon peut contenir des informations sur la pondération. Ce type de codage demande O(|S|+|A|) emplacements mémoire.

Chaque méthode a des avantages comme des inconvénients en fonction des opérations que l’on souhaite effectuer sur le graphe.

graph8

Cheminements

Dans un graphe orienté, un chemin d’un sommet u vers un sommet v est une séquence <s0, s1, … , sk> de sommets telle que u = s0 et v = sk, et (si, s(i+1)) est dans A pour i de 0 à k-1. La longueur du chemin est le nombre d’arcs dans le chemin, c’est-à-dire k. S’il existe un chemin de u à v, on dira que v est accessible à partir de u. Un chemin est élémentaire si les sommets qu’il contient sont tous distincts.
Un chemin forme un circuit si s0 = sk et si le chemin comporte au moins un arc. Ce circuit est élémentaire si le chemin <s0, …, s(k-1)> (le circuit sans le dernier sommet) est élémentaire. Une boucle est donc un circuit de longueur 1.
Un graphe orienté est dit fortement connexe si chaque sommet est accessible à partir de n’importe quel autre : pour tout couple de sommets distincts il existe un chemin entre eux.

Cela peut se calculer par fermeture transitive. Cette dernière est la somme des n premières puissances de la matrice d’adjacence, n=|A|. Le graphe est fortement connexe si toute la matrice comporte value. Une composante fortement connexe est un sous-graphe fortement connexe.

Les mêmes notions existent pour les graphes non orientés sous le nom de chaine et de cycle. Le graphe est dit connexe et l’on parle de composante connexe.

Problème : graphe eulérien

Pour un graphe orienté, un chemin (ou circuit) eulérien passe une et une seule fois par tous les arcs. De même dans le cas non orienté, une chaîne ou cycle eulérien passe une et une seule fois par toutes les arêtes.

Le graphe doit être fortement connexe (ou connexe). En effet, si le graphe ne l’est pas, un ou plusieurs sous-graphes contenant des liaisons ne sont pas atteignables. On constate qu’un cycle ou circuit eulérien contient autant de liaisons arrivant à un sommet qu’il en part (on arrive à un sommet pour en partir)

Conditions nécessaires et suffisantes du circuit/cycle eulérien. Le graphe est connexe (ou fortement connexe). Quel que soit un sommet du graphe, son degré est pair (son degré sortant est égal à son degré entrant).

Puisque tous les sommets possèdent un degré pair, nous savons qu’il existe un circuit. Un parcours est une union de circuits disjoints au niveau des arêtes. Si l’on retire les arêtes d’un parcours alors les degrés sont toujours pairs. Supposons qu’il n’existe pas de parcours donnant un cycle eulérien. Si l’on retire un parcours avec un maximum d’arête au graphe alors les degrés restent pairs. Mais dans ce cas, il existe un circuit disjoint de notre parcours maximum. Le parcours étant une union de circuits disjoints, on en conclut que le parcours initiale n’était pas maximum. En en déduit que le parcours maximum contient toutes les arêtes du graphe. La démonstration est identique pour le cas orienté.

Soit un graphe admettant une chaîne eulérienne. Rajouter une arête entre le début et la fin de la chaîne nous donnera un cycle eulérien. De même, si l’on supprime une arête quelconque d’un cycle eulérien, on aura une chaîne eulérienne.

Avec cette transformation, nous en déduisons les conditions nécessaires et suffisantes pour qu’un graphe possède une chaîne (ou chemin) eulérien.

Conditions nécessaires et suffisantes de la chaîne/chemin eulérien. Le graphe est connexe (ou fortement connexe). Pour tous sommets du graphe, sauf éventuellement deux, son degré est pair (son degré sortant est égal à son degré entrant + ou – 1 pour éventuellement deux sommets.

Problème : graphe hamiltonien

Dans un graphe orienté, un circuit ou un chemin hamiltonien est un circuit ou chemin passant une et une seule fois par tous les sommets. De même pour le cas non orienté.

Il n’existe pas à ce jour de conditions nécessaires et suffisantes mais seulement des conditions suffisantes portant sur les degrés des sommets.

Dirac 1952. Un graphe simple à n sommets (n>2) dont chaque sommet a un degré au moins égale à n/2 est hamiltonien.
Posa 1962. Un graphe simple à n sommets (n>2) tel que pour tout k, 0<k<(n-1)/2 le nombre de sommets de degré inférieur ou égal à k est inférieur à k. Le nombre de sommets de degré inférieur ou égale à (n-1)/2 est inférieur ou égal à (n-1)/2.
Publicités