3.1 Élé ments de la théo rie des graphes
63
© Dunod – Toute reproduction non autorisée est un délit.
Le graphe complet symé trique de n som met est noté K n (ou clique de n som mets),
en honneur au mathématicien polonais Kuratowski.
Une autre manière de décrire un graphe est d’uti li ser sa matrice d’inci dence
som mets/arcs : chaque ligne de cette matrice est asso ciée à un som met, et chaque
colonne est asso ciée à un arc du graphe.
Dans la colonne cor res pon dant à un arc (i, j) autre qu’une boucle, figurent la
valeur 11 sur la ligne cor res pon dant au som met i, la valeur 21 sur la ligne cor res -
pon dant au som met j et la valeur 0 sur toutes les autres lignes.
Dans une colonne cor res pon dant à une boucle (i, i) figurent la valeur 11 sur la
ligne cor res pon dant au som met i et la valeur 0 sur toutes les autres lignes. La figure 3.5
donne cette matrice pour le graphe de notre exemple (les valeurs 0 ont été omises).
Figure 3.5 Matrice d'incidence
Une autre manière de repré sen ter un graphe est d’uti li ser la liste chaînée de ses
suc ces seurs
1
. La figure 3.5 bis donne la liste des suc ces seurs pour notre exemple.
Cette repré sen ta tion compacte d’un graphe est aisée à obte nir en machine en uti li sant
les struc tures de don nées dyna miques exis tant désor mais dans tous les lan gages de
pro gram ma tion.
. . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
C
B
B
B
D
D
E
E
E
A
A
A
C
C
C
successeurs de A
successeurs de B
successeurs de C
successeurs de D
successeurs de E
Figure 3.5 bis Listes de successeurs
1. Rap pe lons que l’ensemble des suc ces seurs d’un som met x se note : G
1
(x), ou bien G(x).