p
u
b
l
i
c
i
t
é
publicité
+ Répondre à la discussion Actualité déjà publiée
Page 3 sur 3 PremièrePremière 123
  1. #41
    Membre à l'essai
    Inscrit en
    décembre 2008
    Messages
    24
    Détails du profil
    Informations forums :
    Inscription : décembre 2008
    Messages : 24
    Points : 23
    Points
    23

    Par défaut

    Citation Envoyé par millie Voir le message
    En fait, dès que le graphe est faiblement connexe, il y a une méthode vachement plus simple que de passer par des flots.
    Laisse moi deviner: à partir du graphe réduit on cherche à compléter les arcs existants pour trouver un cycle hamiltonien ?

  2. #42
    Membre Expert
    Homme Profil pro
    Inscrit en
    mars 2007
    Messages
    900
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Belgique

    Informations forums :
    Inscription : mars 2007
    Messages : 900
    Points : 1 311
    Points
    1 311

    Par défaut

    Bon, il y a quelques temps j'avais implémenté l'algo suivant, mais je n'avais pas posté car je ne sais pas prouver qu'il est bon. Mais bon voilà.
    C'est sur l'idée de Jean-Marc Bourguet à la seconde page de cette discussion.

    1) réduire la graphe à ses composants fortement connexes
    2) si ce graphe ne contient qu'un seul noeud, on a fini
    3) trouver un couple (puits, source) tel que la source ne domine pas le puits (c'est à dire tel qu'il n'existe pas de chemin de la source au puits)
    - s'il un tel couple existe, ajouter cette arc et continuer en 3)
    - sinon relier n'importe quel puits à n'importe quelle source et continuer en 1)

    [edit: J'avais oublié le code]
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    smallestForSC g = applyReduce edgesToAdd g
        where edgesToAdd g' | null (drop 1 $ vertices g') = []
                            | null undominated = let newEdge = (head roots, head sinks) in 
                                                     newEdge : (smallestForSC $ buildG (bounds g') (newEdge:edges g')) 
                            | otherwise = let newEdge = head undominated in
                                              newEdge : (edgesToAdd $ buildG (bounds g') (newEdge:edges g'))
                            where
                   roots = [ix | (ix, deg) <- assocs (indegree g'), deg == 0]
                   sinks = [ix | (ix, deg) <- assocs (outdegree g'), deg == 0]
                   undominated = [(s,r) | [s,r] <- sequence [sinks, roots], not $ path g' r s]
    Pour les fonctions annexes, voir premier post de Jedai dans cette discussion.
    [/edit]

  3. #43
    Membre régulier
    Inscrit en
    décembre 2004
    Messages
    147
    Détails du profil
    Informations forums :
    Inscription : décembre 2004
    Messages : 147
    Points : 73
    Points
    73

    Par défaut Suite ?

    Je vois qu'il n'y a toujours pas eu de réponse à ce fil depuis un moment.
    Le défi est-il terminé ? Quelle serait la (ou les) solution ?

  4. #44
    Rédacteur/Modérateur

    Avatar de millie
    Profil pro
    Inscrit en
    juin 2006
    Messages
    6 944
    Détails du profil
    Informations personnelles :
    Localisation : Luxembourg

    Informations forums :
    Inscription : juin 2006
    Messages : 6 944
    Points : 9 797
    Points
    9 797

    Par défaut

    Citation Envoyé par dest Voir le message
    Je vois qu'il n'y a toujours pas eu de réponse à ce fil depuis un moment.
    Le défi est-il terminé ? Quelle serait la (ou les) solution ?
    Les défis ne se ferment jamais

    Pour l'instant, il n'y a pas eu de solution complète sans erreurs (sauf la brute-force) (EDIT : ah si, celle de dividee doit être bonne )

    Et il y a encore moins eu de réponses avec preuve.
    Je ne répondrai à aucune question technique en privé

  5. #45
    Alp
    Alp est déconnecté
    Expert Confirmé Sénior

    Avatar de Alp
    Homme Profil pro
    Inscrit en
    juin 2005
    Messages
    8 583
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 26
    Localisation : France, Bouches du Rhône (Provence Alpes Côte d'Azur)

    Informations forums :
    Inscription : juin 2005
    Messages : 8 583
    Points : 11 409
    Points
    11 409

Discussions similaires

  1. Théorie des graphes (connexité des graphes)
    Par hajara dans le forum Mathématiques
    Réponses: 3
    Dernier message: 24/03/2013, 16h27
  2. la forte connexité
    Par Black.Rose dans le forum Mathématiques
    Réponses: 3
    Dernier message: 01/01/2009, 12h00
  3. Réponses: 1
    Dernier message: 29/12/2008, 10h00
  4. [Graphe] Vérifier connexité après retrait d'un sommet
    Par Nil_ct dans le forum Général Algorithmique
    Réponses: 1
    Dernier message: 17/01/2008, 16h19
  5. Test de connexité sur graphe non orienté
    Par condor_01 dans le forum Général Algorithmique
    Réponses: 4
    Dernier message: 25/10/2007, 00h01

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