# Graphes

- = réseaux :
	- réseau informatique
	- réseau de transport
	- réseau social
	- modèles moléculaires
	- ...
## Notation

### Graphe non-orienté : $G = (V, E)$
$V$ l'ensemble de sommets **non-vide**
$E \subseteq V^2$ l'ensemble des arrêtes potentiellement vide
$$\delta^+(x) = \delta^-(x) = \delta(x) = \{y \in V | (x, y) \in E\}$$
$$deg(x) = |\delta|$$
### Graphe orienté : $G = (V, E)$
$V$ l'ensemble de sommets **non-vide**
$E \subseteq V^2$ l'ensemble des arrêtes potentiellement vide
Pour un sommet  $x \in V$
$$\delta^+(x) = \{y \in V | (x, y) \in E\}$$
$$\delta^-(x) = \{y \in V | (x, y) \in E\}$$
$$deg^+(x) = |\delta^+|$$
$$deg^-(x) = |\delta^-|$$
On a toujours $\sum_{x \in V} deg^+(x) = \sum_{x \in V} deg(x) = |E|$
On a toujours $\sum_{x \in V} deg(x) = |E|²$

## [Définitions](./Définitions.md)

## [[Parcours|Parcours de graphes]]