Théorie des graphes 101 - Complex systems and AI

IV. Cheminement

VI. Topologie

Contenus

Théorie des graphes

En théorie des graphes, 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 (s_i, s_j) dans S².

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

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

É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 (s_i,s_i).
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 (s_i,s_j) pour tout couple de sommets (ou deux arcs (s_i,s_j) et (s_j,s_i)). Un graphe simple complet à n sommets aura n(n-1)/2 arêtes.
Un attribut peut être associé à (s_i,s_j). L’attribut peut être une lettre, un mot ou un poids (valeur numérique). Un graphe avec des poids est appelé Réseau.

Considérons un graphe G = (V, E,w) avec une fonction de poids :

Notions d’adjacence :

Dans un graphe non orienté, un sommet s_i est dit adjacent à un sommet s_j s’il existe une arête entre s_i et s_j. L’ensemble des sommets adjacents à un sommet s_i est définit par :

Dans un graphe orienté, on distingue les sommets successeurs (terminaux d’un arc) et prédécesseurs (initiaux d’un arc) :

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 :

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 :

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 :

Le nombre de sommets de degré impair est pair. La somme de tous les degrés est égale à deux fois le nombre d’arêtes. Puisque la somme des degrés est paire et que la somme des degrés des sommets à degré pair est paire, la somme des degrés des sommets à degré impair doit être paire. Si la somme des degrés de sommets avec degré impair est pair, il doit y avoir un nombre pair de ces sommets.

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[s_i] contient tous les éléments s_j de S tels qu’il existe un lien (s_i, s_j) dans A. C’est-à-dire la liste des successeurs de s_i. 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.

Cheminements

Dans un graphe orienté, un chemin d’un sommet u vers un sommet v est une séquence <s₀, s₁, … , s_k> de sommets telle que u = s₀ et v = s_k, et (s_i, 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. u est appelé Start, v est appelé End.

Un chemin forme un circuit si s₀ = s_k et si le chemin comporte au moins un arc. Ce circuit est élémentaire si le chemin <s₀, …, s_(k-1)> (le circuit sans le dernier sommet) est élémentaire. Une boucle est donc un circuit de longueur 1. Le graphe est dit acyclique s’il ne possède aucun circuit.

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.