On rappelle que la matrice d'adjacence \(A\) associée à un graphe fini, simple, dont les sommets sont numérotés, est une matrice carrée à \(n\) lignes et \(n\) colonnes si \(n\) est l'ordre 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.
Cette matrice est représentée en Python par une liste contenant \(n\) listes de longueur \(n\), représentant les \(n\) lignes.
On considère des graphes simples non orientés. Dans ce cas la matrice d'adjacence est symétrique.
On utilise ici la définition d'un arbre au sens le plus général du terme: un graphe simple connexe à \(n\) sommets est un arbre si et seulement si le nombre d'arêtes est \(n-1\).
Exemple
Les deux graphes sont des arbres.
Le graphe à gauche a deux sommets et une arête. Sa matrice d'adjacence est [[0,1],[1,0]].
Le graphe à droite à quatre sommets et trois arêtes. Sa matrice d'adjacence est [[0,0,1,1],[0,0,1,0],[1,1,0,0],[1,0,0,0]]
Si on enlève une arête à un graphe, celui-ci n'est plus connexe donc n'est plus un arbre.
Si on ajoute une arête à un graphe, celui-ci possède alors un cycle donc n'est plus un arbre.
Question
Écrire le code de la fonction est_arbre qui prend en paramètre une matrice d'adjacence représentant un graphe supposé connexe et renvoie True si le graphe est un arbre et False sinon.
###(Dés-)Active le code après la ligne # Tests (insensible à la casse) (Ctrl+I)
Entrer ou sortir du mode "deux colonnes" (Alt+: ; Ctrl pour inverser les colonnes)
Entrer ou sortir du mode "plein écran" (Esc)
Tronquer ou non le feedback dans les terminaux (sortie standard & stacktrace / relancer le code pour appliquer)
Si activé, le texte copié dans le terminal est joint sur une seule ligne avant d'être copié dans le presse-papier
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)