Algorithmique et programmation cours avancé

Algorithmique et programmation cours licence d’informatique, tutoriel & guide de travaux pratiques en pdf.

Applications algorithmiques
Marche aléatoire dans un graphe

Soit G un graphe d régulier. Une marche aléatoire de longueur t dans le graphe G est obtenue – en choisissant aléatoirement une origine u0, – en choisissant aléatoirement, étant donnée la i-ème valeur ui, i < t, un sommet ui+1 voisin de ui.
Théorème 9 Soit G un graphe d-régulier et λ la seconde valeur propre en valeur absolue de la matrice d’adjacence; soit W un ensemble de sommets de G; on note c la quantité |W| n et on suppose que l’inégalité
((1−c)d2 + λ2)1/2 ≤
d 21/4 est satisfaite; alors, la probabilité qu’une marche aléatoire de longueur t n’ait aucun élément dans W est majorée par 2−t/4.
Ce théorème est conséquence du lemme suivant.
Lemme 14 Le nombre de marches aléatoires de longueur t qui évitent W est majoré par n(1−c)1/2((1−c)d2 + λ2)t/2. Le nombre total de marches aléatoires de longueur t étant n(d)t la probabilité est, d’après le lemme, majorée par n(1−c)1/2((1−c)d2 + λ2)t/2 n(d)t , ce qui, d’après l’hypothèse du théorème, est bien borné par 2−t/4. Preuve du lemme : On considère la projection P qui à un vecteur x à n coordonnées indexées par les sommets de G associe le vecteur obtenu en annulant toutes les coordonnées qui n’appartiennent pas à W. Le nombre nu de chemins de longueur i qui évitent W et dont l’extrémité est un sommet donné u s’interprète, avec les notations de la section 5.1.2, comme la coordonnée d’indice u du vecteur (PA)iP1. Pour le voir, on procède par récurrence. Le cas i = 0 est clair. Pour passer de i à i + 1, on observe que, par hypothèse de récurrence, le vecteur y dont les coordonnées sont nu, est donné par y = (PA)iP1. Chaque marche aléatoire de longueur i + 1 évitant W est définie en prolongeant d’un dernier choix une marche de longueur i. Celles qui atteignent un sommet donné v sont donc en nombre X{ u,v}∈E nu = X A[u,v]=1 nu =X u A[u,v]nu. On reconnaît là la v-ième coordonnée de A(PA)iP1, et on multiplie par P pour annuler les coordonnées qui n’appartiennent pas à W, afin de tenir compte de ce que le dernier choix doit lui aussi éviter W. Pour évaluer nu, on procède un peu comme dans la preuve du lemme 13 et on établit que l’application linéaire PA a une norme `2 majorée par ((1− c)d2 + λ2)1/2. Pour cela, on étudie séparément l’action de PA sur le sousespace propre engendré par le vecteur propre 1 correspondant à la valeur propre d et sur son orthogonal. Sur le sous espace engendré par 1, la norme `2 est d√1−c, comme on le voit par un calcul direct.
Sur l’orthogonal, les valeurs propres de A sont majorées en valeur absolue par|λ|et donc – comme on le voit immédiatement en diagonalisant la matrice- la norme de A est majorée par |λ|. Comme celle de P est majorée par 1, il vient ||PA||≤|λ|. En sommant les deux applications, on trouve bien, par l’inégalité de Schwarz, une norme majorée par ((1−c)d2 + λ2)1/2. Il résulte du calcul qui précède que la norme `2 de (PA)tP1 est au plus ((1−c)d2 + λ2))t/2||P1||. En fait, c’est la norme `1 qu’il faut majorer mais l’inégalité de Schwarz donne pour cette dernière un majorant de la forme √n((1−c)d2 + λ2))t/2p(1−c)n,