Fermeture transitive
La fermeture transitive d'un graphe orienté : accessibilité, matrice d'accessibilité, algorithme de Warshall et son coût, calcul par parcours et composantes fortement connexes lues dans la matrice.
- 27 cartes
- 6 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
- Mises en situation
- Comprendre
Quelques cartes du deck
Accessibilité : de quoi s'agit-il ?
Voir la réponse
Propriété d'un sommet j par rapport à un sommet i : il existe dans le graphe orienté un chemin d'au moins un arc qui mène de i à j.
Un arc direct n'est qu'un cas particulier : A est accessible depuis B si on peut enchaîner plusieurs arcs. Un sommet n'est accessible depuis lui-même que s'il est sur un circuit.
Qu'affiche ce programme ?
```python
r = [[0, 1, 0, 0], [0, 0, 1, 0], [0, 0, 0, 0], [1, 0, 0, 0]]
for k in range(4):
for i in range(4):
for j in range(4):
r[i][j] = r[i][j] or (r[i][k] and r[k][j])
print(r[3])`[1, 1, 1, 0][1, 0, 0, 0][1, 1, 0, 0][1, 1, 1, 1]
Voir la réponse
[1, 1, 1, 0]Le sommet 3 a un arc vers 0, qui va vers 1, qui va vers 2 : il atteint 0, 1 et 2. Personne n'atteint le sommet 3 lui-même, donc la case (3, 3) reste à 0.
[1, 0, 0, 0]est la ligne de départ : la fermeture ne l'a pas complétée.Dans la fermeture transitive, il y a un arc de i vers j si et seulement s'il existe dans le graphe de départ un … de i vers j.
Voir la réponse
Dans la fermeture transitive, il y a un arc de i vers j si et seulement s'il existe dans le graphe de départ un chemin de i vers j.
Le chemin peut avoir n'importe quelle longueur, un arc ou plusieurs. La fermeture contient donc tous les arcs du graphe, et en ajoute pour chaque raccourci.
Fermeture transitive : de quoi s'agit-il ?
Voir la réponse
Graphe sur les mêmes sommets qui contient un arc de i vers j chaque fois qu'un chemin mène de i à j dans le graphe de départ.
Elle rend la relation « transitive » : si i atteint j et j atteint k, i atteint k directement. Elle répond d'un coup à toutes les questions « peut-on aller de i à j ? ».