Recherche:Théorie des matrices logiques/Application: calcul de la clique maximum d'un graphe

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
Début de la boite de navigation du chapitre
Application: calcul de la clique maximum d'un graphe
Icône de la faculté
Chapitre no 14
Recherche : Théorie des matrices logiques
Chap. préc. :Application: coloriage d'un graphe simple
Chap. suiv. :Sommaire
fin de la boite de navigation du chapitre
Icon falscher Titel.svg
En raison de limitations techniques, la typographie souhaitable du titre, « Théorie des matrices logiques : Application: calcul de la clique maximum d'un graphe
Théorie des matrices logiques/Application: calcul de la clique maximum d'un graphe
 », n'a pu être restituée correctement ci-dessus.

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:

ApplicationCalculdelacliquemaximumd'ungraphePage27.svg
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:

ApplicationCalculdelacliquemaximumd'ungraphePage26.svg

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.