---
title: "Théorie des graphes"
date: "2025-05-16"
---

# Les graphes

\Huge

Les graphes

# Les graphes! Historique

**Un mini-peu d'histoire...**

## L. Euler et les 7 ponts de Koenigsberg:

* Existe-t-il une promenade sympa, passant **une seule fois** par les 7 ponts et revenant au point de départ?

![Les ponts, c'est beau. Source: Wikipédia, <https://bit.ly/37h0yOG>](figs/Konigsberg_bridges.png){width=40%}

. . .

* Réponse: ben non!

# Utilisation quotidienne

## Réseau social

![Source: Wikipedia, <https://bit.ly/3kG6cgo>](figs/Social_Network.svg){width=40%}

* Chaque sommet est un individu.
* Chaque trait une relation d'amitié.
* Miam, Miam, Facebook.

# Utilisation quotidienne

## Moteurs de recherche

![Source: Wikipedia, <https://bit.ly/3kG6cgo>](figs/PageRanks-Example.svg){width=40%}

* Site est un sommet.
* Liens sortants.
* Liens entrants.
* Notion d'importance d'un site: combien de liens entrants, pondérés par l'importance du site.
* Miam, Miam, Google (PageRank).

# Introduction

## Définition, plus ou moins

* Un graphe est un ensemble de sommets, reliés par des lignes ou des flèches.

![Deux exemples de graphes.](figs/ex_graphes.png)

* Des sommets (numérotés 1 à 6);
* Connectés ou pas par des traits ou des flèches!

# Généralités

## Définitions

* Un **graphe** $G(V, E)$ est constitué
    * $V$: un ensemble de sommets;
    * $E$: un ensemble d'arêtes.
* Une **arête** relie une **paire** de sommets de $V$.

## Remarques

* Il y a **au plus** une arête $E$ par paire de sommets de $V$.
* La **complexité** d'un algorithme dans un graphe se mesure en terme de $|E|$ et $|V|$, le nombre d'éléments de $E$ et $V$ respectivement.

# Généralités

## Notations

* Une arête d'un graphe **non-orienté** est représentée par une paire **non-ordonnée** $(u,v)=(v,u)$, avec $u,v\in V$.
* Les arêtes ne sont pas orientées dans un graphe non-orienté 
(elles sont bi-directionnelles, c.-à-d. peuvent être parcourues dans n'importe quel sens).

## Exemple


::: columns

:::: column

![Un graphe non-orienté.](figs/ex_graphe_non_oriente.svg)


::::

:::: column

## Que valent $V$, $|V|$, $E$, et $|E|$?

. . .

\begin{align*}
V&=\{1, 2, 3, 4\},\\
|V|&=4,\\
E&=\{(1,2),(2,3),(2,4),(4,1)\},\\
|E|&=4.
\end{align*}

::::

:::

# Généralités

## Notations

* Une arête d'un graphe **orienté** est représentée par une paire **ordonnée** $(u,v)\neq(v,u)$, avec $u,v\in V$.
* Les arêtes sont orientées dans un graphe orienté (étonnant non?).

## Exemple


::: columns

:::: column

![Un graphe orienté.](figs/ex_graphe_oriente.svg)


::::

:::: column

## Que valent $V$, $|V|$, $E$, et $|E|$?

. . .

\begin{align*}
V&=\{1, 2, 3, 4\},\\
|V|&=4,\\
E&=\{(1,2),(2,3),(2,4),(4,1),(4,2)\},\\
|E|&=5.
\end{align*}

::::

:::

# Généralités

## Définition

* Le somme $v$ est **adjacent** au sommet $u$, si et seulement si $(u,v)\in E$;
* Si un graphe non-orienté contient une arête $(u,v)$, $v$ est adjacent à $u$ et $u$ est adjacent à $v$.

## Exemple

::: columns

:::: column

![Sommet $a$  adjacent à $c$, $c$ adjacent à $a$.](figs/ex_adj_non_or.svg){width=60%}

::::

:::: column

![Sommet $c$  adjacent à $a$.](figs/ex_adj_or.svg){width=60%}

::::

:::

# Généralités

## Définition

* Un **graphe pondéré** ou **valué** est un graphe dont chaque arête a un
  poids associé, habituellement donné par une fonction de pondération $w:E\rightarrow\mathbb{R}$.

## Exemples

![Graphe pondéré orienté (gauche) et non-orienté (droite).](figs/ex_graph_pond.pdf){width=80%}


# Généralités

## Définition

* Dans un graphe $G(V,E)$, une **chaîne** reliant un sommet $u$ à un sommet $v$ est une suite d'arêtes entre les sommets, $w_0$, $w_1$, ..., $w_k$, telles que 
$$
(w_i, w_{i+1})\in E,\quad u=w_0,\quad v=w_k,\quad \mbox{pour }0\leq i< k,
$$
avec $k$ la longueur de la chaîne (le nombre d'arêtes du chemin).

## Exemples

![Illustration d'une chaîne dans un graphe.](figs/ex_graphe_chaine.pdf){width=80%}

# Généralités

## Définition

* Une **chaîne élémentaire** est une chaîne dont tous les sommets sont distincts, sauf les extrémités qui peuvent être égales.

## Exemples

![Illustration d'une chaîne élémentaire dans un graphe.](figs/ex_graphe_chaine_elem.pdf){width=80%}

# Généralités

## Définition

* Une **boucle** est une arête $(v,v)$ d'un sommet vers lui-même.

## Exemples

![Illustration d'une boucle dans un graphe.](figs/ex_graphe_boucle.pdf){width=40%}

# Généralités

## Définition

* Un graphe non-orienté est dit **connexe**, s'il existe un chemin reliant n'importe quelle paire de sommets distincts.

## Exemples

\

::: columns

:::: column

![Graphe connexe. Source: Wikipédia, <https://bit.ly/3yiUzUv>](figs/graphe_connexe.svg){width=60%}

::::

:::: column
![Graphe non-connexe avec composantes connexes. Source: Wikipédia, <https://bit.ly/3KJB76d>](figs/composantes_connexes.svg){width=40%}

::::

:::

# Généralités

## Définition

* Un graphe orienté est dit **fortement connexe**, s'il existe un chemin reliant n'importe quelle paire de sommets distincts.

## Exemples

\

::: columns

:::: column

![Graphe fortement connexe.](figs/ex_graph_fort_connexe.pdf){width=60%}

::::

:::: column

![Composantes fortement connexes. Source, Wikipédia: <https://bit.ly/3w5PL2l>](figs/composantes_fortement_connexes.svg){width=100%}

::::

:::

# Généralités

## Définition

* Un **cycle** dans un graphe *non-orienté* est une chaîne de longueur $\geq 3$ telle que le 1er sommet de la chaîne est le même que le dernier, et dont les arêtes sont distinctes.
* Pour un graphe *orienté*, on parle de **circuit**.
* Un graphe sans cycles est dit **acyclique**.

## Exemples

![Illustration de cycles.](figs/ex_graphe_cycle.pdf){width=100%}

# Question de la mort

* Qu'est-ce qu'un graphe connexe acyclique?

. . .

* Un arbre!

# Représentations

* La complexité des algorithmes sur les graphes s'expriment en fonction du nombre de sommets $V$, et du nombre d'arêtes $E$:
    * Si $|E|\sim |V|^2$, on dit que le graphe est **dense**.
    * Si $|E|\sim |V|$, on dit que le graphe est **peu dense**.
* Selon qu'on considère des graphes denses ou peu denses, différentes structures de données peuvent être envisagées.

## Question

* Comment peut-on représenter un graphe informatiquement? Des idées (réflexion de quelques minutes)?

. . .

* Matrice/liste d'adjacence.

# Matrice d'adjacence

* Soit le graphe $G(V,E)$, avec $V=\{1, 2, 3, ..., n\}$;
* On peut représenter un graphe par une **matrice d'adjacence**, $A$, de dimension $n\times n$ définie par
$$
A_{ij}=\left\{ \begin{array}{ll}
         1 & \mbox{si } i,j\in E,\\
         0 & \mbox{sinon}.
         \end{array} \right.
$$


::: columns

:::: column

## Exemple

```{.mermaid format=pdf width=400 loc=figs/}
graph LR;
    1---2;
    1---4;
    2---5;
    4---5;
    5---3;
```

::::

:::: column

\footnotesize

## Quelle matrice d'adjacence? 

. . .

```
   || 1 | 2 | 3 | 4 | 5
===||===|===|===|===|===
 1 || 0 | 1 | 0 | 1 | 0
---||---|---|---|---|---
 2 || 1 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 3 || 0 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 4 || 1 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 5 || 0 | 1 | 1 | 1 | 0
```

::::

:::

# Matrice d'adjacence

## Remarques

* Zéro sur la diagonale.
* La matrice d'un graphe non-orienté est symétrique

$$
A_{ij}=A_{ji}, \forall i,j\in[1,n]
$$.

::: columns

:::: column

```{.mermaid format=pdf width=400 loc=figs/}
graph LR;
    1---2;
    1---4;
    2---5;
    4---5;
    5---3;
```

::::

:::: column

\footnotesize

```
   || 1 | 2 | 3 | 4 | 5
===||===|===|===|===|===
 1 || 0 | 1 | 0 | 1 | 0
---||---|---|---|---|---
 2 || 1 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 3 || 0 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 4 || 1 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 5 || 0 | 1 | 1 | 1 | 0
```

::::

:::

# Matrice d'adjacence

* Pour un graphe orienté (digraphe)

::: columns

:::: column

## Exemple

```{.mermaid format=pdf width=400 loc=figs/}
graph LR;
    2-->1;
    1-->4;
    2-->5;
    5-->2;
    4-->5;
    5-->3;
```

::::

:::: column

\footnotesize

## Quelle matrice d'adjacence? 

. . .

```
   || 1 | 2 | 3 | 4 | 5
===||===|===|===|===|===
 1 || 0 | 0 | 0 | 1 | 0
---||---|---|---|---|---
 2 || 1 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 3 || 0 | 0 | 0 | 0 | 0
---||---|---|---|---|---
 4 || 0 | 0 | 0 | 0 | 1
---||---|---|---|---|---
 5 || 0 | 1 | 1 | 0 | 0
```

::::

:::

* La matrice d'adjacence n'est plus forcément symétrique
$$
A_{ij}\neq A_{ji}.
$$

# Stockage

* Quel est l'espace nécessaire pour stocker une matrice d'adjacence pour un graphe orienté?

. . .

* $\mathcal{O}(|V|^2)$
* Quel est l'espace nécessaire pour stocker une matrice d'adjacence pour un graphe non-orienté?

. . .

* $\mathcal{O}\left((|V|-1)|V|/2\right)$.

# Considérations d'efficacité

* Dans quel type de graphes la matrice d'adjacence est-elle utile?

. . .

* Dans les graphes denses.
* Pourquoi?

. . .

* Dans les graphes peu denses, la matrice d'adjacence est essentiellement composée de `0`.

## Remarque

* Dans la majorité des cas, les grands graphes sont peu denses.
* Comment représenter un graphe autrement?

# La liste d'adjacence (non-orienté)

* Pour chaque sommet $v\in V$, stocker les sommets adjacents à $v$.
* Quelle structure de données pour la liste d'adjacence?

. . .

* Tableau de liste chaînée, vecteur (tableau dynamique), etc.


::: columns

:::: column

## Exemple

![Un graphe non-orienté.](figs/ex_graph_adj.pdf){width=80%}

::::

:::: column


## Quelle liste d'adjacence? 

. . .

![La liste d'adjacence.](figs/ex_graph_list_adj.pdf)


::::

:::

# La liste d'adjacence (orienté)


::: columns

:::: column

## Quelle liste d'adjacence pour...

* Matrix (2min)

```{.mermaid format=pdf width=400 loc=figs/}
graph LR;
    0-->1;
    0-->2;
    1-->2;
    3-->0;
    3-->1;
    3-->2;
```

::::

:::: column

```











```


::::

:::

# Complexité

## Stockage

* Quelle espace est nécessaire pour stocker une liste d'adjacence (en fonction de $|E|$ et $|V|$)?

. . .

$$
\mathcal{O}(|V|+|E|)
$$

* Pour les graphes *non-orientés*: $\mathcal{O}(|V|+2|E|)$.
* Pour les graphes *orientés*: $\mathcal{O}(|V|+|E|)$.

## Définition

* Le **degré** d'un sommet $v$, est le nombre d'arêtes incidentes du sommet (pour les graphes orientés on a un degré entrant ou sortant).
* Comment retrouve-t-on le degré de chaque sommet avec la liste d'adjacence?

. . .

* C'est la longueur de la liste chaînée si le graphe est non-orienté.


# Parcours

* Beaucoup d'applications nécessitent de parcourir des graphes:
    * trouver un chemin d'un sommet à un autre;
    * trouver si le graphe est connexe.
* Il existe *deux* parcours principaux:
    * en largeur (Breadth-First Search);
    * en profondeur (Depth-First Search).
* Ces parcours créent *un arbre* au fil de l'exploration (si le graphe est non-connexe, cela crée une *forêt*, c.-à-d. un ensemble d'arbres).

# Illustration: parcours en largeur

![Le parcours en largeur.](figs/parcours_larg.pdf){width=80%}

# Exemple

## Étape par étape (blanc non-visité)

![Initialisation.](figs/parcours_larg_0.pdf){width=50%}

## Étape par étape (gris visité)

![On commence en `x`.](figs/parcours_larg_1.pdf){width=50%}

# Exemple

## Étape par étape

![On commence en `x`.](figs/parcours_larg_1.pdf){width=50%}

## Étape par étape (vert à visiter)

![Visiter `w`, `t`, `y`.](figs/parcours_larg_2.pdf){width=50%}

# Exemple

## Étape par étape

![Visiter `w`, `t`, `y`.](figs/parcours_larg_2.pdf){width=50%}

## Étape par étape

![`w`, `t`, `y` visités. `u`, `s` à visiter.](figs/parcours_larg_3.pdf){width=50%}

# Exemple

## Étape par étape

![`w`, `t`, `y` visités. `u`, `s` à visiter.](figs/parcours_larg_3.pdf){width=50%}

## Étape par étape

![`u`, `s`, visités. `r` à visiter.](figs/parcours_larg_4.pdf){width=50%}

# Exemple

## Étape par étape

![`u`, `s`, visités. `r` à visiter.](figs/parcours_larg_4.pdf){width=50%}

## Étape par étape

![`r` visité. `v` à visiter.](figs/parcours_larg_5.pdf){width=50%}

# Exemple

## Étape par étape

![`r` visité. `v` à visiter.](figs/parcours_larg_5.pdf){width=50%}

## Étape par étape

![The end. Plus rien à visiter!](figs/parcours_larg_6.pdf){width=50%}

# En faisant ce parcours...


::: columns

:::: column

## Du parcours de l'arbre

![](figs/parcours_larg_6.pdf){width=100%}

::::

:::: column

## Quel arbre est créé par le parcours (2min)?

. . .

```{.mermaid format=pdf width=400 loc=figs/}
graph LR;
    0[x]-->1[w];
    0-->2[t];
    0-->3[y];
    2-->9[u];
    1-->4[s];
    4-->5[r];
    5-->6[v];
```

::::

:::

## Remarques

* Le parcours dépend du point de départ dans le graphe.
* L'arbre sera différent en fonction du noeud de départ, et de l'ordre de parcours des voisins d'un noeud.

# Le parcours en largeur

## L'algorithme, idée générale (3min, matrix)?

. . .

```C
v = un sommet du graphe
i = 1
pour sommet dans graphe et sommet non-visité
    visiter(v, sommet, i) // marquer sommet à distance i visité 
    i += 1
```

## Remarque

* `i` est la distance de plus court chemin entre `v` et les sommets en cours de visite.


# Le parcours en largeur

## L'algorithme, pseudo-code (3min, matrix)?

* Comment garder la trace de la distance?

. . .

* Utilisation d'une **file d'attente**

. . .

```C
initialiser(graphe) // tous sommets sont non-visités
visiter(sommet, file) // on choisit un sommet de départ 
tant que !est_vide(file)
    défiler(file, (v,u))
    si u != visité
        ajouter (v,u) à l'arbre T
        visiter(u, file)
```

## Que fait visiter?

```
rien visiter(x, file)
    marquer x comme visité
    pour chaque arête (x,w)
        si w != visité
            enfiler(file, (x,w))
```

# Exercice (5min)

## Appliquer l'algorithme sur le graphe

![](figs/parcours_larg_0.pdf){width=50%}

* En partant de `v`, `s`, ou `u` (par colonne de classe).
* Bien mettre à chaque étape l'état de la file.

# Complexité du parcours en largeur

## Étape 1

* Extraire un sommet de la file.

## Étape 2

* Traîter tous les sommets adjacents.

## Quelle est la complexité?

. . .

* Étape 1: $\mathcal{O}(|V|)$
* Étape 2: $\mathcal{O}(2|E|)$
* Total: $\mathcal{O}(|V| + |2|E|)$

# Exercice

* Établir la liste d'adjacence et appliquer l'algorithme de parcours en largeur au graphe

```{.mermaid format=pdf width=400 loc=figs/}
graph LR;
    1---2;
    1---3;
    1---4;
    2---3;
    2---6;
    3---6;
    3---4;
    3---5;
    4---5;
```


# Illustration: parcours en profondeur

![Le parcours en profondeur. À quel parcours d'arbre cela ressemble-t-il?](figs/parcours_prof.pdf){width=80%}

# Parcours en profondeur

## Idée générale

* Initialiser les sommets comme non-lus
* Visiter un sommet
* Pour chaque sommet visité, on visite un sommet adjacent s'il est pas encore visité, récursivement.

## Remarque

* La récursivité est équivalent à l'utilisation d'une **pile**.

# Parcours en profondeur

## Pseudo-code (5min)

. . .

```C
initialiser(graphe) // tous les sommets sont non-visités
visiter(sommet, pile) // on a choisit un sommet du graphe
tant que !est_vide(pile)
    dépiler(pile, (v,u))
    si u != visité
        ajouter (v,u) dans l'arbre T
        visiter(u, pile)
```

## Que fait visiter?

. . .

```C
rien visiter(x, pile)
    marquer x comme visité
    pour chaque arête (x,w)
        si w != visité
            empiler(pile, (x,w))
```


# Exercice

* Établir la liste d'adjacence et appliquer l'algorithme de parcours en profondeur au graphe

```{.mermaid format=pdf width=400 loc=figs/}
graph LR;
    1---2;
    1---3;
    1---4;
    2---3;
    2---6;
    3---6;
    3---4;
    3---5;
    4---5;
```

# Interprétation des parcours

* Un graphe vu comme espace d'états (sommet: état, arête: action)
    * Labyrinthe
    * Arbre des coups d'un jeu

. . .

* BFS (Breadth-First Search) ou DFS (Depth-First Search) parcourent l'espace des états à la recherche du meilleur mouvement.
    * Les deux parcourent *tout* l'espace;
    * Mais si l'arbre est grand, l'espace est gigantesque!

. . .

* Quand on a un temps limité
    * BFS explore beaucoup de coups dans un futur proche;
    * DFS explore peu de coups dans un futur lointain.