IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Théorie des graphes


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre actif
    Inscrit en
    Avril 2007
    Messages
    17
    Détails du profil
    Informations forums :
    Inscription : Avril 2007
    Messages : 17
    Par défaut Théorie des graphes
    bonjour,

    y a t-il une méthode pour trouver le nombre de toutes les chaines dans un graphe

  2. #2
    Membre Expert
    Avatar de Franck Dernoncourt
    Homme Profil pro
    PhD student in AI @ MIT
    Inscrit en
    Avril 2010
    Messages
    894
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : PhD student in AI @ MIT
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2010
    Messages : 894
    Par défaut
    Tu peux essayer de googler "number of paths in a graph" ou "list all paths graph".

    Exemple de liens :


    Sinon comme cela j'utiliserais la somme des A^i, avec
    • i indice de sommation allant de 0 au nombre de noeuds du graphe ;
    • A est la matrice d'adjacence du graphe.

  3. #3
    Membre actif
    Inscrit en
    Avril 2007
    Messages
    17
    Détails du profil
    Informations forums :
    Inscription : Avril 2007
    Messages : 17
    Par défaut
    et pour le nombre de chaines on transformera le graphe en graphe non orienté

  4. #4
    Membre Expert
    Avatar de Franck Dernoncourt
    Homme Profil pro
    PhD student in AI @ MIT
    Inscrit en
    Avril 2010
    Messages
    894
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 38
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : PhD student in AI @ MIT
    Secteur : Enseignement

    Informations forums :
    Inscription : Avril 2010
    Messages : 894
    Par défaut
    Citation Envoyé par aljabr Voir le message
    et pour le nombre de chaines on transformera le graphe en graphe non orienté
    Pourquoi ?

    Sinon l'idée de la somme des A^i n'est qu'une piste, mais je ne sais pas du tout si cela est correct pour ton problème. Notamment, il faut faire attention aux cycles. Mais je serais étonné qu'il n'y ait rien d'intéressant sur Google avec les mots clés que je t'ai donnés.

  5. #5
    Membre actif
    Inscrit en
    Avril 2007
    Messages
    17
    Détails du profil
    Informations forums :
    Inscription : Avril 2007
    Messages : 17
    Par défaut
    merci

    j'ai trouvé pas mal de sites intéressants sur le google mais les méthodes présentées sont un peu compliquées pour être appliquées manuellement

    par exemple j'ai trouvé cet algorithme

    path // is a stack (initially empty)
    seen// is a set
    def stuck(x)
    if x == t
    return False
    for each neighbor y of x
    if y not in seen
    insert y in seen
    if !stuck(y)
    return False
    return True
    def search(x)
    if x == t
    print path
    seen = set(path)
    if stuck(x)
    return
    for each neighbor y of x
    push y on the path
    search(y)
    pop y from the path

    Here search does the exhaustive search and stuck could be implemented in DFS style (as here) or in BFS style.

  6. #6
    Membre Expert
    Homme Profil pro
    Ingénieur développement logiciels
    Inscrit en
    Septembre 2008
    Messages
    1 190
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Ingénieur développement logiciels
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2008
    Messages : 1 190
    Par défaut
    On insert le code dans des balises CODE pour plus de lisibilité.

    Et l'algo que tu présente n'a rien de compliqué, exécute le sur des exemples simple à la main et tu trouveras vite leur logique.

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Idées de Projets en théorie des graphes ou autres.
    Par Iori Yagami dans le forum Sujets
    Réponses: 20
    Dernier message: 22/10/2007, 16h47
  2. Théorie des graphes : algo de Kruskal et files de priorités
    Par AlKoLiK dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 16/05/2007, 10h47
  3. Théorie des graphes
    Par aminos40 dans le forum MATLAB
    Réponses: 2
    Dernier message: 10/04/2007, 22h33
  4. [Théorie des Graphes] Les opérateurs AND et OR
    Par bitou dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 18/03/2007, 03h01
  5. Théorie des graphes : Représentation GRAPHIQUE d'une matrice d'adjacence
    Par jm_gouy dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 03/05/2006, 16h53

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo