blob: 3e3742b70950a45c8984a17341e24063d0d7c402 (
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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
|
# Chemin Eulérien
Chemin qui visite chaque arête exactement une fois
# Cycle Eulérien
Idem mais en finissant sur le point de départ
*Remarque* : Déterminer si un graphe contient un chemin Eulérien se fait en temps linéaire
# Chemin Hamiltonien
Chemin qui visite chaque sommet exactement une fois
# Cycle Hamiltonien
Idem mais en finissant sur le point de départ
*Remarque* : Déterminer si un graphe contient un chemin Eulérien est NP-Complet
#### Coloration de graphes
_"Peut-on colorier un graphe avec k couleurs"_ : NP-Complet
_"Combien de couleurs minimum"_ : NP-Difficile
# Graphe planaire
graphe qu'on peut représenter sur un plan sans croiser d'arrêtes
_Remarque_ : Décider si un graphe est planaire se fait en temps linéaire
# Epaisseur d'un graphe
Nombre minimum de sous-graphes planaires nécessaires pour partitionner un graphe
_Remarque_ : L'épaisseur d'un graphe est NP-Difficile
# Min Vertex Cover
Ensemble minimal de sommets qui touchent toutes les arrêtes
$\Rightarrow$ NP-Difficile
# Min Edge Cover
Ensemble minimal d'arêtes qui touchent tous les sommets
$\Rightarrow$ NP-Difficile
# Composantes connexes
Un graphe connexe est un graphe dans lequel il existe au moins un chemin entre chaque paire de sommes
$\Rightarrow$ linéaire
# Graphe complet
Un graphe connexe est un graphe dans lequel il existe au moins une arête entre chaque paire de sommes
$\Rightarrow$ linéaire
# Tri topologique
Ordonner les noeuds de telle sorte que chaque noeud apparaît avant ses successeurs.
Le tri topologique d'un DAG se fait en temps linéaire avec un parcours en profondeur.
# Min Feedback Arc Set
Plus petit ensemble d'arêtes à retire pour casser tous les cycles du graphe
$\Rightarrow$ NP-Difficile
# Max Clique
Une clique est un sous-graphe [[#Graphe complet|complet]].
# Arbre
Un arbre est un graphe connexe et ayclique.
**Un arbre de n sommets possède exactement $n - 1$ arêtes**
# Arbres couvrants
se fait avec des parcours de graphes
trouver un graphe couvrant $\Rightarrow$ linéaire
de poids minimal $\Rightarrow$ polynomial
|
