Niveaux des graphes

Inhaltsverzeichnis

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).

Deutsche Übersetzung

Sie haben gebeten, diese Seite auf Deutsch zu besuchen. Momentan ist nur die Oberfläche übersetzt, aber noch nicht der gesamte Inhalt.

Wenn Sie mir bei Übersetzungen helfen wollen, ist Ihr Beitrag willkommen. Alles, was Sie tun müssen, ist, sich auf der Website zu registrieren und mir eine Nachricht zu schicken, in der Sie gebeten werden, Sie der Gruppe der Übersetzer hinzuzufügen, die Ihnen die Möglichkeit gibt, die gewünschten Seiten zu übersetzen. Ein Link am Ende jeder übersetzten Seite zeigt an, dass Sie der Übersetzer sind und einen Link zu Ihrem Profil haben.

Vielen Dank im Voraus.

Dokument erstellt 03/01/2010, zuletzt geändert 26/10/2018
Quelle des gedruckten Dokuments:https://www.gaudry.be/de/graphes-decomposition-niveaux.html

Die Infobro ist eine persönliche Seite, deren Inhalt in meiner alleinigen Verantwortung liegt. Der Text ist unter der CreativeCommons-Lizenz (BY-NC-SA) verfügbar. Weitere Informationen auf die Nutzungsbedingungen und dem Autor.

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

Inhaltsverzeichnis Haut

Referenzen

  1. Buch Sprache des Dokuments:fr INFOB321 - Théorie des graphes : JP Leclercq, Cours de Théorie des Graphes et réseaux de Petri (September 2008)

Diese Verweise und Links verweisen auf Dokumente, die während des Schreibens dieser Seite konsultiert wurden, oder die zusätzliche Informationen liefern können, aber die Autoren dieser Quellen können nicht für den Inhalt dieser Seite verantwortlich gemacht werden.
Der Autor Diese Website ist allein dafür verantwortlich, wie die verschiedenen Konzepte und Freiheiten, die mit den Nachschlagewerken gemacht werden, hier dargestellt werden. Denken Sie daran, dass Sie mehrere Quellinformationen austauschen müssen, um das Risiko von Fehlern zu reduzieren.

Inhaltsverzeichnis Haut