# 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