init: initial commit

1 files changed, 59 insertions, 0 deletions

diff --git a/THEG/Définitions.md b/THEG/Définitions.md
new file mode 100755
index 0000000..3e3742b
--- /dev/null
+++ b/THEG/Définitions.md
@@ -0,0 +1,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
\ No newline at end of file