---
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)\},\\
|E|&=4.
\end{align*}

::::

:::