Accueil du site > MOCA > Représentation matricielle d’un graphe
Aller à ...
OMFG
Informations
Dans la rubrique MOCA , cet article a été écrit par b3nj et publié le 18 mars 2006.
4339 personnes ont affiché cette page et sa popularité est de 13.
Pebkac
Mots clefs
I see dead pixels.
Outils
SYN
Représentation matricielle d’un graphe

Matrice booléenne - matrice aux arcs d’un graphe

Soit le graphe orienté G = comportant N sommets :

PNG - 3.4 ko
Exemple de graphe orienté pour réaliser les matrices booléennes et aux arcs

Il peut être représenté par une matrice d’adjacence (matrice booléenne) ou par une matrice aux arcs.

Matrice d’adjacence ou matrice booléenne :

M = \left(a_{ij}\right) ou i et j varient de 1 à N
On a pour chaque élément de la matrice :

  • a_{ij} = 1 si \left(i,j\right) \in U
  • a_{ij} = 0 si \left(i,j\right) \notin U
ABCDE
A01101
B01100
C00010
D10001
E10100

Matrice aux arcs :

A = \left(a_{ij}\right) ou i et j varient de 1 à N
On a pour chaque élément de la matrice :

  • a_{ij} = ij si \left(i,j\right) \in U
  • a_{ij} = 0 si \left(i,j\right) \notin U
ABCDE
A0ABAC0AE
B0BBBC00
C000CD0
DDA000DE
EEA0EC00
pages : 1 2 3 >>
Poster un message