On rappelle que la matrice d'adjacence \(A\) associée à un graphe fini et simple dont les sommets sont numérotés de \(1\) à \(n\) est une matrice carrée à \(n\) lignes et \(n\) colonnes si \(n\) est le nombre de sommets du graphe. Pour tout couple \((i, j)\), le coefficient \(A_{i, j}\) vaut \(1\) si les sommets numéro \(i\) et numéro \(j\) sont adjacents et \(0\) sinon.
Un graphe et sa matrice d'adjacence
flowchart LR
D((1)) --- G((4))
D --- F((3))
E --- H((5))
D --- E((2))
F --- G
F --- H
Cette matrice est représentée en Python par une liste contenant \(n\) listes de longueur \(n\), représentant les \(n\) lignes.
Question 1 : Produit de matrices
Le produit de deux matrices carrées \(A\) et \(B\) à \(n\) lignes et \(n\) colonnes est la matrice \(P=A\times B\) telle que pour tout couple \((i, j)\) :
Si les matrices \(A\) et \(B\) sont représentées respectivement par les listes a et b, alors la matrice \(P\) est représentée par la liste p telle que pour tout couple \((i, j)\) valide :
On considère un graphe, fini, simple et non orienté, la matrice d'adjacence associée \(A\) et la matrice \(A^2= A \times A\). Les deux propriétés suivantes sont équivalentes :
Il existe un couple \((i, j)\), avec \(i \neq j\), tel que les coefficients \(A_{i, j}\) et \(A^2_{i, j}\) sont non nuls ;
Le graphe possède un cycle de longueur \(3\), qu'on appelle un triangle.
Par exemple, les deux graphes ci-dessous possèdent un triangle.
flowchart LR
A((1)) --- B((2))
A --- C((3))
B --- C
D((1)) --- G((4))
D --- F((3))
E --- H((5))
D --- E((2))
F --- G
F --- H
Par contre, ce graphe ne possède pas de triangle :
flowchart LR
A((1)) --- B((2))
Écrire une fonction triangle qui prend en paramètre une matrice d'adjacence associée à un graphe et renvoie True si le graphe possède un triangle et False sinon.
Une version valide de la fonction produit demandée à la question précédente est déjà incluse dans cet éditeur. Vous pouvez l'utiliser sans l'importer.
# Tests(insensible à la casse)(Ctrl+I)