TD sur les graphes
===
# Exercice 1
1. Le graphe est orienté, et non pondéré.
2. G est un graphe d'ordre 10.
3. Les sommets adjacents du sommet :
- pour le sommet **1** : **5 et 3**
- pour le sommet **4** : **2 et 8**
- pour le sommet **9** : **3 et 8**
4. Le degré entrant, et sortant, du sommet 4, est égal à à **2**.
5. Un chemin possible pour le graphe G de longueur 6 est :
$$0 → 4 → 2 → 1 → 5 → 7$$
6. Un cycle possible du graphe G est :
$$1 → 5 → 7 → 6 → 2 → 1$$
7.
$$\begin{pmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
\end{pmatrix}$$
8.
```python=
G_matrice = [
[0,0,0,0,1,0,0,0,0,1],
[0,0,0,1,0,1,0,0,0,0],
[1,1,0,0,0,0,0,0,0,0],
[0,0,0,0,1,0,0,0,0,0],
[0,0,1,0,0,0,0,0,1,0],
[0,0,0,0,0,0,0,1,0,0],
[0,0,1,0,0,0,0,0,0,0],
[0,0,0,0,0,0,1,0,0,0],
[1,0,0,0,0,0,1,0,0,0],
[0,0,0,1,0,0,0,0,1,0]
]
```
9. Est-ce que le sommet 9 est adjacent au sommet 5 ?
```python
# instruction simple
print(G_matrice[5][9] == 1)
# fonction qui fait le travail
def adjacent(matrice, i, j):
"""
Return True si le sommet j est adjacent au sommet i
"""
return matrice[i,j] == 1
```
10. Liste d'adjacence :
11. En Python :
- Création de la liste par compréhension
```python
for (index, ligne) in enumerate(G_matrice):
dico[index] = [index for (index, val) in enumerate(ligne) if val == 1]
```
- liste créée :
```python
G_liste = {
0: [4, 9],
1: [3, 5],
2: [0, 1],
3: [4],
4: [2, 8],
5: [7],
6: [2],
7: [6],
8: [0, 6],
9: [3, 8],
}
```
12. Instruction permettant de déterminer si le sommet 0 est adjacent du sommet 6 :
```python
def adj(liste, i, j):
"""
Return True si i est adjacent au sommet j
"""
return i in liste[j]
```
# Exercice 2
a.
```python
def ordre_graphe_matrice(g: list)->int:
return
```
b.
```python
def ordre_graphe_liste(g: dict)->int:
return
```
c.
```python
def est_adjacent_matrice(g : list, i : int, j : int)->bool:
return
```
d.
```python
def est_adjacent_liste(g : list, i : int, j : int)->bool:
return
```