--- 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? {width=50%} . . . * Réponse: ben non! # Utilisation quotidienne ## Réseau social {width=40%} * Chaque sommet est un individu. * Chaque trait une relation d'amitié. * Miam, Miam, Facebook. # Utilisation quotidienne ## Moteurs de recherche {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.  * 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  :::: :::: 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  :::: :::: 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*} :::: :::