Observations sur les graphes

Adjacence

  • Deux sommets sont adjacents (ou voisins) s’ils sont joints par un arc.
  • Deux arcs sont adjacents (ou voisins) s’ils ont au moins une extrémité commune.

Degrés

  • Le demi-degré extérieur de $x_i$, noté $d^+(x_i)$, est le nombre d’arcs ayant $x_i$ comme extrémité initiale. Donc $d^+(x_i) = |W^+(x_i)|$.
  • Le demi-degré intérieur de $x_i$, noté $d^-(x_i)$, est le nombre d’arcs ayant $x_i$ comme extrémité finale. Donc $d^-(x_i) = |W^-(x_i)|$.
  • Le degré de $x_i$ est noté $d(x_i) = d^+(x_i) + d^-(x_i)$.
  • Pour un graphe non orienté, le degré d’un sommet est le nombre d’arêtes qui lui sont incidentes.
  • Dans un 1-graphe, on peut définir le degré d’un sommet via l’application multivoque $\Gamma$ puisque $|W^+(x_i)| = Card(\Gamma^+(x_i))$ et $|W^-(x_i)| = Card(\Gamma^-(x_i))$.
  • Une boucle augmente de deux unités le degré du sommet concerné.

Une propriété fondamentale découle directement de ces définitions : la somme des degrés de tous les sommets d’un graphe est égale à deux fois le nombre d’arcs (ou d’arêtes), car chaque arc contribue exactement une unité au degré sortant de son origine et une unité au degré entrant de sa destination. Il en découle également qu’un graphe simple possède toujours un nombre pair de sommets de degré impair.

On peut aussi définir le degré d’un graphe comme le degré maximum parmi tous ses sommets. Un graphe est dit $k$-régulier si tous ses sommets ont le même degré $k$.

Exemple

graph LR X1((X1)) X3((X3)) --> X3 X4((X4)) --> X3 X2((X2)) --> X4 X3 --> X1 X2 --> X1 X2 --> X4 X4 --> X2 X4 --> X1

Demi-degrés et degré de chaque sommet :

Sommet $d^+(x_i)$ $d^-(x_i)$ $d(x_i)$
$x_1$ $2$ $3$ $5$
$x_2$ $3$ $1$ $4$
$x_3$ $2$ $2$ $4$
$x_4$ $2$ $3$ $5$

On peut vérifier : $\sum d^+(x_i) = \sum d^-(x_i) = 1+3+2+1 = 7$, ce qui correspond bien au nombre total d’arcs du graphe (en comptant la boucle de $x_3$ comme un arc).

Graphe complémentaire

Deux graphes sont complémentaires si aucun arc (ou aucune arête) n’est commun et si leur union donne un graphe complet. Formellement :

  • Soit un graphe $G = (X, U)$
  • Alors il existe $\overline{G} = (X, \overline{U})$ le graphe complémentaire de $G$
  • $(x_i, x_j) \in U \Rightarrow (x_i, x_j) \notin \overline{U}$
  • $(x_i, x_j) \notin U \Rightarrow (x_i, x_j) \in \overline{U}$

Autrement dit, le graphe complémentaire $\overline{G}$ possède exactement les arcs que $G$ ne possède pas. L’union de $G$ et $\overline{G}$ reconstitue le graphe complet sur le même ensemble de sommets.

Exemple

Graphe complet

graph LR X1((X1)) X2((X2)) X3((X3)) X4((X4)) X5((X5)) X1 --> |u_1| X2 X2 --> |u_2| X4 X2 --> |u_3| X5 X2 --> |u_4| X3 X1 --> |u_5| X4 X1 --> |u_6| X5 X1 --> |u_7| X3 X5 --> |u_8| X1 X4 --> |u_9| X3 X4 --> |u_10| X5 X3 --> |u_11| X5

Graphe partiel

graph LR X1((X1)) X2((X2)) X3((X3)) X4((X4)) X5((X5)) X1 --> |u_1| X2 X2 --> |u_2| X4 X1 --> |u_6| X5 X4 --> |u_9| X3 X4 --> |u_10| X5

Graphe complémentaire

graph LR X1((X1)) X2((X2)) X3((X3)) X4((X4)) X5((X5)) X2 --> |u_3| X5 X2 --> |u_4| X3 X1 --> |u_5| X4 X1 --> |u_7| X3 X5 --> |u_8| X1 X3 --> |u_11| X5

On vérifie bien que l’ensemble des arcs du graphe partiel et l’ensemble des arcs du graphe complémentaire sont disjoints, et que leur réunion redonne exactement l’ensemble des arcs du graphe complet.

Graphe partiel

Un graphe partiel de $G = (X, U)$ est un graphe $G' = (X, U')$ obtenu en conservant tous les sommets de $G$ et en ne gardant qu’un sous-ensemble de ses arcs : $U' \subseteq U$. Autrement dit, on obtient un graphe partiel en supprimant un ou plusieurs arcs du graphe initial, sans toucher à ses sommets.

Cette notion est utile lorsque l’on souhaite étudier l’effet de la suppression de certaines liaisons dans un réseau (par exemple : que se passe-t-il si on coupe certaines routes dans un réseau routier, ou certains câbles dans un réseau informatique ?).

Remarque : un graphe partiel est aussi appelé sous-graphe couvrant (spanning subgraph en anglais), car il « couvre » tous les sommets du graphe d’origine.

Exemple

Soit le graphe $G$ suivant :

graph LR A((A)) B((B)) C((C)) D((D)) A --> B A --> C B --> C B --> D C --> D D --> A

Un graphe partiel $G'$ de $G$ (on supprime les arcs $(A,C)$ et $(C,D)$) :

graph LR A((A)) B((B)) C((C)) D((D)) A --> B B --> C B --> D D --> A

Tous les sommets de $G$ sont conservés ; seuls certains arcs ont été retirés.

Sous-graphe

Un sous-graphe (ou sous-graphe induit) de $G = (X, U)$ est un graphe $G' = (X', U')$ obtenu en sélectionnant un sous-ensemble de sommets $X' \subseteq X$ et en ne conservant que les arcs dont les deux extrémités appartiennent à $X'$ :

$$U' = \{(x_i, x_j) \in U \mid x_i \in X' \text{ et } x_j \in X'\}$$

Contrairement au graphe partiel, c’est ici le choix des sommets qui détermine les arcs conservés : on garde automatiquement tous les arcs reliant les sommets sélectionnés, et on perd tous les arcs incidents à un sommet retiré.

Exemple

En reprenant le graphe $G$ précédent, le sous-graphe induit par $X' = \{A, B, C\}$ est :

graph LR A((A)) B((B)) C((C)) A --> B A --> C B --> C

Le sommet $D$ a été retiré, et avec lui tous les arcs incidents ($B \to D$, $C \to D$, $D \to A$).

Sous-graphe partiel

Un sous-graphe partiel de $G$ est un graphe partiel d’un sous-graphe de $G$. On cumule les deux opérations : on retire d’abord certains sommets (et les arcs incidents), puis on retire éventuellement certains des arcs restants.

Formellement, $G'' = (X', U'')$ est un sous-graphe partiel de $G = (X, U)$ si :

  • $X' \subseteq X$
  • $U'' \subseteq \{(x_i, x_j) \in U \mid x_i \in X' \text{ et } x_j \in X'\}$

Tout sous-graphe induit est donc un sous-graphe partiel (cas particulier où l’on ne retire aucun arc supplémentaire), mais la réciproque n’est pas vraie.

Exemple

En reprenant le même graphe $G$, un sous-graphe partiel avec $X' = \{A, B, C\}$ et suppression de l’arc $(A,C)$ :

graph LR A((A)) B((B)) C((C)) A --> B B --> C

On a retiré le sommet $D$ (sous-graphe) puis l’arc $(A,C)$ (graphe partiel du sous-graphe).

Récapitulatif

Opération Sommets Arcs
Graphe partiel Tous conservés Sous-ensemble de $U$
Sous-graphe (induit) Sous-ensemble $X' \subseteq X$ Tous les arcs entre sommets de $X'$
Sous-graphe partiel Sous-ensemble $X' \subseteq X$ Sous-ensemble des arcs entre sommets de $X'$

Propriétés de certains graphes

Les propriétés suivantes permettent de classifier les graphes selon la nature de leurs arcs et les contraintes qu’ils respectent. Chaque propriété est définie formellement et illustrée par un exemple.

Graphe réflexif

  • Tous les sommets comportent une boucle.
  • $\forall x_i \in X, (x_i,x_i) \in U$
graph LR A((A)) --> A B((B)) --> B C((C)) --> C A --> B B --> C C --> A

Graphe irréflexif

  • Aucune boucle.
  • $\forall x_i \in X, (x_i,x_i) \not\in U$
graph LR A((A)) B((B)) C((C)) A --> B B --> C C --> A

Graphe symétrique

  • Tout sommet lié à un autre l’est dans les deux sens.
  • $\forall x_i,x_j \in X, (x_i,x_j) \in U \Rightarrow (x_j,x_i) \in U$
graph LR A((A)) B((B)) C((C)) A --> B B --> A B --> C C --> B C --> A A --> C A --> A B --> B C --> C

Un graphe symétrique correspond naturellement à un graphe non orienté : chaque paire d’arcs réciproques $(x_i, x_j)$ et $(x_j, x_i)$ peut être remplacée par une arête $\{x_i, x_j\}$.

Graphe asymétrique

  • Pas plus d’un arc entre deux sommets, pas de boucle.
  • $\forall x_i,x_j \in X, (x_i,x_j) \in U \Rightarrow (x_j,x_i) \not\in U$

L’asymétrie implique l’irréflexivité : si un graphe est asymétrique, il ne peut contenir de boucle (car une boucle $(x_i, x_i)$ impliquerait $(x_i, x_i) \in U$ et $(x_i, x_i) \in U$ simultanément, ce qui contredirait la condition).

Graphe antisymétrique

  • Pas plus d’un arc entre deux sommets distincts, boucle possible.
  • $\forall x_i,x_j \in X, x_i \ne x_j, (x_i,x_j) \in U \Rightarrow (x_j,x_i) \not\in U$

La différence avec l’asymétrie est subtile : l’antisymétrie autorise les boucles (car la condition ne s’applique qu’aux paires de sommets distincts), tandis que l’asymétrie les interdit.

Graphe transitif

  • S’il existe un chemin $x_i \rightarrow x_j \rightarrow x_k$, alors il existe aussi $x_i \rightarrow x_k$.
  • $\forall x_i,x_j,x_k \in X, (x_i,x_j) \in U \land (x_j,x_k) \in U \Rightarrow (x_i,x_k) \in U$
  • chaque chemin de longueur 2 possède une arête directe équivalente.

La transitivité est une propriété forte qui, combinée à la réflexivité et à la symétrie, définit une relation d’équivalence. Combinée à la réflexivité et à l’antisymétrie, elle définit une relation d’ordre (partiel).
Voici le même format, avec de courts paragraphes explicatifs pour chaque cas.

exemples transitif

Un cas classique : si A → B et B → C, alors A → C est présent.
La condition de transitivité est respectée.

graph LR A --> B B --> C A --> C

Cycle à deux sommets avec boucles réflexives.
Les compositions A → B → A et B → A → B donnent respectivement A → A et B → B, qui existent déjà.

graph LR A --> B B --> A A --> A B --> B

Chaîne totalement fermée transitivement.
Chaque sommet possède une flèche vers tous les sommets suivants, donc toute composition de chemins existe déjà dans la relation.

graph LR A --> B A --> C A --> D A --> E B --> C B --> D B --> E C --> D C --> E D --> E

exemples non-transtifs

Cycle simple entre A et B.
La transitivité exigerait A → A et B → B, qui sont absents.

graph LR A --> B B --> A

On a A → B et B → A, donc il faudrait B → B.
Comme cette boucle manque, la relation n’est pas transitive.

graph LR A --> B B --> A A --> A

Cycle à trois sommets.
Par exemple A → B et B → C devraient impliquer A → C, qui n’existe pas.

graph LR A --> B B --> C C --> A

Chaîne simple.
La transitivité impose A → C, qui n’est pas présent.

graph LR A --> B B --> C

Chaîne longue avec un raccourci A → E.
Mais il manque encore plusieurs relations comme A → C, B → D ou C → E, donc la relation n’est pas transitive.

graph LR A --> B B --> C C --> D D --> E A --> E

Graphe complet

  • Aucun sommet isolé ; pour toute paire de sommets distincts, au moins un arc existe entre eux.
  • $\forall x_i,x_j \in X, x_i \ne x_j, (x_i,x_j) \not\in U \Rightarrow (x_j,x_i) \in U$

Dans un graphe complet non orienté à $n$ sommets, le nombre d’arêtes est $\frac{n(n-1)}{2}$.

Graphe simple

  • Tous les arcs sont distincts et il n’y a pas de boucle.

Clique

  • Sous-graphe $\tilde G = (\tilde X, \tilde E)$ tel que tout couple de sommets distincts de $\tilde X$ est relié par un arc ou une arête de $\tilde E$.

Une clique est donc un sous-graphe complet du graphe d’origine. La recherche de la clique de taille maximale dans un graphe est un problème NP-complet classique en informatique.

Dans l’exemple ci-dessous : La clique est le triangle formé par $A, B, C$ (toutes les paires sont reliées).

graph LR A((A)) --- B((B)) A --- C((C)) B --- C A --- D((D))

Tournoi

  • Graphe complet et asymétrique.

Un tournoi modélise typiquement une compétition où chaque paire de joueurs s’affronte exactement une fois et où il y a toujours un vainqueur (pas de match nul). Le nombre d’arcs dans un tournoi à $n$ sommets est exactement $\frac{n(n-1)}{2}$.

Dans l’exemple ci-dessous : Pour chaque paire {1,2,3,4}, il y a exactement un arc dans un seul sens.

graph LR 1((1)) --> 2((2)) 1 --> 3((3)) 4((4)) --> 1 2 --> 3 2 --> 4 3 --> 4

Chaînes, chemins et cycles

Chemins élémentaires

Dans un graphe orienté, une chaîne (ou chemin) de longueur $k$ est une suite alternée $(x_0,u_1,x_1,\dots ,u_k,x_k)$ telle que chaque arc $u_i=(x_{i-1},x_i)$ appartienne à $U$. Un chemin est élémentaire si aucun sommet n’y apparaît deux fois (et donc aucun arc non plus). On parle de chemin simple dans un graphe non orienté lorsque chaque arête est empruntée au plus une fois. Cette représentation informatique est particulièrement utilisée sous la forme de Single linked list.

graph LR A((A)) B((B)) C((C)) D((D)) E((E)) A --> B B --> C C --> D D --> E

La longueur d’un chemin est le nombre d’arcs qui le composent. Dans l’exemple ci-dessus, le chemin $(A, B, C, D, E)$ est de longueur 4. La distance entre deux sommets $x_i$ et $x_j$ dans un graphe est la longueur du plus court chemin reliant $x_i$ à $x_j$ (si un tel chemin existe).

Cycles et circuits

Un cycle (non orienté) est un chemin simple dont l’extrémité finale coïncide avec l’origine ; on parle de circuit dans le cas orienté. Cette représentation informatique est particulièrement utilisée sous la forme de Circular linked list.

  • Un graphe sans cycle est dit acyclique ; dans le cas non orienté, un tel graphe est une forêt
  • La plus petite longueur d’un cycle est la maille, la plus grande la circonférence
graph LR A((A)) B((B)) C((C)) D((D)) A --> B B --> C C --> D D --> A

Dans l’exemple ci-dessus, le circuit $(A, B, C, D, A)$ est de longueur 4. Il s’agit d’un circuit élémentaire puisque aucun sommet intermédiaire n’est visité deux fois. Un graphe orienté acyclique (sans aucun circuit) est souvent désigné par l’acronyme DAG (Directed Acyclic Graph), structure que l’on retrouve par exemple dans Git ou dans les réseaux de planification de tâches. La présence d’un cycle dans ces cas la démontre une contradiction.

La maille (girth en anglais) d’un graphe est la longueur de son cycle le plus court. La circonférence (circumference) est la longueur de son cycle le plus long. Ces deux notions ne concernent pas un cycle en particulier, mais le graphe dans son ensemble : on cherche, parmi tous les cycles du graphe, celui qui a le moins d’arêtes (maille) et celui qui en a le plus (circonférence).

Dans le graphe ci-dessous :

  • 3 arêtes : c’est le cycle le plus court => c’est la maille.
  • 4 arêtes : c’est le cycle le plus long => c’est la circonférence.
graph LR A((A)) --- B((B)) B --- C((C)) C --- A C --- D((D)) D --- E((E)) E --- B

Connexité

Un graphe non orienté est dit connexe si, pour toute paire de sommets $(x_i, x_j)$, il existe une chaîne reliant $x_i$ à $x_j$. Si le graphe n’est pas connexe, il se décompose en composantes connexes : ce sont les sous-graphes connexes maximaux.

Pour un graphe orienté, on distingue :

  • la connexité faible : le graphe est connexe si l’on ignore l’orientation des arcs ;
  • la connexité forte : pour toute paire de sommets $(x_i, x_j)$, il existe un chemin orienté de $x_i$ à $x_j$ et un chemin orienté de $x_j$ à $x_i$.

Les composantes fortement connexes d’un digraphe sont les sous-graphes maximaux vérifiant la connexité forte. Leur identification est un problème classique résolu par des algorithmes comme celui de Tarjan ou de Kosaraju.

Arbres et forêts

Un arbre est un graphe non orienté, connexe et sans cycle. Un ensemble disjoint d’arbres forme une forêt.

Propriétés équivalentes pour un graphe $G=(X,E)$ à $n$ sommets :

  1. $G$ est un arbre ;
  2. $G$ est connexe et $|E|=n-1$ ;
  3. $G$ est acyclique et $|E|=n-1$.

Ces trois caractérisations sont fondamentales : elles signifient qu’un arbre est le graphe connexe minimal (retirer une arête le déconnecte) et le graphe acyclique maximal (ajouter une arête crée un cycle).

Arbre : Cette représentation informatique est particulièrement utilisée sous la forme de BST en y associant des propriétés sur les valeurs des nœuds et des fils droits et gauches par rapport à la valeur du nœud parent. Voir cours sur les structure de données.

graph TD A((A)) --- B((B)) A --- C((C)) B --- D((D)) B --- E((E)) C --- F((F)) C --- G((G))

On peut vérifier la propriété $|E| = n - 1$ : ce graphe possède 7 sommets et 6 arêtes.

Forêt :

graph TD %% Arbre 1 A1((A1)) --- B1((B1)) A1 --- C1((C1)) B1 --- D1((D1)) %% Arbre 2 A2((A2)) --- B2((B2)) A2 --- C2((C2)) %% Arbre 3 A3((A3)) --- B3((B3))

Cette forêt est composée de trois arbres disjoints. Elle possède 9 sommets et 6 arêtes. De manière générale, une forêt à $n$ sommets et $k$ composantes connexes possède exactement $n - k$ arêtes.