CNS graphe orienté fortement connexe
Bonjour
Je viens d'écrire un petit programme en Python pour simuler un réseau de pages Web reliées entre elles - en fait un graphe orienté. J'ai fait ce travail dans le cadre de mon cours de SNT (=informatique en seconde), dans le but de montrer une méthode de PageRank : les élèves choisissent les liens entre les pages, puis une balise parcourt le graphe aléatoirement. On compte ensuite le nombre de passages sur chaque sommet (=site Web), ce qui fournit un estimateur de sa pertinence.
Le problème, c'est qu'il faut que le graphe soit fortement connexe (par exemple, c'est un peu idiot si on tourne en rond entre deux pages). Voici donc ma question : y a-t-il une méthode, utilisant la matrice d'un graphe orienté et ses puissances successives, permettant de savoir si ce graphe est fortement connexe ou non (i.e. on peut relier n'importe quels sommets 2 à 2) ?
J'avais envie de dire que pour une matrice de taille n, il suffisait que $\min\left(M_{i,j},M^2_{i,j},\cdots,M^n_{i,j}\right)$ soit non nul. Mais je n'ai pas vraiment d'argument à avancer.
Merci de m'avoir lu !
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Je suis d'accord avec ta CNS rebellin.
À propos de la remarque de @Math Coss : Si le graphe possède un chemin orienté non trivial qui boucle, alors $\sum_{k\in \Bbb N} M^k$ possède des coefficients égaux à $+\infty $. En effet, le coefficient $(i, i) $ de cette matrice est le nombre de chemins de longueur quelconque de $i$ à $i$. Et on peut répéter autant de fois qu'on veut une boucle donnée. Donc $I-M$ n'est pas inversible dans ce cas.