Chemins graphes, etc...

[invite4c324090]

Bonjour dans le cadre de mon tipe j'aurai besoin de ces resultats, dont je n'arrive à sortir que des cas particuliers:

Y a-t-il une CNS(ou au moins CS) simple et surtout pratique pour qu'un graphe soit fortement connexe?

Comment calculer le nombre de chemins de n arcs d'un point à un autre pour un graphe fortement connexe quelcquonque? (si on considere que chaque sommet est relie au plus une fois aux autres et jamais à lui même c'est le produit des matrices d'adjacence)

Dans le cadre d'une marche aléatoire(d'abord en dimension 2, puis sur un graphe fortement connexe) combien-en esperance bien sûr- a-t-on atteint de points distincts en n iterations?

Si vous avez quelquechose, des cas particuliers, des algo,des idees , n'importe quoi ça m'aiderai.Je suis completement nouveau de ces concepts et l'aprentissage sans cours n'est pas simple...Je suis surtout bloqué pour commencer...après ça ira...

Merci à ceux qui m'aideront^^
-----

[acx01b]

salut,

pour le nombre de chemins (sans boucles) de longueur n le plus simple est probablement de faire un parcours en profondeur en s'arrêtant à une profondeur n

pour le fortement connexe :
- un graphe non orienté et simplement connexe est fortement connexe
- dans un graphe ortienté : un sous graphe fortement connexe contenant un sommet s c'est l'intersection de 2 ensembles de noeuds: les noeuds que l'on peut atteindre en partant de s et les noeuds que l'on peut atteindre en partant de s et en empruntant les arcs à l'envers
- une composante simplement connexe sera l'union de ces 2 ensembles de noeuds

sinon c'est ton projet ? il y a un objectif spécifique ?

[invite0fb72cf8]

Dans le cadre d'une marche aléatoire(d'abord en dimension 2, puis sur un graphe fortement connexe) combien-en esperance bien sûr- a-t-on atteint de points distincts en n iterations?

A mon avis, ce qui va être intéressant, c'est d'étudier la loi de puissance de cette espérance (çàd comment cette espérance va augmenter avec le temps).

Vu que pour une marche aléatoire: <x(t)> ~ t^(1/2), tu sait déjà n(t), le nombre de points distincts dans le graphe va être borné par <n(t)> < t. C'est une première estimation pas du tout précise, mais ça donne déjà des idées...

Sinon, je ne sais pas trop le niveau qui t'es demandé, mais j'ai l'idée vague qu'en contrôlant la récurrence de ta marche aléatoire (ce qui est possible), tu puisses essayer de contrôler les boucles qui vont se former, et avoir une meilleure estimation.

Si ça te dépasse, il reste évidement la solution de facilité: la simulation informatique.

A+

Ising

[invite4c324090]

Merci à vous deux.
L'objectif est à la base d'établir un algorithme de recherche à base d'une marche aléatoire(ça existe déjà->essayer de trouver des solutions tout seul) En fait ces questions sont pour essayer de demontrer l'efficacité (probable) de mon algorithme...le vrai problème c'est de n'avoir etudié ni les matrices ni les graphes(je suis en sup)...du coup je suis moyennement à l'aise.Mais ça va s'améliorer on devrais aborder les matrices demain, ça devrai combler mes lacunes théoriques...Si ça vous interesse l'idee de base serait, en considerant un certain critère (un mot par exemple) de considerer qu'un point du graphe(qui represente une page du net par exemple) à une valeur plus ou moins eleve de correspondance avec ce critere(si je cherche thermodynamique, cuisinetv.com est classé ourri, wikipedia un peu moin, les qqs page de wiki qui cite la thermo sont bien classé, et LA page sur la thermo est classée au top) Ca fait des espèces de tache avec au centre la meilleur page du coin.L'idée est de lancer une marche pour essayer de reperer les taches, et à dès qu'on en repère une l'explorer de manière determinisme...ce qui permet d'eviter l'exploration de zone completement morte(genre groland magazine si on cherche tjr thermo) en les traversant juste.La marche permet de remplacer l'echantillonage qu'on aurait fait sur un espace discret par exemple...

D'ailleurs s'il y a des pro du web, vous savez si la complexité temporelle pour "passer" d'une page à une autre est négligeable devant un algo de recherche sur une page?En gros est-ce que j'ai le droit de negliger le nombre d'arc empruntés sur mon graphe?

Sinon ça va vite devenir une usine à gaz ce projet...déjà que...

[A voir en vidéo sur Futura]