init: initial commit

7 files changed, 359 insertions, 0 deletions

diff --git a/THEG/Composantes connexes.md b/THEG/Composantes connexes.md
new file mode 100755
index 0000000..c0c2d01
--- /dev/null
+++ b/THEG/Composantes connexes.md
@@ -0,0 +1,7 @@
+# Définition
+Une **composante connexe** est un ensemble $C \subseteq V$ non vide tel que pour toute paire de sommets $\{ s_{1},s_{2} \} \subseteq C$ telle que $s_{1} \neq s_{2}$ il existe un chemin de $s_1$ à $s_2$.
+
+# Détection
+Un **DFS** ou un **BFS** permet de trouver tous les sommets d'une composante maximale.
+
+# Euler 215
diff --git a/THEG/Couplages.md b/THEG/Couplages.md
new file mode 100755
index 0000000..9f2f215
--- /dev/null
+++ b/THEG/Couplages.md
@@ -0,0 +1,29 @@
+# Définition
+Soit $G = (V,E)$ un graphe simple non-orienté.
+- Un **couplage** (**matching**) $M$ est un ensemble d'arêtes deux-à-deux non adjacentes.
+	- $M_1 = \emptyset$ est un couplage
+- Un couplage est **maximal** s'il n'existe pas de couplage $M'$ tel que $M \subseteq M'$
+- Un couplage est **maximum** s'il n'existe pas de couplage $M'$ tel que $|M| < |M'|$
+- Un couplage est **parfait** si chaque sommet du graphe touche une arête du couplage.
+- Un couplage **parfait** a $\frac{|V|}{2}$ arêtes exactement
+- Un couplage **parfait** est **maximum**
+- Un couplage **maximum** est **maximal**
+
+# Trouver des couplages
+Soit $M \subseteq E$ un couplage pour $G = (V,E)$.
+Un **sommet libre** de $G$ est un sommet non touché par $M$.
+Un **chemin améliorant** est un chemin de $G$ qui :
+- relie deux sommets libres
+- alterne des arêtes de $E \setminus M$ et des arêtes de  $M$.
+
+## Théorème
+$M$ est **maximum** pour $G \Leftrightarrow$ il n'existe pas de **chemin améliorant**.
+
+## Algo
+- On part d'un sommet libre
+- on construit un arbre (avec DFS ou BFS) avec la contrainte d'alterner arêtes de $E \setminus M$ et arête de $M$
+- marquer les sommets comme pairs ou impairs pour aider à respecter l'alternance $E \setminus M$ / $M$
+- on s'arrête quand on tombe sur un sommet libre.
+
+## Cycles de taille impaire - Algorithme de Jack Edmonds
+Consiste à compresser les cycles en un seul noeud.
\ No newline at end of file
diff --git a/THEG/Distances et plus court chemin.md b/THEG/Distances et plus court chemin.md
new file mode 100755
index 0000000..a040318
--- /dev/null
+++ b/THEG/Distances et plus court chemin.md
@@ -0,0 +1,62 @@
+# Rubik's cube
+- noeud = configuration
+- arêtes = 1/4 de tour
+
+# Calcul de distance
+On cherche à trouver la plus petite distance entre le sommet source et tous les sommets destinations
+
+$\rightarrow$ on fait un BFS
+
+![[Pasted image 20250319171722.png]]
+
+**Complexité**: $\Theta(|V| + |E|)$
+
+# Rayon et diamètre
+
+## Excentricité
+
+$exc(x) = max\{ d(x,y) \; | \; y \in V \}$
+
+## Rayon
+
+$rayon(G) = min\{exc(x) \; | \; x \in V\}$
+
+## Diamètre
+
+$diam(G) = max\{exc(x) \; | \; x \in V\}$
+## Centre
+
+$centre(G) = \{x \in V \; | \; exc(x) = rayon(G)\}$
+
+## Périphérie
+
+$périphérie(G) = \{x \in V \; | \; exc(x) = diam(G)\}$
+
+# Dijkstra
+$\rightarrow$ pour les graphes pondérés
+On traite en premier les sommets de distance minimale
+
+![[Pasted image 20250319175639.png]]
+
+**Complexité** :
+- Si todo est un tableau/vecteur : $O(|V|^2 + |E|)$
+- Si todo est un tas min : $O((|V| + |E|)\log |V|)$
+- Si todo est un tas de Fibonacci : $O(|E| + |V|\log |V|)$
+
+# Algorithme de Bellman-Ford
+
+$\rightarrow$ Cas des poids négatifs
+$dist(y,k) =$ distance du PCC allant de $s$ à $y$ avec au plus $k$ arêtes
+$dist(y,k) = \min\{ dist(x,k-1) + w(x,y) \; | \; x \in V \}$
+$$dist(y,0) = \begin{cases}
+0 \quad si \quad s = y \\
+\infty \quad sinon
+\end{cases}$$
+$dist(s,y) = dist(y, |V| - 1)$ ($|V| - 1 =$ nb max d'arête dans un PCC)
+
+![[Pasted image 20250319183624.png]]
+
+### Optimisations
+
+- s'arrêter si rien ne change d'une itération à l'autre $\rightarrow O(|V|.|E|)$
+- lever une exception si le tableau *dist* bouge encore pour l'itération $k = |V|$
\ No newline at end of file
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
diff --git a/THEG/Introduction.md b/THEG/Introduction.md
new file mode 100755
index 0000000..b42b5d6
--- /dev/null
+++ b/THEG/Introduction.md
@@ -0,0 +1,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]]
diff --git a/THEG/PCC & Floyd Warshall.md b/THEG/PCC & Floyd Warshall.md
new file mode 100755
index 0000000..c04561c
--- /dev/null
+++ b/THEG/PCC & Floyd Warshall.md
@@ -0,0 +1,76 @@
+# Fast Power (Exponentiation rapide)
+
+$a^n = a  \times a \times a \times \dots \times a$
+$a^9 = a \times a^8 = a \times (a^4 \times a^4)$
+$\mathcal{O}(n) \rightarrow \mathcal{O}(\log n) \checkmark$
+
+Généralisable sur des monoïdes
+
+---
+
+# Distances n sommets, n designations
+## Notation
+On note $D_{k}[X,Y]$ la distance minimale entre X et Y passant par au plus $k$ arcs
+$$
+D_{k}[X,Y] = \begin{cases}
+M[X,Y] \; si \; k = 1 \\
+min_{Z\in V}(D_{k-1}[X,Z] + M[Z,Y]) \; si \; k > 1
+\end{cases}
+$$
+Avec $M$ la matrice pondérée, et en cherchant $2 \leq k \leq |V| - 1$
+
+![[{337A76B1-DC9F-4A71-A261-156A3B3ABF66}.png]]
+$\longrightarrow \mathcal{O}(|V|^4)$
+
+# Semi-anneau
+$(E,\oplus, \otimes, e,f)$ est un **semi-anneau** si :
+1. $(E,\oplus,e)$ est un **monoïde commutatif**
+2. $(E,\otimes,f)$ est un **monoïde**
+3. $\otimes$ est **distributif** par rapport à $\oplus$
+4. $e$ est **absorbant** pour $\otimes$ ($\forall x \in E, x \otimes e = e \otimes x = e$)
+
+Si $(E,\oplus,\otimes,e,f)$ est un **semi-anneau** alors la structure $(\mathcal{M}_{n}(E),\boxplus,\boxtimes, \mathcal{O},\mathcal{I})$ où $\mathcal{I}$, $\mathcal{O}$, $S = A \boxplus B$, $P = A \boxtimes B$ sont définis par :
+$$
+\begin{align}
+&\mathcal{I}_{i,j} = \begin{cases}
+f \quad si \; i = j \\
+e \quad sinon
+\end{cases} \\
+&\mathcal{O}_{i,j} = e \\
+&S_{i,j} = A_{i,j} \oplus B_{i,j} \\
+&P_{i,j} = A_{i,j} \otimes B_{i,j}
+\end{align}
+$$
+est aussi un **semi-anneau**.
+
+$\rightarrow$ Permet de réduire `SlowShortestPath` à $\mathcal{O}(|V|^3 \log |V|)$
+## Exemples
+$(\mathbb{R}, +, \times$
+
+
+# Floyd Warshall
+![[{2093C32E-4155-4837-8A07-EDB06608F3D6}.png]]
+
+```
+FloydWarshall(M)
+	n <- size(M)
+	D <- M
+	for X <- 1 to n
+		for Y <- 1 to n
+			P[X,Y] <- X
+	for K <- 1 to n
+		for X <- 1 to n
+			for Y <- 1 to n
+				if D[X,K] + D[K,Y] < D[X,Y]
+					D'[X,Y] <- D[X,K] + D[K,Y]
+					P[X,Y] <- P[K,Y]
+				else
+					D'[X,Y] <- D[X,Y]
+		D <- D'
+	return D,P
+```
+
+# Autres application
+
+## THL
+$\longrightarrow$ Automates
\ No newline at end of file
diff --git a/THEG/Parcours.md b/THEG/Parcours.md
new file mode 100755
index 0000000..56503fc
--- /dev/null
+++ b/THEG/Parcours.md
@@ -0,0 +1,97 @@
+# DFS
+
+## Algorithme
+
+On utilise une file.
+
+```pcode
+\begin{algorithm}
+\caption{Quicksort}
+\begin{algorithmic}
+  \PROCEDURE{Quicksort}{$A, p, r$}
+	\IF{$p < r$}
+	  \STATE $q = $ \CALL{Partition}{$A, p, r$}
+	  \STATE \CALL{Quicksort}{$A, p, q - 1$}
+	  \STATE \CALL{Quicksort}{$A, q + 1, r$}
+	\ENDIF
+  \ENDPROCEDURE
+  \PROCEDURE{Partition}{$A, p, r$}
+	\STATE $x = A[r]$
+	\STATE $i = p - 1$
+	\FOR{$j = p$ \TO $r - 1$}
+	  \IF{$A[j] < x$}
+		\STATE $i = i + 1$
+		\STATE exchange
+		$A[i]$ with $A[j]$
+	  \ENDIF
+	\STATE exchange $A[i]$ with $A[r]$
+	\ENDFOR
+  \ENDPROCEDURE
+  \end{algorithmic}
+\end{algorithm}
+```
+## Implémentation
+
+```python
+def adjlist(n, edges, directed=False):
+    lst = [[] for _ in range(n)]
+    for (s,d) in edges:
+        lst[s].append(d)
+        if not directed:
+            lst[d].append(s)
+    return lst
+	
+def dfs(n, edges, start):
+    succ = adjlist(n, edges)
+    seen = [False] * n
+    tree = []
+    def rec(s):
+        seen[s] = True
+        for d in succ[s]:
+            if not seen[d]:
+                tree.append((s,d))
+                rec(d)
+        print(s)
+    rec(start)
+    return tree
+	
+def dfsi(n, edges, start):
+    seen = [False] * n
+    todo = [(start,start)]  # Pile d'arêtes
+    succ = adjlist(n, edges)
+    tree = []
+    while todo:
+        (x,s) = todo.pop() # sans (0)
+        if seen[s]:
+            continue
+        seen[s] = True
+        if x != s:
+            tree.append((x,s))
+        for d in succ[s]:
+            todo.append((s,d))
+    return tree
+```
+
+# BFS
+
+```python
+def bfs(n, edges, start):
+    seen = [False] * n
+    seen[start] = True
+    todo = [start]  # File
+    succ = adjlist(n, edges)
+    tree = []
+    while todo:
+        s = todo.pop(0) # retire la 1re valeur
+        for d in succ[s]:
+            if not seen[d]:
+                seen[d] = True
+                todo.append(d)
+                tree.append((s,d))
+    return tree
+```
+# Circuits & chemins eulériens
+
+**Conditions nécessaires et suffisantes** :
+- Toutes les arrêtes du graphe doivent être dans la même composante
+- Le nombre de sommets de degré impair doit être 0 (pour un cycle eulérien) ou 2 (pour un chemin eulérien)
\ No newline at end of file