from metakernel import register_ipython_magics
register_ipython_magics()
Le graphe est non-orienté. Le graphe est connexe si et seulement si le nombre d'accessible depuis un sommet quelconque $s$ du graphe est égal au nobmre de sommet.
def est_connexe(g) :
# Initialisation en O(1)
nb_s = len(g)
if nb_s == 0 :
return False
vus = [False] * nb_s
pile = []
pile.append(0)
nb_accessibles = 0
# Parcours en O(n + m), et à chaque sommet on incrémente un compteur en O(1)
while len(queue) > 0 :
s = pile.pop()
vus[s] = True
nb_accessible += 1
if nb_accessible == nb_s :
return True
for v in g[s] :
if not vus[v] :
pile.append(v)
return False
Complexité : $\mathrm O(n + m)$
from collections import deque
def accessibles(g) :
nb_s = len(g)
if nb_s == 0 :
return False
accessibles = [False] * nb_s
file = deque()
file.append(0)
accessibles[0] = True
# Parcours en O(n + m), et à chaque sommet on ne fait rien...
while len(queue) > 0 :
s = file.popleft()
for v in g[s] :
if not accessible[v] :
queue.append(v)
accessibles[v] = True
return [ i for i in range(nb_s) if accessibles[i] ]
Complexité : $\mathrm O(n + m)$
def parcours(g, s, vus) :
if vus[s] :
return True
vus[s] = True
for v in g[s] :
if parcours(g, v, vus) :
return True
return False
def cyclique(g) :
nb_s = len(g)
vus = [False] * nb_s
for s in range(nb_s) :
if not vus[s] and parcours(g,s,vus) :
return True
return False
Chaque sommet est vu une seule fois. Le reste des opérations sont élémentaires.
Complexité : $\mathrm O(n + m)$
def plus_court(g, u, v) :
nb_s = len(g)
accessibles = [False] * nb_s
file = deque()
file.append((u,0))
accessibles[u] = True
# Parcours en O(n + m), et à chaque sommet on ne fait rien...
while len(queue) > 0 :
(s,d) = file.popleft()
if s = v :
return d
for w in g[s] :
if not accessible[w] :
queue.append((w,d+1))
accessibles[w] = True
return -1
Chaque sommet est vu une seule fois. Le reste des opérations sont élémentaires.
Complexité : $\mathrm O(n + m)$
def parcours(g, s, vus) :
if vus[s] :
return [s]
vus[s] = True
for v in g[s] :
cycle = parcours(g, v, vus)
if cycle != [] :
cycle.append(s)
return cycle
return []
def cyclique(g) :
nb_s = len(g)
vus = [False] * nb_s
for s in range(nb_s) :
if not vus[s] :
cycle = parcours(g,s,vus)
if cycle != [] :
return cycle
return []
Chaque sommet est vu une seule fois. Le reste des opérations sont élémentaires.
Complexité : $\mathrm O(n + m)$
def est_2coloration(g,coloration) :
for s in range(len(g)) :
for v in g[s] :
if coloration[s] == coloration[v] :
return False
return True
Intuitivement, les couleurs du graphe doivent alterner sur un chemin. Donc si $u$ et $v$ sont reliés par un chemin et que $h(u) = f(u)$, nécessairement $h(v) = f(v)$ ou il existe deux sommets consécutifs du chemin qui ont la même couleur.
Comme $f$ est une 2-coloration, $$\forall 1 \leq i \leq k, f(i) = \begin{cases} f(u) && \text{ si i est pair} \\ 1-f'u) && \text{sinon} \end{cases}$$ Soit $j = \min\{ 0 \leq i \leq k, f(s_i) \neq h(s_i) \}$. $j$ existe car $h(v) = f(v)$ et $j > 0$ car $h(u) = f(u)$. $h(s_{j-1}) = f(s_{j-1}) = 1 - f(s_j) = h(s_j)$ Donc $h$ n'est pas une 2-coloration.
def est_2coloriable(g) :
nb_s = len(g)
coloration = [None] * nb_s
file = deque()
file.append(0)
coloration[0] = True
# Parcours en O(n + m), et à chaque sommet on ne fait rien...
while len(queue) > 0 :
s = file.popleft()
for w in g[s] :
if coloration[w] == None :
coloration[w] = not coloration[s]
queue.append(w)
elif coloration[w] != coloration[s] :
return []
return coloration
Soit $C$ un cycle eulerien. Soit $s$ un sommet de $G$. Supposons $s$ n'étant pas le premier sommet du cycle. Soit $A_s = \{ (u,s) \in A, us \in C\} \cup \{ (s,u) \in A, su \in C$. Soit $n$ le nombre d'apparition de $s$ dans $C$. Comme $C$ est eulérien, $d(s) = |A_s|$. Par ailleurs , on a $|\{ (u,s) \in A, us \in C\}| = n$ et comme $C$ est un cycle $|\{ (u,s) \in A, us \in C\}| = |\{ (s,u) \in A, su \in C\}|$.
Si le graphe ne possède pas d'arête, le cycle $\epsilon$ convient. Par récurrence sur le nombre d'arête. Prenons un sommet $s$ de degré non nul. On a donc $d(s) \geq 2$. Soit $(u,s)$ et $(s,v)$ deux arêtes reliées à $s$. On supprime ces deux arêtes et on ajoute l'arête $(u,v)$ pour crée un graphe $G'$ ayant une arête de moins. Dans $G'$, $d_{G'}(s) = d_G(s) -2$ reste pair et pour tous les autres sommets, dont $u$ et $v$, le sommet reste inchangé, donc pair. $G'$ possède un cycle eulérien, $C$. $C$ contient l'arête $uv$ ou $vu$. On construit dans $G$ le cycle $C'$ en changeant $uv$ par $usv$, ou $vu$ par $vsu$. $C'$ est un cycle eulérien dans $G$. CQFD.
Supposons $C$ n'est pas eulerien. Il existe une arête $uv$ qui n'est pas dans $C$. Supposons $u$ et $v$ ne sont pas dans $C$. Soit $s$ un sommet de $C$ (non vide). Comme $G$ est connexe, il existe un chemin $s = s_0 \cdot \dots s_k = u$ dans $G$ de $s$ à $u$. Soit $j = \min \{ 0 \leq i < k, s_is_{i+1} \not\in C \}$. $j$ existe car $u \not\in C$. Alors $s_j$ apparaît dans $C$ car $s_0 \in C$ ou $s_{j-1}s_j \in C$. Et l'arête $s_js_{j+1} \not\in C$. On renomme alors $u = s_j$, $v = s_{j+1}$.
Si $u$ ou $v$ sont dans $C$, quitte à renommer $v$ en $u$ on peut considérer que $u \in C$. $u$ convient.
On effectue une rotation sur $C$ et $C'$ de manière à les faire démarrer de $s$. On a $C = s s_1 \dots s_k s$ et $C' = s s_1' \dots s_l' s$. On construit le cycle $ss_1\dots s_ks s_1'\dots s_l's$. C'est bien un cycle et il est bien simple.
On cherche un cycle simple depuis un sommet quelconque $s$ de $G$. On le nomme $C$. On cherche une arête partant d'un sommet de S mais n'étant pas dans $C$. S'il n'y en a pas, soit il n'y a plus d'arêtes et le cycle est eulérien, soit $G$ n'est pas eulérien. Sinon on part du sommet $s'$ trouvé. On cherche un cycle simple $C'$ partant de $s'$ ne réutilisant pas les même arêtes. On fusionne $C$ et $C'$. On réitère.
# g liste d'adjacence
def cycle_simple(g,s, a_vus, a_restante) :
if a_restante[s] == False :
return [s]
t = -1
nb_dispo = 0
for v in g[s] :
if not a_vus[s][v] :
v = t
nb_dispo += 1
if nb_dispo > 1 :
break
if nb_dispo == 1 :
a_restante[s] = False
a_vus[s][t] = True
C = cycle_simple(g,t,a_vus,a_restante)
C.append(t)
return C
def nouveau_depart(a_restante) :
for s in range(len(a_restante)) :
if a_restante[s] :
return s
return -1
def eulerien(g) :
nb_s = len(g)
nb_a = 0
for i in range(nb_s) :
nb_a += len(g[i])
a_vus = [[False] * nb_s for i in range(nb_s) ] # si l'arête i,j a été utilisé
a_restante = [False] * nb_s # pour chaque sommet : None -> pas dans C ; True -> dans C et il reste des arêtes pas dans C ; False -> Dans C et aucune arête restante
C = []
for s in range(nb_s) :
if len(g[s]) > 0 :
a_restante[s] = True
C = [s]
while s != -1 :
C0 = cycle_simple(g, s,a_vus,a_restante)
if C0 == [] or C0[0] != s : return None
C0 += C
C = C0
if len(C) == nb_a +1 :
return C
s = nouveau_depart(a_restante)
return None
return C