matrice d'incidence

Imaginez un réseau de trois stations reliées par quatre liaisons. On trace un tableau : chaque ligne représente une station et chaque colonne une liaison. Une case indique simplement si la station touche la liaison correspondante.

Dans un graphe non orienté, une liaison ordinaire touche deux sommets : sa colonne contient donc deux 1. Une boucle part d’un sommet et y revient ; elle y compte deux incidences, notées 2. Si les liaisons ont un sens, les signes + et − distinguent départ et arrivée.

Soit un graphe possédant n sommets et p arêtes ou arcs. Sa matrice d’incidence comporte n lignes, une par sommet, et p colonnes, une par arête ou arc. Le coefficient situé à la ligne du sommet i et à la colonne de l’élément j indique comment ce sommet est incident à cet élément. L’ordre choisi pour les lignes et les colonnes fait partie de la représentation, sans modifier le graphe encodé.

Dans la convention non orientée de cette fiche, le coefficient vaut 1 lorsque le sommet est une extrémité d’une arête ordinaire, 2 lorsqu’une boucle est attachée à ce sommet, et 0 sinon. Chaque colonne d’une arête ordinaire contient ainsi deux 1 ; celle d’une boucle contient un seul 2. Cette règle accepte aussi les arêtes parallèles, qui peuvent produire des colonnes identiques.

Dans la convention orientée retenue ici, l’origine d’un arc reçoit +1 et son extrémité reçoit −1 ; les autres sommets reçoivent 0. La somme d’une colonne correspondant à un arc non bouclé vaut alors 0. Inverser tous les signes est une autre convention courante : elle décrit la même incidence si elle est appliquée partout. Une boucle orientée exige une convention explicitement annoncée, car son origine et son extrémité coïncident.

La construction repose sur quatre données. La liste ordonnée des sommets fixe les lignes. La liste ordonnée des arêtes ou arcs fixe les colonnes. Les extrémités de chaque liaison déterminent les coefficients non nuls. Enfin, pour un graphe orienté, le sens de chaque arc détermine leur signe.

Une colonne dépend donc d’une liaison et de ses extrémités, tandis qu’une ligne rassemble toutes les liaisons incidentes à un sommet. Permuter les sommets permute les lignes ; permuter les liaisons permute les colonnes. Ces changements de présentation ne changent pas la connectivité. En revanche, modifier une extrémité change les coefficients et donc le graphe encodé. La position des sommets sur un dessin, la longueur des traits et leurs croisements ne participent pas à la matrice.

Considérons le graphe non orienté illustré par trois sommets A, B et C. L’arête e₁ relie A à B, e₂ relie B à C, e₃ relie C à A et e₄ est une boucle attachée à C. Les lignes suivront l’ordre A, B, C et les colonnes l’ordre e₁, e₂, e₃, e₄.

1. Pour e₁, A et B sont les deux extrémités : la première colonne est formée de 1, 1 et 0.
2. Pour e₂, les extrémités sont B et C : la deuxième colonne est formée de 0, 1 et 1.
3. Pour e₃, les extrémités sont C et A : la troisième colonne est formée de 1, 0 et 1.
4. Pour e₄, la boucle compte deux fois au sommet C : la dernière colonne est formée de 0, 0 et 2.

La matrice obtenue est :Le contrôle se refait colonne par colonne : chacune a une somme égale à 2, y compris la boucle. Les sommes des lignes valent respectivement 2, 2 et 4 ; elles comptent les incidences attachées à chaque sommet.
Mini-cas orienté. Orientons e₁ de A vers B en gardant l’ordre A, B, C. Avec la convention de cette fiche, son origine A reçoit +1, son extrémité B reçoit −1 et C reçoit 0 : la colonne devient donc 1, −1, 0. Sa somme vaut 0, ce qui contrôle un arc non bouclé ; à la lecture, les signes indiquent directement le départ A et l’arrivée B.

Pour saisir un réseau, on remplit une colonne à la fois à partir des extrémités de chaque liaison. Ce format est préférable à un simple dessin lorsque l’on veut automatiser des calculs sur de nombreux sommets et arêtes.

Pour contrôler des données non orientées, on vérifie que chaque colonne a une somme égale à 2 avec la convention des boucles notées 2. Une autre somme signale une extrémité oubliée ou une convention différente.

Pour étudier des flux, des cycles ou des coupes, la version orientée est souvent plus adaptée, car les signes séparent départ et arrivée. Si seul le voisinage direct entre sommets importe, une matrice d’adjacence peut être plus immédiate.

Matrice d’adjacence. Ses lignes et ses colonnes représentent toutes deux des sommets ; une case indique si deux sommets sont voisins. Dans une matrice d’incidence, les colonnes représentent au contraire des arêtes ou des arcs. Pour trois sommets et quatre arêtes, la première est carrée de taille 3, tandis que la seconde a 3 lignes et 4 colonnes.

Liste d’incidence. Elle énumère, pour chaque sommet, les liaisons qui le touchent. Elle porte une information comparable, mais sous forme de listes de longueurs variables. La matrice impose une case pour chaque couple formé d’un sommet et d’une liaison, ce qui facilite les opérations algébriques.

Boucle orientée. Elle exige une convention explicitement annoncée, car son origine et son extrémité coïncident. Si les contributions +1 et −1 sont additionnées dans la même case, elles s’annulent et donnent une colonne nulle : celle-ci signale l’arc bouclé, mais la matrice seule ne permet pas d’identifier son sommet d’attache. Il faut alors conserver au besoin la liste des arcs.

Convention de signe. Certains textes placent −1 à l’origine et +1 à l’arrivée. Le symptôme est une matrice opposée colonne par colonne à celle attendue. Il faut vérifier la convention avant de comparer deux résultats, car aucune des deux orientations de signe n’est universelle.

Arêtes parallèles. Deux arêtes reliant les mêmes sommets donnent deux colonnes identiques dans la version non orientée. Il ne faut pas fusionner ces colonnes : leur multiplicité appartient au graphe.

Sommet isolé. Un sommet sans arête incidente produit une ligne entièrement nulle. Cette ligne n’est pas superflue : la supprimer ferait disparaître le sommet de la représentation.

Graphe orienté et non-orienté. Cette fiche précise le rôle du sens des liaisons, qui commande les signes dans la matrice orientée.

Sous-graphe. Elle aide à reconnaître ce qui subsiste lorsqu’on sélectionne certaines lignes et colonnes avec leurs incidences compatibles.