Geen cache-versie.

Caching uitgeschakeld. Standaardinstelling voor deze pagina:ingeschakeld (code LNG204)
Als het scherm te langzaam is, kunt u de gebruikersmodus uitschakelen om de cacheversie te bekijken.

Niveaux des graphes

Inhoudsopgave

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

  1. //initialisation
  2. ∀x : level[x] := -1;
  3. ∀x : deg[x] := degré intérieur de x;
  4. k := 0;
  5. //décomposition possible
  6. decomp := true;
  7.  
  8. //exécution
  9. tant_que ∃ x : level[x] = -1 ∧ decomp faire
  10.  
  11. 	decomp :=false;
  12.  
  13. 	// ∀ sommet non traité
  14. 	∀x : deg[x] = 0 ∧ level[x] = -1 faire
  15.  
  16. 		// positionner x sur le niveau courant
  17. 		level[x] := k;
  18.  
  19. 		// poursuivre la décomposition
  20. 		decomp := true;
  21.  
  22. 	fin ∀
  23.  
  24. 	// ∀ sommet de ce niveau
  25. 	∀x : level[x] = k faire
  26.  
  27. 		// ∀ sommet y incident au sommet x
  28. 		// rappel : A est l'ensemble des arcs
  29. 		∀y : (x,y) ∈ A
  30.  
  31. 			// retirer le sommet car il est traité
  32. 			// => diminuer le degré intérieur
  33. 			deg[y] := deg[y]-1;
  34.  
  35. 		fin ∀
  36.  
  37. 		// changer de niveau
  38. 		k := k+1;
  39.  
  40. 	fin ∀
  41.  
  42. fin tant_que

Complexité

La complexité de l'algorithme de décomposition en niveaux est de Ordre de grandeur(n2), bien que les deux ∀ imbriqués laissent présumer une complexité de Ordre de grandeur(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.

Notes

  1. ↑ Numérotation des niveaux : La numérotation des niveaux débute à zéro.

Inhoudsopgave Haut

Referenties

  1. boek Taal van het document:fr 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.

Inhoudsopgave Haut