from metakernel import register_ipython_magics
register_ipython_magics()
%load_ext snoop
%load_ext birdseye
The snoop extension is already loaded. To reload it, use: %reload_ext snoop
L1 = [
[1,3], #0
[0,2,3], #1
[1,3], #2
[0,1,2,4], #3
[3], #4
[6], #5
[5] #6
]
L2 = [
[1,2], #0
[3], #1
[5], #2
[4,0], #3
[2,5], #4
[1], #5
]
M1 = [
[False, True, False, True, False, False, False],
[True, False, True, True, False, False, False],
[False, True, False, True, False, False, False],
[True, True, True, False, True, False, False],
[False, False, False, True, False, False, False],
[False, False, False, False, False, False, True],
[False, False, False, False, False, True, False]
]
M2 = [[False, True, True, False, False, False],
[False, False, False, True, False, False],
[False, False, False, False, False, True],
[True, False, False, False, True, False],
[False, False, True, False, False, True],
[False, True, False, False, False, False]]
13425130
passe par tous les sommetsdef nb_s_l(l) :
return len(l)
def nb_s_m(m) :
return len(m)
def nb_a_l(l) :
nb_a = 0
for v in l :
nb_a += len(v)
return nb_a
def nb_a_m(m) :
nb_a = 0
for v in m :
for b in v :
if b :
nb_a += 1
return nb_a
$G = (S,A)$, $n = |S|$, $m = |A|$
def est_voisin_l(l,x,y) :
# Recherche linéaire de y dans l[x]
for v in l[x] :
if v == y :
return True
return False
def est_voisin_m(m,x,y) :
return m[x][y]
$G = (S,A)$, $n = |S|$, $m = |A|$
def degre_l(l,x,y) :
degre_sortant = len(l[x])
# Calcul du degré entrant
degre_entrant = 0
# Recherche linéaire de x dans chaque l[y]
for v_y in l :
for v in v_y :
if v == x :
degre_entrant += 1
break
return degre_entrant + degre_sortant
def degre_m(m,x,y) :
n = nb_s_m(m)
degre_sortant, degre_entrant = 0, 0
for y in range(n) :
if m[x][y] :
degre_sortant += 1
if m[y][x] :
degre_entrant += 1
return degre_entrant + degre_sortant
$G = (S,A)$, $n = |S|$, $m = |A|$
def degre_no_l(l,x,y) :
return len(l[x])
def degre_m(m,x,y) :
deg = 0
for b in m[x] :
if b :
deg += 1
return deg
$G = (S,A)$, $n = |S|$, $m = |A|$
def la2mat(l : list[list[int]]) -> list[list[bool]] :
n = nb_s_l(l)
m = [ [False]*n for x in range(n) ]
for y in range(n) :
for v in l[y] :
m[y][v] = True
return m
$G = (S,A)$, $n = |S|$, $m = |A|$
$\mathrm O(n^2) + \sum_{y \in S} ( \mathrm O( d_G^+(y)) + \mathrm O(1) ) = \mathrm O(n + m + n^2) = \mathrm O(n^2)$
def mat2la(m : list[list[bool]]) -> list[list[int]] :
n = nb_s_m(m)
l = [ ]
for y in range(n) :
v_y = []
for x in range(n) :
if m[y][x] == True :
v_y.append(x)
l.append(v_y)
return l
$G = (S,A)$, $n = |S|$, $m = |A|$
$\mathrm O(n^2)$
def est_chemin_l(l, c) :
if len(c) < 2 :
return False
s_pre = c[0]
for s_suiv in c[1:] :
if not est_voisin_l(l,s_pre,s_suiv) :
return False
s_pre = s_suiv
return True
def est_chemin_m(m, c) :
if len(c) < 2 :
return False
s_pre = c[0]
for s_suiv in c[1:] :
if not est_voisin_m(l,s_pre,s_suiv) :
return False
s_pre = s_suiv
return True
$G = (S,A)$, $n = |S|$, $m = |A|$, $k = |c|$
# liste d'adjacence
def C(l,u,v) :
if u == v :
return True
for w in l[u] :
if C(w,v) :
return True
return False
Supposons que l'algorithme ne termine pas sur $l, u, v$.
Soit $G = (S,A)$ le graphe représenté par $l$ et $n = |S|$.
Si l'algorithme ne termine pas, c'est nécessairement parcequ'il y a une séquence infinie d'appels récursif (la boucle for
termine).
On note $u_0, u_1, \dots, u_n$ les seconds arguments des $n+1$ premiers appels récursifs. $c = u_0\,u_1\,\dots\,u_n$ est un chemin de $G$ car $u_{i+1}$ est voisin de $u_i$.
Comme $|S| = n$, il existe $i < j \in \{ 0 \dots n \}$ tels que $u_i = u_j$ (principe des tiroirs). Donc $c' = u_i\,u_{i+1}\,\dots\,u_j$ est un cycle de $G$.
On en conclu que l'algorithme $C$ termine sur tout graphe acyclique, donc termine dans le contexte de cet exercice.