Composantes Fortement Connexes

Rappel :

Composantes simplement connexes

Nous pouvons définir la connexité simple de la manière suivante : x, ∀y : ∃ chaîne entre x et y.

La notion « simplement connexe » (en anglais, “weakly connected”) peut s'appliquer à l'ensemble du graphe (si pour tout couple de sommet x et y il existe une chaîne entre x et y), ou à une partie du graphe (nous parlons alors de composante simplement connexe). Cette notion de connexité simple est assez évidente lorsque nous avons peu de sommets et que nous représentons graphiquement le graphe, comme dans l'exemple ci dessous. Nous pouvons dès lors constater qu'au sein d'une composante simplement connexe (csc) chaque sommet est accessible au départ de n'importe quel sommet de la composante.

Graphes simplement connexes

Si mn-1, toutes les arêtes2sont reliées. Dans ce cas, nous avons une seule composante simplement connexe.

Si m < n-1, nous nous trouvons en présence de plus d'une composante simplement connexe.

L'exemple ci-contre montre que notre graphe comporte deux composantes simplement connexes.
Les sommets {1, 2, 3, 4, 5} forment une composante simplement connexe, et les sommets {6,7} forment la deuxième.

Cet exemple montre un graphe simple non-orienté. Qu'en est-il pour les graphes orientés ?

Dans notre premier exemple, si nous appliquons cete définition le ne comportait qu'une seule csc composée des sommets {1,3}, et cinq csc composées chacune d'un seul sommet ({2}, {4}, {5}, {6}, et {7}). Or ce n'est pas le cas.
Dans le cas de graphes orientés nous devons considérer les arcs comme des arêtes, et nous pouvons ensuite appliquer la définition de la csc qui dit que chaque sommet de la composante simplement connexe doit être accessible depuis n'importe quel sommet de la même composante.

Si notre graphe comportait un huitième sommet qui n'était relié à aucun autre sommet, ou s'il était relié à lui même par une boucle, il serait considéré comme une composante simplement connexe, car tout sommet isolé respecte la définition de la csc. Nous aurions alors trois composantes simplement connexes.

Un graphe complet est donc toujours simplement connexe, mais tout graphe simplement connexe n'est pas forcément complet, car la connexité relie x et y par des chaînes (peu importe la longueur), mais un graphe complet a la contrainte que x et y soient reliés par seulement des chaînes (ou chemins) de longueur 1.

Inhaltsverzeichnis Haut

Composantes fortement connexes

Nous pouvons définir la connexité forte de la manière suivante : x, ∀y : ∃ chemin entre x et y et ∃ chemin entre y et x.

Nous pourrions considérer chaque composante simplement connexe d'un graphe non-orienté comme une composante « fortement connexe » (en anglais, “strongly connected”) de ce graphe, en considérant chaque arête comme deux arcs de sens opposés, mais nous réserverons uniquement la connexité forte aux graphes orientés.

Comme dans le cas de la connexité simple, la connexité forte peut s'appliquer à un graphe en entier (graphe fortement connexe), ou le graphe peut être décomposé en composantes fortement connexes.

Un graphe complet est donc toujours un graphe fortement connexe (car nous pouvons remplacer les arêtes par deux arcs aux directions opposées), mais l'inverse n'est pas toujours vrai (pour être complet, les chemins doivent avoir une longueur 1).

De par sa définition, un graphe fortement connexe contient forcément des circuits.

Pour chercher les composantes fortement connexes d'un graphe, nous pouvons utiliser les algorithmes de Foulkes ou de Malgrange.

Inhaltsverzeichnis Haut

Algorithme de Foulkes

Fonctionnalités de l'algorithme de Foulkes

  • L'algorithme de Foulkes permet de construire les composantes fortement connexes d'un graphe.

Caractéristiques de l'algorithme de Foulkes

L'algorithme de Foulkes présume que nous avons préalablement effectué une recherche de la fermeture transitive de notre graphe (par exemple avec l'algorithme de Warshall).

Si deux sommets appartiennent à la même composante fortement connexe, nous pouvons en déduire certaines similitudes au niveau de la matrice d'accessibilité (ils peuvent accéder au même ensemble de sommets). Nous devrons donc chercher au sein de la matrice de fermeture transitive les sommets pour lesquels la ligne dans cette matrice est identique. Ils appartiennent donc à la même composante fortement connexe.

Inhaltsverzeichnis Haut

Complexité de l'algorithme de Foulkes

La complexité générale est de Ordre de grandeur(n3) car le calcul de la matrice de fermeture transitive est déjà de Ordre de grandeur(n3).

Algorithme de Malgrange

Fonctionnalités de l'algorithme de Malgrange

  • L'algorithme de Malgrange permet de construire les composantes fortement connexes d'un graphe.

Caractéristiques de l'algorithme de Malgrange

  • Choisir arbitrairement un sommet x
  • Chercher les successeurs de x, soit S(x) au moyen de DFS
  • Chercher les prédécesseurs de x, soit P(x) au moyen de DFS
  • S(x) ∩P(x) nous donne la composante fortement connexe contenant x.

Inhaltsverzeichnis Haut

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-cfc.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.  simplement connexe : entspricht “weakly connected” en anglais

  2.  Arête ou arc : Nous utilisons ici le terme arête pour désigner aussi bien une arête qu'un arc

  3.  fortement connexe : entspricht “strongly connected” en anglais

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)
  2. Zeigen Sie - pdf-Dokument Sprache des Dokuments:fr Algorithmique des graphes : Jean-Michel Hélary, Circuits. Composantes fortement connexes. (2004)

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