blob: b42b5d647b7bc6a69bc6e283a6cbf5e4be80cd85 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
# 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]]
|
