# OLA, TP 1
Rappels de Python :
Pour définir une variable:
```python=
my_var = 12
```
Pour définir une fonction:
```python=
def f(i):
if i < 0:
return True
else:
return False
```
## Exercice 1:
1. Représentation en Python du graphe
Correction :
```python =
exemple_matrice =
[[0, 1, 1, 0, 1, 0, 0, 0], #0
[0, 0, 0, 1, 0, 1, 0, 0], #1
[0, 0, 0, 1, 0, 0, 1, 0], #2
[0, 0, 0, 0, 0, 0, 0, 1], #3
[0, 0, 0, 0, 0, 1, 1, 0], #4
[0, 0, 0, 0, 0, 0, 0, 1], #5
[0, 0, 0, 0, 0, 0, 0, 1], #6
[0, 0, 0, 0, 0, 0, 0, 0]] #7
exemple_liste =
[[1, 2, 4],
[3, 5],
[3, 6],
[7],
[5, 6],
[7],
[7],
[]]
```
2. Question 2
```python=
def compte_sommet(g):
return len(g)
def compte_arete_m(g):
nb=0
for i in range(len(g)):
for j in range (len(g)):
nb+=g[i][j]
return nb
print(compte_arete_m(exemple_matrice))
def compte_arete_l(g):
nb=0
for i in range(len(g)):
nb+=len(g[i])
return nb
print(compte_arete_l(exemple_liste))
```
3. Question 3:
```python=
def adjacents_matrice(g,i,j):
return g[i][j]==1 or g[j][i]==1
def adjacents_liste(g,i,j):
return j in g[i] or i in g[j]
```
4. Question 4:
```python=
def successeurs_matrice(g, s):
l=[]
for i in range(len(g)):
if g[s][i]==1:
l.append(i)
return l
def successeurs_liste(g, s):
return g[s]
```
5. Question 5 :
```python=
def predecesseurs_matrice(g, s):
l=[]
for i in range(len(g)):
if g[i][s]==1:
l.append(i)
return l
def predecesseurs_liste(g, s):
l=[]
for i in range(len(g)):
if s in g[i]:
l.append(i)
return l
```
6. Question 6 : réflexif
```python=
def reflexif_m(g):
for i in range(len(g)):
if not g[i][i]==1:
return False
return True
def reflexif_l(g):
for i in range(len(g)):
if not (i in g[i]):
return False
return True
```
7. Question 7 : symétrique
```python=
def symetrique_m(g):
for i in range(len(g)):
for j in range(len(g)):
if g[i][j]==1:
if g[j][i]==0:
return False
return True
print(symetrique_m(g))
def symetrique_l(g):
for i in range(len(g)):
for j in g[i]:
if not i in g[j]:
return False
return True
```
8. Symétrisation
```python=
def symetrisation_m(g):
for i in range(len(g)):
for j in range(len(g)):
if g[i][j]==1:
g[j][i]=1
def symetrisation_l(g):
for i in range (len(g)):
for j in g[i]:
if not i in g[j]:
g[j].append(i)
```
9. Transitif
```python=
def transitif_matrice(g):
for i in range(len(g)):
for j in successeurs_matrice(g, i):
for k in successeurs_matrice(g, k):
if not g[i][k]:
return False
return True
def transitif_liste(g):
for i in range(len(g)):
for j in g[i]:
for k in g[j]:
if not k in g[i]:
return False
return True
```
Code d'Ariane
```python=
#Q1
#a) Matrice
g1 = [[False, True, True, False, True, False, False, False],
[False, False, False, True, False, True, False, False],
[False, False, False, True, False, False, True, False],
[False, False, False, False, False, False, False, True],
[False, False, False, False, False, True, True, False],
[False, False, False, False, False, False, False, True],
[False, False, False, False, False, False, False, True],
[False, False, False, False, False, False, False, False]]
#b) Liste
g2 = [[1, 2, 4],
[3, 5],
[3, 6],
[7],
[5, 6],
[7],
[7],
[]]
#Q2
#a)
def compte_sommets(g):
return len(g)
def compte_aretes_m(g):
nb = 0
for i in range(len(g)): # de 0 à len(g)-1
for j in range(len(g)):
if g[i][j]:
nb+=1
return nb
def compte_aretes_l(g):
nb = 0
for i in range(len(g)):
nb+=len(g[i])
return nb
#Q3
#a)
def adjacents_m(g, i, j):
return g[i][j] or g[j][i]
#b)
def adjacents_l(g, i, j):
return (i in g[j]) or (j in g[i])
#Q4
#a)
def successeurs_m(g, s):
res=[]
for i in range(len(g)):
if g[s][i]:
res.append(i)
return res
#b)
def successeurs_l(g, s):
return g[s]
#Q5
#a)
def predecesseurs_m(g, s):
res=[]
for i in range(len(g)):
if g[i][s]:
res.append(i)
return res
#b)
def predecesseurs_l(g, s):
res=[]
for i in range(len(g)):
if s in g[i]:
res.append(i)
return res
#Q6
#a)
def reflexif_m(g):
for i in range(len(g)):
if not g[i][i]:
return False
return True
#b)
def reflexif_l(g):
for i in range(len(g)):
if not (i in g[i]):
return False
return True
#Q7
#a)
def symetrique_m(g):
for i in range(len(g)):
for j in range(len(g)):
if g[i][j]:
if not g[j][i]:
return False
return True
#b)
def symetrique_l(g):
for i in range(len(g)):
for j in range(len(g)):
if j in g[i]:
if not i in g[i]:
return False
return True
#Q8
#a)
def symetrisation_m(g):
for i in range(len(g)):
for j in range(len(g)):
if g[i][j]:
g[j][i]=True
#b)
def symetrisation_l(g):
for i in range(len(g)):
for j in g[i]:
if not i in g[j]:
g[j].append(i)
#Q9
#a)
def transitif_m(g):
for i in range(len(g)):
for j in successeurs_m(g, i):
for k in successeurs_m(g, j):
if not g[i][k]:
return False
return True
#b)
def transitif_l(g):
for i in range(len(g)):
for j in g[i]:
for k in g[j]:
if not k in g[i]:
return False
return True
```
Señor Alexis :
```python=
# Q1
g_M = [[False, True, True, False, True, False, False, False],
[False, False, False, True, False, True, False, False],
[False, False, False, True, False, False, True, False],
[False, False, False, False, False, False, False, True],
[False, False, False, False, False, True, True, False],
[False, False, False, False, False, False, False, True],
[False, False, False, False, False, False, False, True],
[False, False, False, False, False, False, False, False]]
g_L = [[1, 2, 4],
[3, 5],
[3, 6],
[7],
[6, 5],
[7],
[7],
[]]
# Q2
def compte_sommets(g):
return len(g)
def compte_aretes_matrice(g):
nb_aretes = 0
for s in g:
for a in s:
if a is True:
nb_aretes += 1
return nb_aretes
def compte_aretes_liste(g):
nb_aretes = 0
for s in g:
nb_aretes+=len(s)
return nb_aretes
# Q3
def adjacents_matrice(g,i,j):
return g[i][j] or g[j][i]
def adjacents_liste(g,i,j):
return j in g[i] or i in g[j]
# Q4
def successeurs_matrice(g,s):
successeurs = []
for index_a, a in enumerate(g[s]):
if a is True:
successeurs.append(index_a)
return successeurs
def successeurs_list(g,s):
return g[s]
# Q5
def predecesseurs_matrice(g, s):
predecesseurs = []
for index_v,v in enumerate(g):
if v[s] is True:
predecesseurs.append(index_v)
return predecesseurs
def predecesseurs_list(g, s):
predecesseurs = []
for index_v, v in enumerate(g):
if s in v:
predecesseurs.append(index_v)
return predecesseurs
# Q6
def reflexif_matrice(g):
for index_v, v in enumerate(g):
if v[index_v] is False:
return False
return True
def reflexif_list(g):
for index_v, v in enumerate(g):
if index_v not in v:
return False
return True
# Q7
def symetrique_matrice(g):
for i in range(len(g)):
for j in range(len(g[i])):
if g[i][j] is True:
if g[j][i] is False:
return False
return True
def symetrique_list(g):
for index_s, s in enumerate(g):
for v in s:
if index_s not in g[v]:
return False
return True
# Q8
def symetrisation_matrice(g):
for s1, s in enumerate(g):
for s2, a in enumerate(s):
if a is True:
g[s2][s1] = True;
return g
def symetrisation_list(g):
for s1, s in enumerate(g):
for s2 in s:
g[s2].append(s1)
return g
# Q9 (Brut)
def transitif_matrice(g):
for i in range(len(g)):
for j in range(len(g[i])):
for k in range(g[i][j]):
if g[i][j] is True and g[j][k] is True:
if g[i][k] is False:
return False
return True
```
Jacobo
```python=
#1
#graphe_M= deja fait par les autres.
graphe_L =
[[1,2,4],
[3,5],
[3,6],
[7],
[6,5],
[7],
[7],
[]]
#2
def compte_somets(graphe):
return len(graphe)
def compte_aretes_L(graphe):
res=0
for i in range (len(graphe)):
res += len(graphe[i])
return res
def compte_aretes_M(graphe)
sum=0
for sommet in graphe:
for i in sommet:
if i==True:
sum+=1
return sum
#3
def adjacents_M(g, i, j)
return g[i][j] or g[j][i]
def adjacents_L(g, i,j)
for t in g[i]:
if t == j:
return true
for x in g[j]:
if x == i:
return true
return false
#return j in g[i] or i in g[j] OP
#4
def succeseurs_L(g, s)
return g[s]
def succeseurs_M(g, s)
res = []
for i in range len(g[s]):
if g[i]:
res.append(i)
return res
#5
def predecesseurs_L(g, s):
res=[]
for i in range compte_sommets(g):
if s in g[i]:
res.append(i)
return res
def predecesseurs_M(g,s)
res=[]
for i in range compte_sommets(g):
if g[s]:
res.append(i)
return res
def reflexif_L(g)
for i in range len(g):
if !(i in g[i]):
return False
return True
def reflexif_M(g)
for i in range len(g):
if !g[i][i]:
return False
return True
#7
def symetrique_L(g)
for i in range len(g):
for j in range len(i):
if !(j in g[i] and i in g[j]):
return False
return True
def symetrique_M(g)
for i in range len(g):
for j in range len(i):
if !(g[i][j] and g[j][i])
return False
return True
def symetrisation_L(g)
for i in range len(g):
for j in range len(i):
if !(j in g[i] and i in g[j]):
res = g[]
return res
def symetrisation_M(g)
#
```
Brahim
```python=
g = [[False,True,True,False,True,False,False,False],
[False,False,False,True,False,False,True,False],
[False,False,False,False,False,False,False,True],
[False,False,False,False,False,True,True,False],..
...
]
g = [[1,2,4],
[3,5],
[3,6],
[7],
[5,6],
[7],
[7],
[]]
def compte_sommet(g):
return len(g)
def compte_arete(g):
res=0
for i in range (len(g)):
for j in range(len(g[i])):
if g[i][j] == True then :
res=res+1
return res
def adjacents(la,i,j):
b=False
for k in range(len(la(i))):
if k ==j :
b=True
for k in range(len(la(j)):
if k==i :
b=True
return b
def sucesseurs(g,s):
l=[]
for i in range(len(g[s])):
if g[s][i]:
l.append(i)
return l
def predecesseurs(g,s):
l=[]
for i in range(len(g)):
for j in range(len(g[i])):
if j==s and g[i][s] :
l.append(i)
return l
def reflexif(g):
for i in range(len(g)):
if not(g[i][i]):
return False
return True
def symetrique(g):
for i in range(len(g)):
for j in range(len(g[i])):
if g[i][j] and not(g[j][i]):
return False
return True
def symetrisation(g):
g_prime=g
for i in range(len(g)):
for j in range(len(g[i])):
if g[i][j] and not(g[j][i]):
g_prime[j][i]=True
return g_prime
```
Rachad
```python=
Q1)
exemple_matrice =
[[0, 1, 1, 0, 1, 0, 0, 0], #0
[0, 0, 0, 1, 0, 1, 0, 0], #1
[0, 0, 0, 1, 0, 0, 1, 0], #2
[0, 0, 0, 0, 0, 0, 0, 1], #3
[0, 0, 0, 0, 0, 1, 1, 0], #4
[0, 0, 0, 0, 0, 0, 0, 1], #5
[0, 0, 0, 0, 0, 0, 0, 1], #6
[0, 0, 0, 0, 0, 0, 0, 0]] #7
Q2)
def compte_sommet(g):
return len(g)
def nbr_arrete(graphe):
return sum([sum(i) for i in graphe ]) #output=12
Q3):
def adjacent(graphe,first,second):
Q4):
def Succeseur(graphe,sommet):
""" Succeseur(g,2) =[3, 6]"""
return [som for som in range(8) if g[sommet][som]] #len(g) =8
Q5)
def predecesseurs(graphe,sommet):
return [som for som in range(8) if g[som][sommet]] #len(g) =8
Q6)
def reflexive(graphe):
"""1 case de la diagonale =1 <=> True"""
return any([g[e][e] for e in range(8)]) #len(g) =8
Q7)
def symetrique(graphe):
nb=len(graphe)
return all([graphe[i][j]==graphe[j][i] for i in range(nb) for j in range(nb) ])
Q8)
def symetrisation(graphe):
nb=len(graphe)
for i in range(nb):
for j in range(nb):
if graphe[i][j]==1:
graphe[j][i]=1
return graphe
Q9)
def transitif(graphe):
pass
#---------Fonction annexe-------------------------------
def createMiniListe(Liste):
init=[False]*8
for i in Liste:
init[i]=True
return init
def m12(listeadja):
MatriceAdja=[]
for i in listeadja:
MatriceAdja.append(createMiniListe(i))
return MatriceAdja
#----------------------------------------
def getIndex(miniListe):
init=[]
for e,i in enumerate(miniListe):
if i: init.append(e)
return init
def m21(MatriceAdja):
init=[]
for i in MatriceAdja:
init.append(getIndex(i))
return init
Q10)
def verifie_chemin(graphe,c):
None not in g[c]
```
Brice
Q1)
g1 = [[False, True, True, False, True, False, False, False], #0
[False, False, False, True, False, True, False, False], #1
[False, False, False, True, False, False, True, False], #2
[False, False, False,False, False, False, False, True], #3
[False, False, False, False, False, True, True, False], #4
[False, False, False, False, False, False, False, True], #5
[False, False, False, False, False, False, False, True], #6
[False, False, False, False, False, False, False, False]] #7
g1liste = [[1,2,4], #0
[3, 5], #1
[3, 6], #2
[7], #3
[5, 6], #4
[7], #5
[7], #6
[]] #7
Sign in with Wallet
Connect another wallet