Structure d'un graphe

Auteur :

François Brucker

Cours/Théorie des graphes/Introduction à la théorie des graphes/Structure d'un graphe

Définition de la structure de graphe et de ses composants (sommets et arêtes). On terminera cette partie en démontrant une première propriété fondamentale les liant.

Dans toute sa généralité, on peut définir un multi-graphe comme étant un triplet $G = (V, E, \phi)$ où :

$V$ est un ensemble de sommets (vertices).
$E$ est un ensemble d'arcs (edges)
$\phi: E \rightarrow V \times V$ une fonction d'incidence qui associe à chaque arête un couple (possiblement égaux) de sommets.

Cette définition permet de considérer des ensemble a priori non dénombrable, mais elle le fait au prix d'une grosse lourdeur de manipulation puisqu'il faut passer par une fonction d'incidence.

En pratique, on aura toujours un nombre fini de sommets et d'arêtes (ou au pire dénombrable), on choisit donc une définition plus restrictive, mais plus facilement manipulable en informatique :

Définition

Un multi-graphe est un couple $G = (V, E)$ où :

$V$ est un ensemble fini de sommets (vertices)
$E$ est une liste finie de d'éléments de $V \times V$ appelés arcs (edges)

Notez que la définition précédente s'étant sans problème aux ensemble infinis dénombrables.

Pour ne pas avoir à toujours rappeler l'ensemble des sommets et des arêtes d'une graphe, on utilisera parfois les notations suivantes :

Définition

Si $G$ est un multi-graphe, on note :

$V(G)$ et $v(G)$ pour noter l'ensemble des sommets et leur nombre,
$E(G)$ et $e(G)$ pour noter l'ensemble des arcs et leur nombre.

Exemple

Le multi-graphe $G = (V, E)$ avec :

$V = \{1, 2, 3, 4, 5\}$
$E = ((1, 2), (2, 3), (2, 2), (1, 2), (4, 5), (5, 4))$

Peut se représenter graphiquement (sur le plan) :

exemple multi-graphe

Remarquez qu'un multi-graphe peur avoir :

plusieurs fois le même arc : l'arc $(1, 2)$
des boucles : l'arc $(2, 2)$

Utilité

Les multi-graphes sont des outils puissants de modélisation permettant de résoudre nombre de problèmes d'optimisation.

Résolution de problème

Outre le problème évident de construction ou de maintien de réseaux (informatique, de transports ou encore sociaux), on peut aussi citer :

google maps. On cherche un itinéraire entre deux villes en ne connaissant à priori que ce qui se passe entre deux croisement consécutifs, mais on connaît tous les croisements,
les contraintes d'allocations de ressources. Les sommets sont les antennes et les arêtes si il y a des interférences possibles, on cherche à trouver une coloration du graphe,
problèmes de transports où l'on veut distribuer le plus de ressources possibles dans un réseau routier/fluvial/informatique,

Les problèmes ci-dessus ont ceci de particulier qu'ils peuvent très facilement se décrire localement :

le problème de la recherche d'itinéraire se décrit par une liste de croisement et, pour chaque croisement, une liste de ceux qu'il peut atteindre
le problème d'allocation de ressources se décrit de même par une liste d'antenne et, pour chaque antenne, une liste de celles avec laquelle il y a interférence possible
enfin, le problème de transport se décrit de la même manière que le problème d'itinéraire en ajoutant une capacité à chaque couple de croisement)

Mais la solution cherchée est globale :

une suite de croisement pour le problème d'itinéraire
une fréquence à associer à chaque antenne pour le problème d'allocation de ressources
un flot sur chaque route pour le problème de transport

C'est une caractéristique générale :

À retenir

Un problème pouvant se décrire localement mais dont la solution est globale peut souvent se modéliser puis se résoudre à l'aide de graphes.

Modélisation

Ils permettent également de comprendre le réel en utilisant des classes particulières de multi-graphes. Par exemple :

le modèle arboré des arbres phylogénétique modélisent l'évolution des espèces
des graphes aléatoire générés en utilisant par exemple le modèle de Barabasi-Albert permettent de créer des graphes "petit monde" typiques des réseaux sociaux ou de l'internet.

Esthétique

Enfin, ils procurent une satisfaction purement esthétique de part la grande beauté des démonstrations, de leurs théorèmes et de leurs algorithmes.

Définition d'un Graphe

Notre définition est tellement générale, qu'elle est très peu utilisée telle quelle. On utilisera souvent des cas particuliers selon le problème que l'on veut résoudre :

Définition

Un multi-graphe sera dit :

sans boucles si es arcs commencent et finissent toujours sur nœuds différents.
sans arcs multiples si une arête ne peut arriver qu'une seule fois (les arêtes sont un sous-ensemble de $V \times V$ : c'est une relation).
non orienté si le sens d'une arête importe peu (une arête est alors un sous-ensemble à 2 éléments).

Ainsi, un multi-graphe non orienté sans boucle est un multigraphe tel que si $(x, y) \in E$ alors $(y, x) \in E$ et tel que $(x, x) \notin E$ pour tout $x \in V$.

Le cas le plus simple (et donc celui que l'on utilisera en priorité) est le multi-graphe sans boucle, sans arcs multiples et non orienté. On les appelle graphes et on peut les définir comme suit :

Définition

Un graphe est un couple $G = (V, E)$ où :

$V$ est un ensemble fini. Ses éléments sont appelés sommets.
$E$ est un sous-ensemble de $\{ \{x, y\} \mid x \neq y \in V \}$. Ses éléments sont appelés arêtes.

De cette définition minimale on pourra alors définir d'autres cas, comme le graphe orienté :

Définition

Un graphe orienté est un multi-graphe sans boucle et sans arcs multiples. C'est un couple $G = (V, E)$ où :

$V$ est un ensemble fini
$E$ est un sous-ensemble de $\{ (x, y) \mid x \neq y \in V \}$

Enfin, plus rarement, vous pourrez rencontrer des graphes mixtes qui permettent de rendre compte de situations réelles comme lorsque l'on modélise des réseaux routiers où il existe à la fois des routes à doubles sens et à sens unique et où l'on ne veut parcourir une route qu'une seule fois (pas une fois dans un sens et une fois dans l'autre pour les routes à double sens) :

Définition

Un graphe mixte est un triplet $G= (V, E, A)$ tel que $G_1=(V, E)$ soit un graphe non orienté et $G_2=(V, A)$ soit un graphe orienté.

Ou toutes les généralisations de ceux-ci comme :

le graphe avec arêtes multiples
le graphe avec boucles
un multi-graphe mixte orienté
...

Il est important de connaître précisément de quels type de graphe on parle car les algorithmes ne fonctionnent pas toujours sur toutes les classes de graphes.

Vocabulaire

À retenir

Par abus de langage on écrira $xy$ pour designer une arête (resp. arc) plutôt que $\{x, y\}$ (resp. $(x, y)$).

Parties de graphes

On a parfois envie de découper un graphe pour en étudier une partie (s'il est trop gros ou que certains sommet et/ou arêtes ne nous intéresse pas) ou au contraire de rabouter plusieurs graphes entres eux pour en former un plus gros. Il existe deux façons canonique de découper un graphe, supprimer soit des sommets, soit des arêtes :

Définitions

Soit $G = (V, E)$ un (multi-)graphe (non) orienté. Si $V' \subsetneq V$ et $E' \subsetneq V' \times V' \cap E$, alors $\left.G\right|_{V'} = (V', E')$ est un sous-graphe de $G$.

Un sous-graphe admet deux cas particuliers :

Définitions

Soit $G = (V, E)$ un (multi-)graphe (non) orienté, $V' \subsetneq V$ et $E' \subsetneq V' \times V' \cap E$.

$G'=(V, E')$ est appelé graphe partiel ou encore un sous-graphe couvrant de $G$
$G' = (V' , E' \cap V' \times V')$ est dit être un sous-graphe induit de $G$. On dit que $G'$ est la restriction de $G$ à $V'$ et est noté $G\vert_{V'}$.

Un cas d'intérêt particulier de sous-graphes induits pour les graphes sont les cliques et les stables :

Définitions

Soit $G = (V, E)$ un graphe. L'ensemble $V' \subseteq V$ est dit être :

une clique de $G$ si son sous-graphe induit par $V'$ est complet,
un stable de $G$ si son sous-graphe induit par $V'$ est discret.

Par exemple pour le graphe $G$ suivant :

losange

$G' = (\{A, B, C, D\}, \{ BC , CD\} )$ est un graphe partiel de $G$
$G'' = (\{A, B, D\}, \{ AB , AD\} )$ est un sous-graphe induit de $G$
$\{A, B, C\}$ est une clique de $G$
$\{B, D\}$ est un stable de $G$

Taille et ordre

Définition

Pour un graphe (potentiellement orienté) $G = (V, E)$ on appellera :

ordre le nombre de sommets d'un graphe et on le note $n$ par défaut
taille le nombre d'arêtes d'un graphe et on le note $m$ par défaut

A ordre fixé, les graphes de taille maximum son dit complet :

Définition

Un graphe est complet s'il possède toutes les arêtes : pour tous $x, y \in V$ $xy$ est une arête. On le note $K_n$ et $m = n(n-1)/2$.

Réciproquement, un graphe sans arête est dit discret :

Définition

Un graphe est discret s'il ne possède aucune arête.

On peut noter qu'un graphe orienté ayant un nombre maximum d'arêtes est en fait un graphe (non orienté) complet. C'est pour cela que la définition d'un graphe orienté complet n'existe pas. On préfère parler de tournoi :

Définition

Un tournoi est un graphe orienté $G=(V, E)$ tel que :

si $xy \in E$ alors $yx \notin E$
pour tous $x \neq y \in V$, soit $xy$ soit $yx$ est un arc de $G$.

Arcs

Un arc $xy$ est un élément de $E$ pour les graphes orientés. On le représente graphiquement comme ça :

arc

Quelques notations et définitions relatives aux arcs :

Définitions

$x$ est l'origine de l'arc,
$y$ est la destination de l'arc.

On appelle voisinage sortant de $x$ (neighbors) l'ensemble des arcs d'origine $x$ et on le note :

$$N^+(x) = \{ y \mid xy \in E\}$$

Son cardinal est appelé degré sortant de $x$ et est noté :

$$\delta^+(x) = \vert N^+(x) \vert$$

De la même manière, l'ensemble des arcs de destination $y$ est appelé voisinage entrant en $y$ et est noté :

$$N^-(y) = \{ x \mid xy \in E\}$$

Son cardinal est appelé degré entrant de $y$ et on le note :

$$\delta^-(y) = \vert N^-(y) \vert$$

Lorsque l'on a besoin d'inclure l'élément dans le voisinage, on considère les voisinages fermés :

Définitions

On appelle voisinage fermé de $x$ l'ensemble des arcs d'origine $x$ plus $x$ et on le note :

$$N^+[x] =N^+(x) \cup \{ x \}$$

$$N^-[x] =N^-(x) \cup \{ x \}$$

Arêtes

Une arête $xy$ est un élément de $E$ pour les graphes non orienté. On la représente graphiquement comme ça :

arête

Contrairement aux arcs, il n'y a pas de distinction entre origine et destination :

Définitions

Le voisinage d'un sommet $x$ est l'ensemble des sommets $y$ tels que $xy \in E$. On les notes :

$$N(x) = \{ y \mid xy \in E\}$$

$$N[x] = N(x) \cup \{ x \}$$

Le cardinal d'un voisinage est appelé degré. On le note :

$$\delta(x) = \vert N(x) \vert$$

En remarquant que $0 \leq \delta(x) < n$ pour un sommet $x$ d'un graphe à $n$ sommets, prouvez la propriété suivante :

Montrez que dans tout graphe (à au moins 2 sommets) il existe au moins deux sommets différents ayant même degré.

solution

C'est une application directe du principe des tiroirs. Pour un graphe à $n$ sommet, le degré de tout sommet est entre 0 et $n-1$, soit $n$ possibilités. Si tous les sommets avaient des degrés différents il y en aurait 1 avec 0 voisins et un autre avec $n-1$, ce qui est impossible.

Enfin :

Définitions

Si $G=(V, E)$ est un graphe, on note :

$\Delta(G) = \max(\{\delta(x) \vert x \in V\})$
$\delta(G) = \min(\{\delta(x) \vert x \in V\})$

Si tous les sommets ont mêmes degré, on les appelle régulier :

Définitions

Un graphe $G$ est dit k-régulier (ou parfois juste régulier) si $\Delta(G) = \delta(G) = k$.

Voisinages et arêtes

Nous allons présenter une première relation fondamentale pour les graphes. Cette propriété va lier une notion locale : les voisinages de sommets, à une notion globale : le nombre d'arêtes du graphe.

Avant d'énoncer la propriété, commençons par le visualiser. Considérons le graphe orienté avec boucles suivant :

un graphe orienté

On a par exemple :

$N^+(a) = \{ b, e \}$,
$\delta^+(b) = \delta^-(b) = 2$.

Calculez $\sum_x \delta^+(x)$ ? et $\sum_x \delta^-(x)$

solution

$$\sum_x \delta^+(x) = \delta^+(a) + \delta^+(b) + \delta^+(c) + \delta^+(d) + \delta^+(e) = 2 + 2 + 1 + 1 + 2 = 8$$

$$\sum_x \delta^-(x) = \delta^-(a) + \delta^-(b) + \delta^-(c) + \delta^-(d) + \delta^-(e) = 2 + 2 + 1 + 2 + 1 = 8$$

On remarque que la boucle en $b$ est comptée pour $\delta^-(b)$ et pour $\delta^+(b)$. On peut également remarquer que $\sum_x \delta^+(x) = \sum_x \delta^-(x) = \vert E \vert$.

On voit que $\sum_x \delta^+(x) = \sum_x \delta^-(x)$et vaut le nombre d'arcs du graphe orienté avec boucle.

Cette constatation va — peu ou prou — s'étendre aux graphes. Une version non orienté du graphe orienté avec boucles précédent pourrait être :

un graphe simple

On a :

$\delta(a) = 3$,
$N(a) = \{b, d, e \}$.

Calculez $\sum_x \delta(x)$

solution

$$\sum_x \delta(x) = \delta(a) + \delta(b) + \delta(c) + \delta(d) + \delta(e) = 3 + 2 + 2 + 3 + 2 = 12$$

On peut remarquer que $\sum_x \delta(x) = 2\vert E \vert$.

On peut maintenant démontrer :

Propriété

Pour un graphe orienté avec boucle $G=(V, E)$, on a la propriété suivante :

$$ \sum_x \delta^+(x) = \sum_x \delta^-(x) = \vert E \vert$$

Pour un graphe $G=(V, E)$, on a :

$$ \sum_x \delta(x) = 2\vert E \vert$$

Preuve

Pour un graphe orienté avec boucle, chaque arc $uv$ est unique. Il est compté exactement 1 fois dans la somme $\sum_x \delta^+(x)$ (pour $\delta^+(u)$), donc $\sum_x \delta^+(x) = \mid E \mid$.

Pour un graphe, chaque arête $uv$ est unique et est comptée 2 fois dans la somme $\sum_x \delta(x)$ (une fois pour $\delta(u)$ et une fois pour $\delta(v)$), donc $\sum_x \delta^+(x) = 2 \mid E \mid$.

Isomorphismes de graphes

Deux graphes sont isomorphes s'ils sont identique au noms de leurs sommets prêt. Formalisons cette intuition :

Définition

Deux graphes $G = (V, E)$ et $G' = (V', E')$ sont isomorphes s'il existe une bijection $f: V\to V'$ telle que $xy \in E$ si et seulement si $f(x)f(y) \in E'$.

La fonction $f$ est appelé isomorphisme entre $G$ et $G'$.

La notion d'isomorphisme se généralise directement à des graphes orienté ou à des multigraphes.

Cela revient à regarder un graphe juste structurellement, sans noms de sommets :

iso sans noms

La relation d'isomorphisme est une relation d'équivalence entre les graphes : si $G$ est isomorphe à $G'$ qui est isomorphe à $G''$ alors $G$ est isomorphe à $G''$. Deux graphes isomorphes auront les mêmes propriétés (puisqu'ils sont structurellement identiques !) :

même nombre de sommets et d'arêtes,
connectivité,
même cliques, stables
...

Notez que le fait que $f$ soit une bijection est important ! Les deux graphes ci-dessous ne sont en effet pas identiques aux sommets prêt mais $xy \in E$ si et seulement si $f(x)f(y) \in E'$ :

non

Savoir si deux graphes sont isomorphes n'est pas toujours un problème simple !

Par exemple en considérant les 3 graphes ci dessous :

iso graphes

Il est clair de voir que les 2 premiers sont isomorphes ($f(a) = 1$, $f(b) = 2$, $f(c) = 4$ et $f(d) = 3$) alors que le troisième ne l'est pas.

Mais c'est moins clair avec les deux suivants :

Petesen iso

Montrez que les deux graphes précédents sont isomorphes

corrigé

Le graphe en question est le graphe de Petersen, que l'on peut représenter de plein de jolis façons : https://mathworld.wolfram.com/PetersenGraph.html.

Petesen iso

C'est pourquoi lorsque l'on énumère des graphes on le fera la plupart du temps à sommets fixés et 2 automorphismes du même graphe seront alors considérés comme différents.

Enfin, on peut chercher les isomorphismes entre un graphe et lui-même. Il en existe toujours au moins un puisque la fonction identité marchera toujours.

Définition

Un isomorphisme d'un graphe dans lui-même est appelé automorphisme.

Attention, ne confonde pas isomorphe, isomorphisme et automorphisme :

iso et automorphisme

Les 3 graphes $G_1$, $G_2$ et $G_3$ sont isomorphes (nous n'avons que renuméroté les sommets entre eux), mais seuls $G_1$ et $G_3$ sont automorphes par l'automorphisme qui échange $A$ et $C$. En effet, le graphe $G_2$ n'est pas le graphe $G_1$ puisque le degré de son sommet $B$ vaut 2 : leurs ensembles d'arêtes sont différents.

À retenir

un isomorphisme change le nom des sommets (si les sommets sont les même être les graphes de de départ et d'arrivée, les arêtes peuvent être différentes),
un automorphisme cherche les symétries dans un graphe (le graphe d'arrivée est le même que le graphe de départ (sommets et arêtes)).