Selon la définition 5.2, le degré d'un sommet est égal au nombre de brins d'arêtes incidents au sommet. Ici, nous allons définir formellement le degré moyen d'un graphe.
L'objectif de cette section est de trouver différents algorithmes pour calculer le degré moyen.
Pour le type abstrait centré-arêtes, le travail est
presque trivial. On applique directement le
théorème 5.1,
qui nous donne
en fonction
de
, puis on divise par
.
Voici l'algorithme sous une forme plus ``algorithmique'' :
Cet algorithme est particulièrement simple. Il ne contient ni
boucle, ni test. En fait, son temps d'exécution est constant,
indépendant de la taille (i.e., du nombre de sommets et du nombre
d'arêtes) du graphe. Dans ce cas, on dit que la complexité
asymptotique est . Cela signifie que la forme générale de la
fonction du temps de cet algorithme est la même que celle de la
fonction constante
dont la valeur est
pour toute valeur
de
. Un algorithme de complexité
est optimal.
Nous avons donc trouvé le meilleur algorithme pour calculer le
degré moyen d'un graphe. Malheureusement, cet algorithme
n'est utilisable que dans le cas centré-arêtes.
Si le type abstrait est centré-sommets, nous sommes obligés d'examiner chaque sommet pour déterminer le nombre de brins d'arêtes incidents à ce sommet. Voici un algorithme possible :
Cet algorithme contient une boucle qui est exécutée une fois pour
chacun des sommets du graphe. Le corps de la boucle ne contient que des
opérations élémentaires. Cela donne une complexité asymptotique
. Autrement dit, l'algorithme prend un
temps d'exécution proportionnel au nombre de sommets du graphe. On
dit aussi qu'un tel algorithme est linéaire ou qu'il a
une complexité linéaire. Dans notre cas, il faut préciser qu'il est
linéaire par rapport au nombre de sommets du graphe.
Le temps d'exécution d'un algorithme dépend donc du type abstrait,
i.e., des opérations élémentaires disponibles. Dans le cas du type
abstrait centré-arêtes, on a un algorithme de complexité ,
alors que dans le cas du type abstrait centré-sommets, on a
un algorithme de complexité
.
Mais attention à ne pas conclure qu'un des
types abstraits est meilleur que l'autre. Pour d'autres
problèmes les performances sont inversées.