théorie des graphes
Répondre à la discussion
Affichage des résultats 1 à 2 sur 2

théorie des graphes



  1. #1
    Abderhman

    théorie des graphes


    ------

    Bonjour à tous
    j'ai une question concernant le plus court chemin entre deux nœuds dans un graphe. Supposons que j'attribue un poids a^k à un chemin de longueur k. La somme de tout les chemins pondérés est alors donné par la matrice B=(I-aA)^{-1} , A étant la matrice d'adjacence. On me dit que la longueur du chemin le plus court entre deux noeuds i et j est donné par la limite quand a tend vers 0 de dlog Bij/dlog a, je n'arrive pas à comprendre pourquoi

    J'espère que la question est clair sinon n'hésitez pas à me demander des précisions, merci pour votre aide

    -----

  2. #2
    Resartus

    Re : théorie des graphes

    B vaut 1+aA+(aA)^2+...
    Le terme ij de A^n est le nombre de parcours valant exactement n.
    Quand a tend vers zero, le terme prépondérant dans Bij sera celui de chemin le plus court k : on a Bij=a^k*(A^k)ij+o(a^k)

    Ensuite, si on prend le logarithme on a log(Bij)=klog(a)+cste et en dérivant k=dlogBij/dloga

Discussions similaires

  1. Théorie des graphes(graphes faiblement triangulé)
    Par saad17453 dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 20/12/2014, 19h13
  2. théorie des graphes
    Par gantaro dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 10/11/2012, 13h00
  3. Théorie des graphes
    Par invitea35bb224 dans le forum Mathématiques du supérieur
    Réponses: 7
    Dernier message: 19/04/2012, 00h08
  4. Theorie des graphes
    Par BioBen dans le forum Mathématiques du supérieur
    Réponses: 1
    Dernier message: 29/11/2007, 18h25
  5. Théorie des graphes et graphes de liaisons
    Par Eogan dans le forum Mathématiques du supérieur
    Réponses: 2
    Dernier message: 08/12/2006, 22h59