Une arête s'écrit deux fois, et la boucle compte double

1. Une arête $\{u,v\}$ s'écrit deux fois : $v$ dans la liste de $u$, et $u$ dans celle de $v$.

/* Ajoute l'arête non orientée {u, v}. DEUX écritures pour UN lien. */
void ajouter_arete(int u, int v) {
    assert(voisins[u][0] < DEG_MAX && voisins[v][0] < DEG_MAX);
    voisins[u][0] = voisins[u][0] + 1;  voisins[u][voisins[u][0]] = v;
    voisins[v][0] = voisins[v][0] + 1;  voisins[v][voisins[v][0]] = u;
}

La place occupée est donc $\Theta (n+2m)$, soit $\Theta (n+m)$ — la constante $2$ disparaît dans la notation, mais elle est bien là dans la mémoire, et elle compte quand on dimensionne un tableau.

La faute classique est d'oublier la seconde écriture. Le graphe reste utilisable : un parcours partant de $u$ trouve $v$. Mais il n'est plus symétrique, et un parcours partant de $v$ ne trouve pas $u$. On a écrit un graphe orienté en croyant écrire un graphe non orienté, et le défaut ne se révèle que sur certains sommets de départ — le pire genre de défaut.

2. Il trouve $2m$, et non $m$. Mesuré sur le triangle $\{0,1\},\{1,2\},\{2,0\}$ : la somme des longueurs de listes vaut $6$ pour $3$ arêtes. C'est le lemme des poignées de main lu à l'envers : la longueur de la liste de $u$ est $d(u)$, et ${\sum }_{s}d(s)=2m$. Il faut diviser par deux — ou, si l'on préfère, ne compter que les couples $(u,v)$ avec $u<v$.

3. Une boucle apporte $2$ au degré. C'est une convention, et le lemme des poignées de main est ce qui l'impose.

Prenons deux sommets $a$ et $b$, l'arête $\{a,b\}$ et une boucle en $a$ : $m=2$, donc $\sum d(s)$ doit valoir $4$.

• Si la boucle comptait $1$ : $d(a)=2$, $d(b)=1$, somme $3\ne 4$. Le lemme tombe.
• Si elle compte $2$ : $d(a)=3$, $d(b)=1$, somme $4$. Le lemme tient.

Vérifié par le calcul. La raison profonde est que la démonstration du lemme compte les extrémités d'arêtes : une arête en a deux, et celles d'une boucle sont toutes deux au même sommet.

Le piège de programmation qui en découle : dans une liste d'adjacence, une boucle en $u$ doit être écrite deux fois dans la liste de $u$ pour que sa longueur soit le degré. Presque personne ne le fait, et presque tous les programmes traitent la boucle comme un cas particulier — ce qui explique que le programme officiel écarte les multi-arcs et que beaucoup d'exercices supposent le graphe simple, c'est-à-dire sans boucle. Quand une convention coûte un cas particulier partout, on l'évite en interdisant l'objet, et c'est ce que fait ici la définition usuelle.