Degrés et formule d'Euler, en Python

Les fonctions.

def degres(A):
    n = len(A)
    d = []
    for i in range(n):
        s = 0
        for j in range(n):
            s = s + A[i][j]
        d.append(s)
    return d

def nb_aretes(A):
    return sum(degres(A)) // 2

def verifie_euler(A):
    return sum(degres(A)) == 2 * nb_aretes(A)

Ce que fait degres. Le degré du sommet $i$ est le nombre de $1$ de la ligne $i$ : c'est exactement la somme des coefficients de cette ligne, puisque les autres valent $0$. La double boucle coûte $n^2$ additions.

Ce que fait nb_aretes. La formule d'Euler donne $m=\frac{1}{2}{\sum }_i\mathrm{deg}(i)$. On emploie la division entière //, car $m$ est un entier et que / renverrait un flottant — un détail qui compte si l'on veut ensuite indexer une liste.

L'hypothèse, et c'est le point important. Ces fonctions supposent le graphe non orienté et sans boucle : la matrice doit être symétrique et de diagonale nulle. Si A n'est pas symétrique, degres renvoie les degrés sortants, et la formule d'Euler ne s'applique pas (la somme des degrés sortants vaut $m$, pas $2m$). Si la diagonale n'est pas nulle, une boucle serait comptée une fois là où la convention usuelle la compte deux fois.