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

Recherche:

Type: Messages; Utilisateur: dividee

Recherche: Recherche effectuée en 0,02 secondes.

  1. Votes reçus
    +0 -0
    Réponses
    44
    Affichages
    15 651

    Bon, il y a quelques temps j'avais implémenté...

    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...
  2. Votes reçus
    +0 -0
    Réponses
    44
    Affichages
    15 651

    Non de ce côté là ça va. Avec cet exemple (3...

    Non de ce côté là ça va.
    Avec cet exemple (3 noeuds A B C et une arête A->B), d'abord je calcule le graphe des CFC, qui est dans ce cas ci identique au graphe original. Je ne travaille que sur...
  3. Votes reçus
    +0 -0
    Réponses
    44
    Affichages
    15 651

    Mais c'est vrai que pour la minimalité, j'ai été...

    Mais c'est vrai que pour la minimalité, j'ai été un peu vite... A chaque étape j'élimine un "sink" et un "root", mais je peux réintroduire l'un des deux, mais pas les deux, car le graphe a...
  4. Votes reçus
    +0 -0
    Réponses
    44
    Affichages
    15 651

    Je comprends pas comment plusieurs composants...

    Je comprends pas comment plusieurs composants faiblement connexe pourrait avoir un même sink... Par définition, ils ne peuvent pas avoir de noeud en commun... Un "sink", c'est juste un noeud avec un...
  5. Votes reçus
    +0 -0
    Réponses
    44
    Affichages
    15 651

    Mais ce graphe n'est pas connexe... C'est bien...

    Mais ce graphe n'est pas connexe... C'est bien pour ça que j'avais précisé.
    Oui c'est vrai il faudrait une preuve que le graphe résultant est fortement connexe, mais il faudrait pour ça que je me...
  6. Votes reçus
    +0 -0
    Réponses
    44
    Affichages
    15 651

    Euh... Sous réserve que le graphe des CFC...

    Euh... Sous réserve que le graphe des CFC résultant est connexe, cela ne suffit pas ? Tu as un contre-exemple ?
  7. Votes reçus
    +0 -0
    Réponses
    44
    Affichages
    15 651

    Cet algo devrait être plus performant. L'idée est...

    Cet algo devrait être plus performant. L'idée est la suivante:
    D'abord, réduire le graphe à ses composants fortement connexe, comme l'a expliqué Jedai. Cet graphe ne contient pas de cycles, c'est un...
Affichage des résultats 1 à 7 sur 7