Laberge, Vincent
(2022).
« Démonstration d'une borne supérieure du nombre d'itérations de l'algorithme de Weisfeiler-Lehman de dimension 2 » Mémoire.
Montréal (Québec), Université du Québec à Montréal, Maîtrise en mathématiques.
Fichier(s) associé(s) à ce document :
Résumé
L’algorithme de Weisfeiler-Lehman prend pour entrée une paire de graphes ayant le même nombre de sommets et soit permet de déterminer que ces derniers ne sont pas isomorphes, soit ne peut rien conclure. Le but de ce mémoire est d’éclaircir le résultat original de Kiefer et Schweitzer donnant une borne supérieure pour la complexité algorithmique de la version bidimensionnelle de cet algorithme. En plus de présenter la preuve en détails, des concepts et des étapes intermédiaires sont ajoutés pour rendre le raisonnement plus explicite. Le mémoire présente donc tout d’abord les notions de graphes colorés et de raffinements sur ces derniers. L’algorithme bidimensionnel de Weisfeiler-Lehman est alors reformulé comme étant une succession de raffinements sur des graphes colorés. Borner la complexité temporelle de l’algorithme revient alors à borner le nombre de raffinements effectués jusqu’à ce que ces derniers se stabilisent. Pour cela, les auteurs conçoivent un jeu où deux joueurs raffinent tour à tour un graphe coloré. À une partie de ce jeu est alors associé un coût. Puis, l’objectif du premier joueur est le maximiser et du deuxième joueur de le minimiser. Il est alors démontré que le nombre de raffinements qu’il est possible d’effectuer lors de l’exécution de l’algorithme bidimensionnel de Weisfeiler-Lehman est borné supérieurement par le coût associé à une partie où les deux joueurs jouent optimalement. Ce nombre est ensuite borné par l’usage d’arguments combinatoires utilisant les concepts de grandes et petites classes de couleurs et de graphes auxiliaires. Des conséquences de ce résultat en logique sont ensuite traitées.
_____________________________________________________________________________
MOTS-CLÉS DE L’AUTEUR : isomorphismes de graphes, algorithme de Weisfeiler-Lehman, graphe coloré, raffinement de graphe coloré, jeu de Kiefer-Schweitzer, grandes et petites classes de couleurs, graphe auxiliaire
| Type: |
Mémoire accepté
|
| Informations complémentaires: |
Fichier numérique reçu et enrichi en format PDF/A. |
|
Directeur de thèse: |
Villemaire, Roger |
| Mots-clés ou Sujets: |
Isomorphismes / Théorie des graphes / Algorithme de Weisfeiler-Lehman |
| Unité d'appartenance: |
Faculté des sciences > Département de mathématiques |
| Déposé par: |
Service des bibliothèques
|
| Date de dépôt: |
31 oct. 2025 10:31 |
| Dernière modification: |
31 oct. 2025 10:31 |
| Adresse URL : |
http://archipel.uqam.ca/id/eprint/18981 |
RECHERCHER
PARCOURIR
LIBRE ACCÈS
