---
title: "Graphes - Généralités"
date: "2022-05-03"
patat:
  eval:
    tai:
      command: fish
      fragment: false
      replace: true
    ccc:
      command: fish
      fragment: false
      replace: true
  images:
    backend: auto
---

# Historique

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

## L. Euler, 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=50%}

. . .

* 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%}

* Sommet est un site.
* 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, peuvent être parcourues dans n'importe quel ordre).

## 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 non-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$ et adjacent à $v$.

## Exemple

::: columns

:::: column

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

::::

:::: column

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

::::

:::

# 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, ou pas 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.](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.](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=80%}

::::

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

::::

:::

# 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 $\leq 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, ou pas.](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 structure 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 diagonale
$$
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}(|V|-1)|V|/2$.

# Considérations d'efficacité

* Dans quel type de graphes la matrice d'adjacence est 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

* 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)


::::

:::