Previous Up Next
Mathématiques pour l’Informatique 2 2015–16                  http://www.lri.fr/~paulin/MathInfo2


2  Graphes

Dans ce chapitre, nous allons poser les bases d’une structure qui a beaucoup d’importance en informatique qui est celle de graphe. On a vu au chapitre précédent la notion de relation binaire, qui est une notion importante car c’est à partir d’elle qu’on définit d’autres notions comme celles de fonction, d’égalité, de relation d’ordre. Les graphes peuvent se voir comme une forme “concrète” de relations binaires sur un ensemble A : les éléments de A sont vus comme des points et deux éléments de A qui sont dans la relation sont reliés par un arc. La théorie des graphes va se poser des questions sur les chemins qui peuvent être construits dans le graphe (avec des contraintes comme de ne visiter les sommets une seule fois, ou de trouver le chemin le plus court entre deux sommets), ou encore la possibilité de colorier les sommets avec la contrainte que deux sommets liés ne sont pas de la même couleur. On s’intéresse à ces problèmes à la fois de manière abstraite mais aussi pour construire des algorithmes efficaces pour les résoudre. En effet beaucoup de problèmes concrets peuvent se modéliser comme des problèmes de graphes.

La théorie des graphes est un domaine complexe qui est l’objet de cours entiers spécifiques au niveau master et qui reste un sujet de recherche actif. L’objectif dans ce cours est de fournir les bases du vocabulaire sur les graphes qui est utile dans de nombreux contextes et d’illustrer les concepts sur des exemples élémentaires.

2.1  Exemples

Nous commençons par donner quelques exemples de problèmes qui peuvent se ramener à des questions sur les graphes.

Les ponts de Königsberg

Dans la ville de Königsberg, peut-on faire un trajet qui passe une et une seule fois par chacun des sept ponts et revenir à son point de départ ?

Euler en 1736 répond à cette question en utilisant une modélisation comme un graphe.

La réponse est négative, pourquoi ?

Un exemple venant de la compilation

Comment stocker des variables dans un nombre limité de registres pour faire un calcul ?

Les variables d,k,j seront utilisées dans la suite du programme.

instructionsvariables utiles
g:= mem [j+12]k j
h:= k - 1j g k
f:= g * hj g h
e:= mem[j+8]j f
m:= mem[j+16]j f e
b:= mem[f]m f e
c:= e+8m b e
d:= cm b c
k:= m+4m b d
j:= bb d k
 d k j

Graphe d’interférence

Les variables qui doivent être disponibles en même temps sont liées. Ranger les variables dans des registres revient à colorier le graphe.

Coloriage : une solution avec 4 couleurs

Si un sommet a moins de 3 voisins on peut toujours lui trouver une couleur.

Il y a beaucoup d’autres situations dans lesquelles la notion de graphe est importante, par exemple pour tout ce qui est la planification de trajets (dans une agence de voyage, ou bien à l’aide de GPS). La structure de graphe sera alors enrichie avec des annotations comme la durée du trajet ou son coût et on cherchera des chemins qui sont optimaux suivant certains critères.

Les graphes servent aussi à décrire des systèmes à états et transitions comme un système d’authentification avec un mot de passe que l’on ne peut essayer plus de trois fois ou encore un système de passage à niveau qui se ferme à l’approche d’un train. Les sommets du graphe vont correspondre à la description de l’état du système et les arètes correspondent à des changements d’états en fonction d’événements spécifiques.

2.2  Définitions

On a vu sur les exemples, que dans un graphe on avait des points (appelés sommets) et des liens entre deux points (appelés arêtes). On a visualisé les graphes comme des dessins mais ce n’est qu’une représentation, la définition générale est plus abstraite.

On distingue deux sortes de graphes suivant s’ils sont orientés ou non. Dans un graphe orienté, les liens entre deux sommets ont une direction (que l’on représente en général par une flèche), c’est-à-dire qu’il est possible qu’il y ait un chemin de A à B sans qu’il y ait de chemin inverse de B à A.

Définition 1 (Graphe)   Un graphe G est défini par un triplet (S,A,є) de deux ensembles et une application. L’ensemble S est l’ensemble des sommets, l’ensemble A celui des arêtes et le fonction є associe à une arète les points qui sont ses extrémités. On dit que deux sommets sont adjacents s’il existe une arête qui les relie.

Afin de ne pas dupliquer les définitions, on introduit une relation entre les arêtes et les sommets E(e,a,b) qui représente le fait que l’arête e a pour extrémités les sommets a et b. Dans le cas d’un graphe orienté, cela revient à dire que є(e)=(a,b) et dans le cas d’un graphe non orienté є(e)={a,b}

Remarques.

2.3  Degré, chemins

Définition 2 (Degré d’un sommet)   Soit G =def  (S,A,є) un graphe et aS un sommet. On définit le degré de a noté d(a).

Dans un graphe non orienté, d(a) est le cardinal de l’ensemble des arêtes qui ont a pour extrémité, les boucles sur a vont compter deux fois. On a donc

d(a)=|{e∈ A|a∈ є(e)}|+|{e∈ A|є(e)={a}}|

Dans un graphe orienté, on distingue les arêtes entrantes qui ont a comme destination et les arêtes sortantes qui ont a comme origine. Le degré entrant, noté d(a), est le nombre d’arêtes entrantes alors que le degré sortant, noté d+(a), est le nombre d’arêtes sortantes. Le degré d’un sommet est la somme des degrés entrants et sortants.

d(a)=|{e∈ A|∃ b, (b,a)∈ є(e)}|          d+(a)=|{e∈ A|∃ b, (a,b)∈ є(e)}|          d(a)=d+(a)+d(a)
Définition 3 (Chemin dans un graphe)   Soit G =def  (S,A,є) un graphe.
Proposition 1 (Concaténation de deux chemins)   s’il existe un chemin de a à b de longueur n et un chemin de b à c de longueur p alors il existe un chemin de a à c de longueur n+p.

Preuve: Le chemin entre a et b s’écrit (a0,e1,a1,…,en,an) avec a0=a et an=b. Le chemin entre b et c s’écrit (b0,f1,b1,…,fp,bp) avec b0=b et bp=c. On forme le chemin entre a et c en concaténant les deux chemins puisque an=b=b0 : (a0,e1,a1,…,en,b,f1,b1,…,fp,bp) qui est bien un chemin de longueur n+p qui va de a à c.

Proposition 2   Dans un graphe non-orienté, s’il existe un chemin de a à b alors il en existe un de b à a.

Preuve: Par récurrence sur la longueur du chemin.

Exemples de graphe

On considère les deux graphes ci-dessous, le premier est non-orienté, le second est orienté.

Indiquer les degrés des sommets 2 et 4.
Donner plusieurs chemins des sommets 4 à 6.
Ces graphes sont-ils fortement connexes ? Même question pour les sous-graphes dans lesquels on a enlevé les sommets 1 et 5.

Proposition 3   Soit un chemin allant de a à b alors il existe un chemin élémentaire (qui ne passe pas deux fois par le même sommet), plus court, allant de a à b.

Preuve: Soient deux sommets a et b et un chemin entre a et b noté (a0,e1,a1,…,en,an) avec a0=a et an=b. Si le chemin est élémentaire, la propriété est montrée. Sinon il existe deux indices i et j tels que i<j et ai=aj et en choisissant i le plus petit possible et j le plus grand possible on garantit que pour tout 0≤ k<i et j<ln on a akal. On considère le chemin obtenu en mettant bout à bout le sous-chemin allant de a0 à ai et le sous-chemin allant de aj à an qui est élémentaire.

On est souvent intéressé par revenir à son point de départ.

Définition 4 (Circuit)   
Définition 5 (Circuit eulérien, cycle hamiltonien)   
Proposition 4  

Preuve: On regarde le cas des graphes non-orientés.

S’il n’y a pas de points isolés alors le cycle eulérien qui passe par toutes les arêtes passe aussi par tous les sommets. Le graphe est donc fortement connexe puisque deux sommets sont reliés par la portion du circuit entre ces deux sommets. Lorsqu’un sommet apparait dans le chemin il y a une arête qui entre et une qui sort, c’est évident pour les sommets qui sont au milieu du chemin mais c’est aussi vrai pour les extrémités puisque le départ et l’arrivée sont les mêmes, donc le degré de chaque sommet est pair.

Montrons que tout graphe G fortement connexe dont les sommets sont de degré pair à un cycle eulérien.

On fait la preuve par récurrence sur le nombre d’arêtes du graphe. S’il n’y a pas d’arêtes alors comme il n’y a pas de point isolé le graphe est vide et le résultat est vrai.

Supposons que le résultat est vrai pour tout graphe ayant moins de n arêtes et montrons qu’il est vrai pour un graphe qui à n+1 arêtes. On distingue plusieurs cas

  1. si le graphe a une boucle sur un sommet a, alors on retire cette boucle. On obtient un graphe G, les degrés des sommets de G sont toujours pairs (seul le degré de a a diminué de deux). Le graphe G est fortement connexe (s’il existe un chemin entre deux points, il en existe un qui est élémentaire et donc en particulier ne passe pas par la boucle). On peut donc appliquer l’hypothèse de récurrence au graphe G pour construire un cycle eulérien C, il suffit ensuite de rajouter la boucle sur a dans le cycle eulérien lorsqu’il passe par a pour avoir un cycle eulérien du graphe d’origine G;
  2. si le graphe n’a pas de boucle, alors il existe un point a de degré au moins 2 dont il part deux arêtes e et f. On construit un graphe G en retirant les deux arêtes e et f et en les remplaçant par une arête g entre b et c. Si b et c sont le même sommet alors l’arête g est une boucle.
    Le nouveau graphe G a toujours tous ses sommets de degré pair. En effet le degré de a a diminué de 2 et les degrés de b et c n’ont pas bougé. Le graphe G a également une arête de moins que le graphe G. On ne peut néanmoins pas appliquer directement l’hypothèse de récurrence car rien ne garantit que le graphe G soit fortement connexe.
    • Si le graphe G est fortement connexe, alors par hypothèse de récurrence il admet un cycle eulérien. Dans ce cycle eulérien apparaît une et une seule fois l’arête g, et il suffit de remplacer cette arête par la suite eaf ou fae suivant le sens dans lequel l’arête est parcourue. On a alors un cycle eulérien de G.
    • Si le graphe G n’est pas fortement connexe, alors il se compose de deux sous-graphes fortement connexes : le sous-graphe Ga des sommets accessibles dans G à partir de a et le sous-graphe Gb des sommets accessibles dans G à partir de b. En effet si on prend n’importe quel nœud x, il est relié à a dans G car G est connexe. S’il n’est pas relié à a dans G c’est que le chemin passe par l’arête e ou f. On regarde la première fois où on passe par l’une de ces arêtes, si c’est e alors il y a un chemin dans G de x à b, si le chemin passe d’abord par l’arête f alors il y a un chemin dans G de x à c que l’on prolonge par l’arête g vers b.

      Il ne peut pas y avoir d’arête qui va d’un sommet de Ga à un sommet de Gb sinon tous les sommets de G seraient liés. Donc les arêtes de G sont soit dans Ga soit dans Gb. Les degrés des sommets dans Ga et Gb sont les mêmes que ceux des sommets dans G et sont donc pairs. Le nombre d’arêtes dans chacun de ces graphes est plus petit que le nombre d’arêtes de G et donc que n. L’hypothèse de récurrence s’applique aux deux graphes. On obtient deux cycles eulériens Ca qui couvre les arêtes de Ga et Cb qui couvre les arêtes de Gb. Il suffit de prendre le cycle Cb qui contient l’arête g, par exemple dans la direction bgc et on remplace cette arête par bfCagc. On a bien ainsi couvert toutes les arêtes du graphe G.

2.4  Représentation

On va proposer plusieurs représentations concrètes des graphes (finis) qui pourront donner des pistes pour une représentation en machine. On s’intéresse ici à des graphes finis (nombre fini de sommets et d’arêtes).

Il est donc toujours possible de représenter les sommets et les arêtes par des entiers.

2.4.1  Matrice d’incidence

La matrice d’incidence est une matrice qui représente la relation entre les arêtes et ses extrémités. Cette matrice a pour lignes les sommets et comme colonnes les arêtes.

Dans le cas d’un graphe non orienté, la matrice d’incidence J contient des entiers entre 0 et 2. On a J(a,e)=0 si a∉є(e) J(a,e)=2 si є(e)={a} et J(a,e)=1 dans les autres cas, c’est-à-dire si a ∈є(e) et є(e)≠{a}.

Exemple : matrice d’incidence

L’exemple précédent du graphe non orienté a la matrice d’incidence suivante.

Dans le cas d’un graphe orienté on utilisera deux matrices qui ne contiennent que des 0 et des 1. La matrice d’incidence sortante J+ et la matrice d’incidence entrante J telles que J+(a,e)=1 si et seulement si il existe bS tel que є(e)=(a,b) et J(b,e)=1 si et seulement si il existe aS tel que є(e)=(a,b).

Exemple : matrices d’incidences sortante et entrante

L’exemple précédent du graphe orienté a la matrice d’incidence sortante et la matrice d’incidence entrante suivantes.

Exercice 1   Dire à quoi correspondent la somme des valeurs des lignes et des colonnes de chacune des matrices. Comment sont reliés les matrices d’incidence d’un graphe orienté et celle du graphe non-orienté sous-jacent.

2.4.2  Matrice d’adjacence

Une autre manière de représenter le graphe G =def (S,A,є) est de le voir comme une matrice carrée indicée par l’ensemble des sommets S et telle que sur la ligne a et la colonne b on met l’ensemble des arêtes qui ont a et b comme extrémités, c’est-à-dire l’ensemble {eA| E(e,a,b)}. Si on s’intéresse à une représentation des graphes à isomorphisme prêt, il n’est même pas nécessaire de conserver dans la matrice l’ensemble des arêtes, il suffit de conserver leur nombre. En effet on peut toujours à partir de la matrice, compter le nombre total d’arêtes et ensuite les numéroter.

Exemple : matrice d’adjacence

Les exemples de graphes donnés précédemment ont pour matrice d’adjacence :

Un graphe non orienté est représenté par une matrice symétrique.

2.5  Recherche de chemins

Soit un graphe G sur l’ensemble de sommets 1,…,n et α sa matrice d’adjacence.

Il y a un chemin entre deux sommets, si et seulement si il y a un chemin élémentaire qui ne passe pas deux fois par le même sommet. Comme il y a n sommets, ce chemin a au plus n−1 arêtes. Il n’est donc pas utile de chercher etre les deux points des chemins de longueur plus que n−1.

Chemins de longueur k

Si on multiplie α par elle même on obtient une matrice α2 telle que α2(i,j)=Σk=1k=nα(i,k)α(k,j). Ce nombre représente exactement le nombre de chemins de longueur 2 entre i et j. On montre aisément par récurrence sur k que la matrice αk a comme coefficient (i,j) le nombre de chemins de longueur k entre les sommets i et j.

Multiplier deux matrices carrées de taille n nécessite par la méthode naive n3 opérations et donc déterminer s’il y a un chemin entre deux points du graphe en calculant αn−1 par une méthode naive de calcul d’exponentiel prendra de l’ordre de n4 opérations. En calculant αn avec une méthode dichotomique, on peut ne faire que log2(n) multiplications.

Chemins

On peut aussi vouloir simplement savoir s’il existe un chemin entre deux points. C’est l’algorithme de Warshall. L’idée est de construire par récurrence sur k une matrice βk qui contient des booléens et telle que βk(i,j)=V si et seulement si il y a un chemin de i à j dont les nœuds intermédiaires sont dans l’ensemble {1,…,k}.

Dans le cas où k=0 il n’y a pas de nœud intermédiaire et donc il y a un chemin si et seulement si il y a une arête et donc β0(i,j)=(α(i,j)≠0).

Maintenant on suppose que l’on a calculé βk et on veut calculer βk+1. Il y a un chemin de i à j dont les nœuds intermédaires sont dans l’ensemble {1,…,k+1}. Deux cas sont possibles,

On a donc βk+1(i,j)=βk(i,j)∨ βk(i,k+1)∧βk(k+1,j).

On peut donc calculer βk+1 en n2 opérations et donc finalement savoir s’il y a un chemin entre deux points en calculant βn−1 en n3 opérations.


Previous Up Next