Calcul de la règle de distance avec la matrice d'adjacence

En découvrant un théorème fabuleux en cours de maths, j’ai eu une idée folle.

Le théorème en question est si A est la matrice d’adjacence d’un graphe, alors Ani,j est le nombre de chemins de taille n allant de i à j.

On peut donc calculer les puissances 1, 2, 3, 4, 5 de la matrice d’adjacence de la WoT à chaque changement, et vérifier la règle de distance d’un nœud en O(N), sans récursivité.

Le gros inconvénient est qu’une telle matrice est de taille O(N^2), et que tout changement est aussi en temps O(N^2).

J’imagine bien que ça ne sera jamais utilisé en pratique, mais c’est amusant.


Pour le fun, j’ai dessiné la matrice d’adjacence de la WoT (une image de taille N×N, un pixel blanc pour 0 et noir pour 1), mais le résultat était décevant : quelques pixels noirs perdus dans un océan de vide. Il faudrait tester avec les transactions, ça serait peut-être plus joli.

2 Likes