Recherche:Théorie des matrices logiques/Application: calcul de la clique maximum d'un graphe
Le problème de la clique maximum est l'un des piliers de la théorie de la complexité (21 problèmes de Karp).
Une clique-n est un graphe complet à n sommets.
Étant donné un graphe G, on cherche ici à connaître le nombre de sommets de la plus grande clique qui soit un sous-graphe de G.
Exemple, matrice d'adjacence du graphe G:
- Une clique-4 se laisse apercevoir dans la matrice d'adjacence de G, en haut à gauche. Il y en a 9 autres, mieux dissimulées.
- G ne contient aucune clique-5. La clique-4 est donc la clique maximum de G.
Matrice canonique transcrivant le problème de recherche de cliques-4 dans G:
On cherche ici à appliquer le graphe complet à 4 sommets sur G.
Les cellules n'appartenant pas à la diagonale principale de la matrice canonique sont toutes identiques à la matrice d'adjacence de G.
La matrice canonique est satisfaisable. Elle cesserait de l'être si l’on ajoutait un nouveau segment (graphe complet à 5 sommets).
Cette matrice possède un degré de régularité tel qu’il est possible, tout au moins pour certaines opérations (dont la recherche des cliques, autrement dit des 1 de la table diagonale), de ne pas la construire et de travailler directement sur une seule cellule, c'est-à-dire sur la matrice d'adjacence de G.
La matrice logique devient virtuelle.
En quelque sorte, la TML prête ici ses algorithmes à la théorie des graphes.
