matrice booléenne

Imaginez une grille qui répond seulement par oui ou par non. Dans la ligne A et la colonne B, un 1 signale que A est relié à B ; un 0 signale l'absence de lien. Cette grille est une matrice booléenne. Elle conserve donc la structure des relations sans compter leur nombre ni mesurer leur intensité. En combinant ses lignes et ses colonnes avec les règles ET et OU, on peut aussi repérer des chemins passant par des étapes intermédiaires.

Une matrice booléenne est un tableau rectangulaire dont chaque coefficient vaut 0 ou 1. Ces valeurs sont lues comme les valeurs logiques faux et vrai. Les dimensions peuvent être quelconques ; une matrice carrée possède autant de lignes que de colonnes.

Les calculs emploient l'algèbre de Boole. L'addition ordinaire est remplacée par le OU logique, noté ∨, et la multiplication ordinaire par le ET logique, noté ∧. Considérons deux matrices compatibles notées A et B, dont les coefficients sont désignés par les lettres minuscules a et b. L'indice i repère une ligne, l'indice j une colonne et l'indice k une position intermédiaire. Le coefficient du produit booléen situé à la ligne i et à la colonne j vaut : Il vaut donc 1 lorsqu'il existe au moins un indice k pour lequel les deux coefficients concernés valent 1.

Pour un graphe orienté simple à n sommets, une matrice booléenne carrée d'ordre n code les arcs : la ligne désigne le sommet de départ et la colonne le sommet d'arrivée. Le coefficient vaut 1 exactement quand l'arc correspondant existe. Les puissances booléennes détectent alors des chemins de longueurs successives, ce qui conduit au calcul de la clôture transitive, notamment par le procédé de Roy-Warshall.

Une matrice booléenne est un tableau dont les lignes indexent les objets de départ, les colonnes indexent les objets d'arrivée ou les propriétés observées, et chaque case contient exclusivement 0 ou 1. Pour les calculs booléens, les opérations ET et OU fixent la manière de combiner ces cases.

Dans une matrice d'adjacence, l'ordre choisi pour les sommets détermine simultanément l'ordre des lignes et celui des colonnes. Changer cet ordre déplace les 1 sans changer le graphe représenté. En revanche, inverser lignes et colonnes transpose la matrice et renverse le sens de tous les arcs.

Les dimensions et les coefficients définissent la matrice ; la couleur ou la disposition dessinée des sommets n'en font pas partie. Ces données suffisent à reconstruire les arcs d'un 1-graphe orienté et à tester, par produits booléens, l'existence de chemins.

Considérons trois sommets ordonnés A, B et C, avec seulement deux arcs : A vers B et B vers C. Leur graphe et sa grille de 0 et de 1 rendent visible la correspondance entre chaque arc et chaque coefficient.

1. Placez les sommets dans l'ordre A, B, C pour les lignes comme pour les colonnes. La matrice d'adjacence obtenue est :

2. Pour savoir si A rejoint C en deux arcs, combinez chaque étape intermédiaire. Le passage par B donne 1 ∧ 1, donc le coefficient de la ligne A et de la colonne C vaut 1 dans le carré booléen de M.

3. Le produit complet est : Il révèle l'unique chemin de longueur 2, A→B→C.

4. Le OU coefficient par coefficient entre M et son carré ajoute ce chemin aux arcs directs. On obtient des 1 aux positions (A, B), (B, C) et (A, C). Un contrôle direct consiste à énumérer les deux arcs et leur seul enchaînement possible.

En théorie des graphes, la matrice booléenne sert à enregistrer seulement l'existence des arcs. Si les arcs portent des distances, des capacités ou plusieurs occurrences, une matrice pondérée ou une structure multigraphe conserve mieux cette information supplémentaire.

Pour une relation binaire, chaque ligne correspond à un premier élément et chaque colonne à un second. Les produits booléens repèrent les compositions de la relation ; l'algorithme de Roy-Warshall est préférable à l'énumération manuelle lorsque la grille devient grande.

En logique formelle et en informatique théorique, ces matrices permettent de propager des possibilités : un résultat vaut 1 dès qu'au moins une chaîne d'étapes compatibles existe. Une matrice numérique classique reste nécessaire si l'on doit compter ces chaînes plutôt que constater leur existence.

Matrice binaire. Elle contient elle aussi seulement 0 et 1, mais ces nombres peuvent être traités avec l'arithmétique ordinaire. Ainsi, 1 + 1 vaut 2 dans un calcul numérique, tandis que 1 ∨ 1 vaut 1 dans l'algèbre booléenne.

Matrice d'adjacence. C'est le rôle joué par une matrice lorsqu'elle code les liaisons d'un graphe. Une matrice booléenne peut toutefois décrire toute relation oui-non, sans qu'un graphe soit explicitement étudié.

Matrice pondérée. Ses coefficients portent une valeur telle qu'une distance ou un coût. Deux arcs de coûts différents peuvent avoir la même valeur 1 dans la matrice booléenne, car celle-ci ne conserve que leur présence.

Plusieurs arcs entre deux sommets. Une seule case ne peut contenir que 0 ou 1. Dans un multigraphe, elle signale donc la présence d'au moins un arc, mais perd leur multiplicité ; il faut une matrice de comptage pour la conserver.

Boucles sur la diagonale. Un 1 en position (i, i) indique un arc du sommet i vers lui-même. Une diagonale nulle n'est donc pas une propriété de toute matrice booléenne ; elle dépend du graphe ou de la relation codée.

Chemins de longueur nulle. La clôture transitive stricte réunit les chemins d'au moins un arc. Si la convention inclut aussi chaque sommet relié à lui-même par un chemin vide, il faut calculer la clôture réflexive-transitive et ajouter la matrice identité booléenne.

Produit ordinaire. Une entrée positive du produit numérique compte des marches de longueur fixée, qui peuvent répéter des sommets ou des arcs, alors qu'une entrée 1 du produit booléen affirme seulement qu'il en existe au moins une. Employer l'addition classique peut donc produire 2 ou davantage et changer le sens du calcul.

Algèbre de Boole présente les règles logiques ET et OU qui remplacent la multiplication et l'addition dans les calculs booléens.

Matrice d'adjacence approfondit la traduction d'un graphe en tableau et l'interprétation précise de ses lignes, colonnes et coefficients.

Graphe orienté et non-orienté aide à reconnaître quand le sens des arêtes impose une matrice non symétrique.