Publicité
+ Répondre à la discussion Actualité déjà publiée
Page 1 sur 3 123 DernièreDernière
Affichage des résultats 1 à 20 sur 45
  1. #1
    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 773
    Points
    9 773

    Par défaut Défi N°5 : Forte connexité et graphes

    Bonjour,

    Pour ce cinquième défi, l'équipe de developpez.com vous propose un challenge un peu plus difficile.

    Le problème est composé de 2 problèmes assez proches. Vous pouvez donc proposer une solution pour le problème que vous souhaitez.

    Challenge :


    Il y a 2 versions possibles (la première ayant l'avantage d'avoir une formulation plus clair et une solution unique)

    Variante 1 :
    Pour un graphe orienté donné, donner le nombre minimal d'arc à ajouter afin qu'il devienne fortement connexe.

    Variante 2 :
    Pour un graphe orienté donné, chercher un ensemble d'arcs de taille minimal tel que l'ajout des arcs au graphe le rende fortement connexe.

    Par exemple, pour le graphe suivant :


    Une solution serait : (BF, FA).

    On entend par taille minimal, la taille tel que pour tout ensemble d'arc de taille strictement inférieur, l'ajout de ces arcs au graphe ne le rende pas fortement connexe.

    Il n'y a pas de règles quand à la représentation d'un graphe, cela peut être une implémentation récursive ou encore tout simplement [sommet: [A,B,C,D,E,F], arc: [[A,B], [B,C]] ]

    La proposition peut être avec ou sans preuve.



    Les règles

    Il n'y a pas de règle particulière (évidemment, il faut que la solution proposée fonctionne). Vous pouvez proposer des solutions aussi bien dans des langages fonctionnels (caml, haskell, scheme, lisp...) qu'impératif. Le public pourra ainsi juger du code suivant divers critères :
    • la maintenabilité
    • la simplicité
    • le fait qu'il soit optimisé


    Le public pourra également juger les différences entre une solution fonctionnelle et une solution impérative. Il lui sera ainsi plus facile de voir, pour un même problème, les différences entre divers paradigmes.

    Pour répondre, il vous suffit de poster à la suite.

    A vos claviers
    de votre participation.

    __________________________
    Sujet proposé par millie
    Je ne répondrai à aucune question technique en privé

  2. #2
    Expert Confirmé Sénior
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 180
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : avril 2003
    Messages : 6 180
    Points : 8 322
    Points
    8 322

    Par défaut

    Pour commencer par une solution de référence, exploration exhaustive des solutions :
    Code Haskell :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    import Data.Graph
    import qualified Data.Set as S
    import Data.Array
    import Data.List
    import Control.Arrow
    import Data.Maybe
    
    smallestForSC g = 
        snd . fromJust . find (isSC . fst) 
                . concatMap (map (addEdges g &&& id) . flip combi absentEdges) $ [0..]
            where 
              absentEdges = 
                  S.elems $ S.fromList (pairs $ vertices g) S.\\ S.fromList (edges g)
    
    addEdges g es = buildG b es'
        where b = bounds g
              es' = es ++ edges g
    
    isSC = null . drop 1 . scc
    
    combi 0 _ = [[]]
    combi n [] = []
    combi n (x:xs) = map (x:) (combi (n-1) xs) ++ combi n xs
    
    pairs xs = concat [ [(x,y),(y,x)] | x:ys <- tails xs, y <- ys ]
    Bien sûr, c'est légèrement trop lent pour être utilisable

    --
    Jedaï

  3. #3
    Expert Confirmé Sénior
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 180
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : avril 2003
    Messages : 6 180
    Points : 8 322
    Points
    8 322

    Par défaut

    Ceux qui l'ont essayé ont dû pouvoir constater que la solution ci-dessus était parfaitement inutilisable sur des graphes de taille raisonnable. Nous pouvons néanmoins examiner la structure du problème et nous rendre compte qu'en réalité nous pouvons réduire tous les éléments d'un même composant fortement connexe à un seul noeud sans changer la solution :
    Code Haskell :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    reduceToSCC g = (g', translate)
        where
          roots = map rootLabel . scc $ g
          m = M.fromList couples
          couples = zip [1..] roots
          translate = (m M.!)
          g' = buildG (1, M.size m) 
               $ [ (x,y) | ((x,x'),(y,y')) <- pairs couples, path g x' y' ]
    
    applyReduce f g = map (tr *** tr) . f $ g'
        where (g', tr) = reduceToSCC g
    Je ferais remarquer que applyReduce ne présuppose rien à propos de f sinon qu'elle renvoie la solution comme une liste d'arêtes, on peut l'appliquer sur n'importe quel algorithme pour l'améliorer.

    --
    Jedaï

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

    Informations forums :
    Inscription : mars 2007
    Messages : 895
    Points : 1 300
    Points
    1 300

    Par défaut

    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 DAG. De fait, certains noeuds n'ont pas d'arc entrant et d'autres pas d'arc sortant. Pour que ce graphe (et le graphe original) soit fortement connexe, le degré entrant et sortant de chaque noeud doit être au moins 1. Si N noeuds ont un degré sortant 0 et M un degré entrant de 0, le nombre minimum d'arêtes à ajouter est max(N,M). C'est suffisant, mais il faut également que le graphe soit (faiblement) connexe.

    Le principe est de toujours connecter un noeud avec un degré sortant de 0 (attention, toujours dans le graphe des composants fortement connexes, pas dans le graphe original) à un noeud avec un degré entrant de 0.

    La première chose à faire est donc d'ajouter des arêtes pour le rendre connexe. La façon la plus économique (en nombre d'arêtes) est bien sûr de constituer un seul cycle. Donc choisir un noeud de d° entrant 0 et un noeud de d° sortant 0 dans chaque composant (faiblement) connexe (il y en a forcément au moins un dans chaque composant) et ajouter ces arêtes.

    Ensuite, lorsque le graphe est connexe, le plus simple est de procéder récursivement: ajouter une arête en choisissant un noeud de d° 0 entrant et un sortant, les connecter, ce qui crée un cycle, donc on recalcule le graphe des composants fortement connexes et on recommence (il y a certainement moyen d'améliorer l'algo à ce niveau-là). On continue jusqu'à ce que le graphe se réduise à un seul noeud.

    Pour l'implémentation, j'ai continué sur la lancée de Jedai (après avoir passé 2 heures à comprendre son code). Mais je suis nul en Haskell alors c'est pas aussi élégant... J'espère seulement que c'est correct. Toute amélioration est bienvenue.

    Voilà le code complet:
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    module Main where
    
    import Data.Graph
    import qualified Data.Set as S
    import Data.Array
    import Data.List
    import Control.Arrow
    import Data.Maybe
    
    import Data.Tree
    import qualified Data.Map as M
    
    addEdges g es = buildG b es'
        where b = bounds g
              es' = es ++ edges g
    
    pairs xs = concat [ [(x,y),(y,x)] | x:ys <- tails xs, y <- ys ]
    
    reduceToSCC g = (g', translate)
        where
          roots = map rootLabel . scc $ g
          m = M.fromList couples
          couples = zip [1..] roots
          translate = (m M.!)
          g' = buildG (1, M.size m) 
               $ [ (x,y) | ((x,x'),(y,y')) <- pairs couples, path g x' y' ]
    
    applyReduce f g = map (tr *** tr) . f $ g'
        where (g', tr) = reduceToSCC g
    
    smallestForSC g = applyReduce edgesToAdd g
        where edgesToAdd g' | length (vertices g') == 1 = []
                            | isConnected = newEdge : (smallestForSC $ addEdges g' [newEdge])
                            | otherwise = edgesForConn ++ (smallestForSC $ addEdges g' edgesForConn)
                            where
                    isConnected = null $ drop 1 comp
                    comp = map flatten $ components g'
                    newEdge = (outVertex &&& inVertex) (head comp)
                    outVertex = fromJust . find ((==0) . (outdegree g' !))
                    inVertex = fromJust . find ((==0) . (indegree g' !))
                    edgesForConn = map (outVertex *** inVertex) $ zip comp (tail comp ++ [head comp])                        
    
    graph1 = buildG (1,5) [(1,2),(1,3),(3,4),(4,1)]
    graph2 = buildG (1,7) [(1,2),(1,3),(2,4),(4,5),(3,5),(6,3),(6,7),(7,5),(4,1)]
    
    main = do
        print $ smallestForSC graph1
        print $ smallestForSC graph2
    Quelqu'un aurait-il de gros graphes avec les solutions précalculées pour tester mon programme ?

  5. #5
    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 773
    Points
    9 773

    Par défaut

    Citation Envoyé par dividee Voir le message
    Le principe est de toujours connecter un noeud avec un degré sortant de 0 (attention, toujours dans le graphe des composants fortement connexes, pas dans le graphe original) à un noeud avec un degré entrant de 0.
    Si ceci est ton principe. Cela ne marche pas à tous les coups
    Je ne répondrai à aucune question technique en privé

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

    Informations forums :
    Inscription : mars 2007
    Messages : 895
    Points : 1 300
    Points
    1 300

    Par défaut

    Euh... Sous réserve que le graphe des CFC résultant est connexe, cela ne suffit pas ? Tu as un contre-exemple ?

  7. #7
    Expert Confirmé Sénior
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 180
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : avril 2003
    Messages : 6 180
    Points : 8 322
    Points
    8 322

    Par défaut

    Citation Envoyé par dividee Voir le message
    Quelqu'un aurait-il de gros graphes avec les solutions précalculées pour tester mon programme ?
    Je n'ai pas vérifié en détail l'implémentation, mais a priori vu ta description tu n'ajoute jamais plus d'arêtes que max(N / in = 0 , N / out = 0) donc la minimalité va de soi. Pour la correction, une joli preuve serait mieux, mais pour s'en convaincre on peut essayer QuickCheck. J'avais déjà concocté un petit module de test pour mes essais (qui allaient dans le même sens que toi mais je n'ai pas eu l'intuition de travailler sur la connexité faible) donc je l'ai appliqué à ton algorithme (une simple propriété d'une ligne) et le résultat semble valider ton algorithme et le trouver relativement rapide même !!

    Félicitation !

    --
    Jedaï

  8. #8
    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 773
    Points
    9 773

    Par défaut

    Citation Envoyé par dividee Voir le message
    Euh... Sous réserve que le graphe des CFC résultant est connexe, cela ne suffit pas ? Tu as un contre-exemple ?
    Comment ça sous réserve que le graphe des CFC résultant est connexe ?

    Bah, si t'as un graphe non fortement connexe et que t'ajoutes un arc et qu'il est fortement connexe, c'est que ça va
    Je ne répondrai à aucune question technique en privé

  9. #9
    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 773
    Points
    9 773

    Par défaut

    Avec ça, je suis OK :

    La façon la plus économique (en nombre d'arêtes) est bien sûr de constituer un seul cycle. Donc choisir un noeud de d° entrant 0 et un noeud de d° sortant 0 dans chaque composant (faiblement) connexe (il y en a forcément au moins un dans chaque composant) et ajouter ces arêtes.
    Mais la ligne du dessus ne suffisait pas tout seul

    Mais pourquoi est-ce le nombre minimal ?
    Je ne répondrai à aucune question technique en privé

  10. #10
    alex_pi
    Invité(e)

    Par défaut

    Citation Envoyé par millie Voir le message
    Si ceci est ton principe. Cela ne marche pas à tous les coups
    Il me semble que si à chaque fois que tu obtiens une composante fortement connexe, tu l'écrase en un seul sommet, ça devrait marcher, nan ? En effet, si on suppose qu'on a un graphe sans aucune composante fortement connexe (et où on vire tout lien de type "S -> S" avec S un sommet) et tel que tout les sommets ont au moins un lien sortant, on a forcément un graphe fortement connexe. En effet, si on suit les lien sortants, soit on arrive à un sommet sans lien sortant (contradictoire), soit on revient sur un lien déjà visité, et donc on a une composante fortement connexe non écrasée.
    Et pour les connexion entrante, c'est pareil, il suffit de retourner tout les liens.

    Donc je pense que ça marche ! Pas forcément que ça donne l'optimum par contre :-\

  11. #11
    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 773
    Points
    9 773

    Par défaut

    Si c'était le seul principe, mon contre exemple est le suivant :

    Graphe de 3 sommets, (A,B,C) et un seul arc (A,B)

    Tu peux choisir A comme ayant un degré entrant de 0 et B comme ayant un degré sortant de 0. Ce qui est un mauvais plan évidemment.
    Je ne répondrai à aucune question technique en privé

  12. #12
    alex_pi
    Invité(e)

    Par défaut

    Citation Envoyé par millie Voir le message
    Si c'était le seul principe, mon contre exemple est le suivant :

    Graphe de 3 sommets, (A,B,C) et un seul arc (A,B)

    Tu peux choisir A comme ayant un degré entrant de 0 et B comme ayant un degré sortant de 0. Ce qui est un mauvais plan évidemment.
    Ah oui effectivement là, pour la minimalité on repassera ;-)

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

    Informations forums :
    Inscription : mars 2007
    Messages : 895
    Points : 1 300
    Points
    1 300

    Par défaut

    Citation Envoyé par millie Voir le message
    Si c'était le seul principe, mon contre exemple est le suivant :

    Graphe de 3 sommets, (A,B,C) et un seul arc (A,B)

    Tu peux choisir A comme ayant un degré entrant de 0 et B comme ayant un degré sortant de 0. Ce qui est un mauvais plan évidemment.
    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 replonge dans la théorie des graphes... La minimalité ça me parait évident...

  14. #14
    Expert Confirmé Sénior
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 180
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : avril 2003
    Messages : 6 180
    Points : 8 322
    Points
    8 322

    Par défaut

    Citation Envoyé par dividee Voir le message
    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 replonge dans la théorie des graphes... La minimalité c'est effectivement assez évident...
    Non, le graphe résultant est bien fortement connexe, mais la minimalité ne marche pas (va falloir que je regarde de plus près l'algo). Par ailleurs le contre exemple donné par millie marcherait sur ton algo mais c'est plus un hasard qu'autre chose. Tu as négligé le fait que plusieurs composantes faiblement connexes pouvaient avoir le même sink. De mon côté je me suis bien cassé la tête la dessus aussi. J'ai rajouté un test de minimalité à mon quickcheck, en supposant que max(N / in = 0, N / out = 0) soit bien atteignable.

    --
    Jedaï

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

    Informations forums :
    Inscription : mars 2007
    Messages : 895
    Points : 1 300
    Points
    1 300

    Par défaut

    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 degré sortant de 0, non ?

  16. #16
    Expert Confirmé Sénior
    Avatar de Jedai
    Homme Profil pro
    Enseignant
    Inscrit en
    avril 2003
    Messages
    6 180
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Côte d'Or (Bourgogne)

    Informations professionnelles :
    Activité : Enseignant

    Informations forums :
    Inscription : avril 2003
    Messages : 6 180
    Points : 8 322
    Points
    8 322

    Par défaut

    Citation Envoyé par dividee Voir le message
    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 degré sortant de 0, non ?
    Je confonds mes tentatives avec ton algorithme, oublie ça.

    --
    Jedaï

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

    Informations forums :
    Inscription : mars 2007
    Messages : 895
    Points : 1 300
    Points
    1 300

    Par défaut

    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 préalablement été rendu connexe, ce qui implique qu'il y aura obligatoirement soit des arêtes entrantes soit des arêtes sortantes du nouveau noeud résultant de la contraction du CFC qui peut être introduite (sauf à la dernière étape ou il n'y pas plus qu'un seul noeud bien sûr). Du coup, il se pourrait que l'algorithme introduise jusqu'à (N | in = 0) + (N | out = 0) - 1 nouvelles arêtes dans le pire des cas.

    Maintenant, y a-t'il toujours une solution en n'introduisant que max (N | in = 0, N | out = 0) arêtes ?

    PS: je sais que je devrais dire "arc" plutôt que "arête". Mais c'est trop tard, je vais pas corriger tous mes posts précédents, et je continuerais de toute façon à me tromper

  18. #18
    alex_pi
    Invité(e)

    Par défaut

    Comment choisis-tu les arcs qui rendent ton graphe connexe ? Parce que dans l'exemple de millie, (trois sommets, A B C, un arc A->B), si tu as eu la mauvaise idée de choisir un arc A->C, il te faudra encore deux arcs, alors qu'un arc B->C fera que tu n'en as plus besoin que d'un. Donc cette phase aussi est importante !

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

    Informations forums :
    Inscription : mars 2007
    Messages : 895
    Points : 1 300
    Points
    1 300

    Par défaut

    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 celui-là par la suite. Ensuite, je calcule les composants (faiblement) connexes. Il y en a 2: (AB) et (C). Je relie chaque fois un noeud de degré sortant 0 d'un composant connexe avec un noeud de degré entrant 0 dans le composant suivant (en les prenant dans un ordre arbitraire), jusqu'à avoir fait le tour des composants faiblement connexe. Donc ici, si (AB) est le premier composant et (C) le second, je choisirais B->C et pas A->C. A l'étape suivante, je choisirais C -> A et j'ai fini la boucle. Dans ce cas-ci ça se termine ici et tout va bien.
    Le problème serait plutôt après, pour traiter les "sink" et les "root" qui restent.

  20. #20
    Membre chevronné

    Inscrit en
    juillet 2008
    Messages
    228
    Détails du profil
    Informations forums :
    Inscription : juillet 2008
    Messages : 228
    Points : 641
    Points
    641

    Par défaut

    Je propose un algo de type impératif

    1. Étant donné une liste d'arêtes, créer un tableau associatif de noeuds qui ont la structure suivante:
    • Arêtes sortantes
    • Nombre d'arêtes entrantes
    • Marqueur "visité"

    2. Parcourir le graphe en utilisant le marqueur "visité" pour détecter un cycle
    Note: seuls les noeuds avec nombre d'arêtes entrantes supérieur à 0 peuvent appartenir à un cycle
    3. Réduire le cycle en appliquant aux noeuds:
    Pour toutes les arêtes sortantes
    • Si le noeud destination est marqué "visité"
    • Alors réduire le nombre d'arêtes entrantes du noeud destination
    • Sinon ajouter l'arête sortante au noeud combiné

    Le nombre d'arêtes entrantes du noeud combiné est la somme du nombre d'arêtes entrantes des noeuds du cycle.
    4. Associer tous les noeuds du cycle au noeud combiné dans le tableau associatif
    5. Répéter depuis le point 2 jusqu'à éliminer tous les cycles
    6. Trouver un noeud avec nombre d'arêtes entrantes = 0 (source)
    7. Parcourir le graphe depuis ce noeud jusqu'à un noeud avec nombre d'arêtes sortantes = 0 (sink) en marquant les noeuds visités
    8. Ajouter une arête depuis ce noeud jusqu'à une source non marquée
    9. Répéter depuis 7 jusqu'à ce qu'il n'y ait plus de source non marquée
    10. Ajouter une nouvelle arête depuis le sink jusqu'à la source du point 6
    11. Réduire le cycle créé en 10.
    On a maintenant un graphe en étoile: il y a une seule source, le noeud combiné
    12. Rechercher tous les noeuds avec nombre d'arêtes sortantes = 0 (sink) et ajouter une arête vers la source-
    Fini!

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •