next up previous contents index
suivant: Complexité asymptotique monter: La notion d'algorithme précédent: Type abstrait   Table des matières   Index


Le graphe en tant que type abstrait

Dans cette section, nous allons examiner deux façons de considérer un graphe comme un type abstrait. Différents types abstraits induisent différents algorithmes. Chacun des deux types abstraits correspond en fait à une définition de graphe du chapitre 4.

D'habitude, les algorithmes qui manipulent des graphes permettent aussi de les modifier (rajouter ou supprimer un sommet ou une arête). Dans ce livre, dans le but de simplifier les algorithmes, nous n'autorisons pas ce genre de modifications.

Le premier type abstrait que nous allons considérer met en avant les arêtes. Pour cette raison, nous allons l'appeler le type abstrait centré-arêtes. Il contient les opérations suivantes :

Les quatre premières opérations sont nécessaires pour qu'on puisse énumérer tous les sommets et toutes les arêtes. La cinquième opération correspond à la fonction $\phi$ de la définition 4.1. Les autres opérations existent pour qu'il soit possible de parcourir les sommets et les arêtes du graphe et pour pouvoir déterminer si un sommet (ou une arête) a déjà été parcouru.

Les opérations du type centré-arêtes seront notées de la manière suivante (la tradition est d'utiliser l'anglais) :

NB_NODES(G)
NB_EDGES(G)
NODE(G, i)
EDGE(G, i)
EDGE_END(e, i)
MARK_NODE(s)
UNMARK_NODE(s)
NODE_MARKED(s)
MARK_EDGE(e)
UNMARK_EDGE(e)
EDGE_MARKED(e)

Le deuxième type abstrait que nous allons considérer est similaire au premier. Mais cette fois-ci, ce sont les sommets qui sont au centre du type. En conséquence, nous allons l'appeler le type abstrait centré-sommets. En voici les opérations :

Les opérations du type centré-sommets seront notées de la manière suivante :

NB_NODES(G)
NODE(G, i)
NB_EDGES(s)
EDGE(s, i)
FOLLOW_EDGE(s, e)
MARK_NODE(s)
UNMARK_NODE(s)
NODE_MARKED(s)
MARK_EDGE(e)
UNMARK_EDGE(e)
EDGE_MARKED(e)


next up previous contents index
suivant: Complexité asymptotique monter: La notion d'algorithme précédent: Type abstrait   Table des matières   Index