Niveaux des graphes
La décomposition en niveaux nous fournit un ordre topologique pour le graphe, puisque nous pouvons considérer les sommets "de haut en bas" (comparer les niveaux des sommets).
La décomposition en niveaux n'est possible que si le graphe ne possède pas de circuit.
Cela peut se démontrer de la manière suivante :
- soient x et y deux sommets d'un mê;me circuit, avec les arcs (x,y) et (y,x)
- Selon l'arc (x,y), nous définissons le niveau de x à 01 et le niveau de y à 1.
- Ensuite, selon l'arc (y,x), le niveau de y doit être inférieur au niveau de x, mais ces niveaux ont déjà été définis, et 1 < 0 est faux.
Algorithme de décomposition en niveaux
//initialisation ∀x : level[x] := -1; ∀x : deg[x] := degré intérieur de x; k := 0; //décomposition possible //exécution // ∀ sommet non traité // positionner x sur le niveau courant level[x] := k; // poursuivre la décomposition fin ∀ // ∀ sommet de ce niveau // ∀ sommet y incident au sommet x // rappel : A est l'ensemble des arcs ∀y : (x,y) ∈ A // retirer le sommet car il est traité // => diminuer le degré intérieur deg[y] := deg[y]-1; fin ∀ // changer de niveau k := k+1; fin ∀
Complexité
La complexité de l'algorithme de décomposition en niveaux est de (n2), bien que les deux ∀ imbriqués laissent présumer une complexité de (n3).
Nederlandse vertaling
U hebt gevraagd om deze site in het Nederlands te bezoeken. Voor nu wordt alleen de interface vertaald, maar nog niet alle inhoud.Als je me wilt helpen met vertalingen, is je bijdrage welkom. Het enige dat u hoeft te doen, is u op de site registreren en mij een bericht sturen waarin u wordt gevraagd om u toe te voegen aan de groep vertalers, zodat u de gewenste pagina's kunt vertalen. Een link onderaan elke vertaalde pagina geeft aan dat u de vertaler bent en heeft een link naar uw profiel.
Bij voorbaat dank.
Document heeft de 03/01/2010 gemaakt, de laatste keer de 26/10/2018 gewijzigd
Bron van het afgedrukte document:https://www.gaudry.be/nl/graphes-decomposition-niveaux.html
De infobrol is een persoonlijke site waarvan de inhoud uitsluitend mijn verantwoordelijkheid is. De tekst is beschikbaar onder CreativeCommons-licentie (BY-NC-SA). Meer info op de gebruiksvoorwaarden en de auteur.
Referenties
- INFOB321 - Théorie des graphes : JP Leclercq,
Cours de Théorie des Graphes et réseaux de Petri
(September 2008)
Deze verwijzingen en links verwijzen naar documenten die geraadpleegd zijn tijdens het schrijven van deze pagina, of die aanvullende informatie kunnen geven, maar de auteurs van deze bronnen kunnen niet verantwoordelijk worden gehouden voor de inhoud van deze pagina.
De auteur Deze site is als enige verantwoordelijk voor de manier waarop de verschillende concepten, en de vrijheden die met de referentiewerken worden genomen, hier worden gepresenteerd. Vergeet niet dat u meerdere broninformatie moet doorgeven om het risico op fouten te verkleinen.