CM7

Sous-graphe

Definition : Soit $G=(V,E)$ un graphe. $H=(V^{\prime },E^{\prime })$ est un sous graphe de $G$ si $xy\in E^{\prime }$ ssi $xy\in E$ $E^{\prime }|V^{\prime }$ la restriction des arrêtes à $V^{\prime }$

Instance : $G_1$ et $G_2$ deux graphes Question : Est-ce que $G_1$ est un sous-graphe de $G_2$ ?

C’est a dire trouver une application : $\Psi :V_1\to V_2$ $xy\in E_1$ ssi $\Psi (x)\Psi (y)\in E_2$

Cas particulier : isomorphisme Si $G_1$ est un sous-graphe de $G_2$ et $|V_1|=|V_2|$ alors $G_1$ et $G_2$ sont dit isomorphe et $\Psi$ est un isomorphisme.

2. Sous graphe $\in$ NP ?

Certificat : Permutation de $V_2$ Verification : pour i = 1 à |V1| faire : $\Psi$(i) = P[i] pour i$\ne$j $\in$ V1 faire : si (ij $\in$ E1 et $\Psi$(i) $\Psi$(j) $\notin$ E2) ou ((i) (j) $\in$ E2 et ij $\notin$ E1): exit retourner oui

2. Sous-graphe est NP-hard ?

$MIS{\ll }_{P}SG$ $f:I(MIS)\to I(SG)$ <$G,k$> → <$G_1,G_2$>

Une clique de G est un sous-graphe complet de G.

$G_2=G$ $G_1=(V_1=\{1,2,\dots ,k\},E_1=\{ij|i\ne j\notin [1,k]\}$ Complexité de $k^2$ donc polynomiale car $k\le M^2$ Même chose avec stable ($G_1=\varnothing$)

3. Sous-graphe est self réductible ?

Hypothese : On a un oracle $O(1)$ pour sous-graphe. Question : Algo polynomial pour sous-graphe_search.

On peut nettoyer le graphe en supprimant les sommets tant que l’oracle répond oui. Ainsi, les 2 graphes sont isomorphes.

Idée : peut-on decider si $y\in V_2$ est l’image de $x\in V_1$ ?

pour x $\in$ V2 faire si sous-graphe(G1, G2 | {x}) alors G2 = G2 | {x}

Théorème

$P=co-P$ Exemple : un tableau est-il trié ? → polynomial Le complémentaire est polynomial aussi

Théorème

Si $NP\ne \text{co-NP}$ alors $P\ne NP$ Preuve : $P=NP⟹\text{co-P}=\text{co-NP}=P$ $\text{co-NP}=P$ $NP=P⟹\text{co-NP}=NP$

PSPACE = Tous les algo deterministe qu’on peut résoudre avec un espace polynomial NSPACE = Tous les algo non-deterministe qu’on peut résoudre avec un espace polynomial

Théorème : PSPACE = NSPACE

Preuve que $NP\subseteq PSPACE$ Soit $Q\in NP$ $Q{\ll }_{P}3SAT$ Algo(i): j = f(i) // transformation poly retourner (algo3SAT(j)) // espace poly

Je pensais a un truc marrant et j’ai oublié parce que t’as dit un autre truc marrant. Alexis 2025

Une théorie récursivement axiomatisable est une théorie qui peut être axiomatisé. Youssef 2025

TD

$3CP{\ll }_{P}3color$ <G, $\Psi$> →<G’> G’ = le graphe G avec des arrêtes entre les sommets qui n’ont pas la même couleur

Decision = faire Qi