Worldlex Wiki La profondeur est une constante à maintenir lors d'une recherche en profondeur. Le point le plus bas de (c'est-à-dire juste avant que , la profondeur de tous les voisins de dans l'arbre de recherche en profondeur) et le point le plus bas de tous les enfants de est un sommet de coupure (ou point d'articulation) séparant deux composantes biconnexes si et seulement s'il existe un enfant tel que . Cette propriété peut être testée une fois que le parcours en profondeur a renvoyé tous les enfants de ne soit dépilé). Si elle est vraie , (une composante contenant plus de l'arbre.
Le sommet racine doit être traité séparément : il s’agit d’un sommet de coupe si et seulement s’il possède au moins deux enfants dans l’arbre de parcours en profondeur (DFS). Il suffit donc de construire un composant à partir de chaque sous-arbre enfant de la racine (y compris la racine elle-même).
Pseudocode
GetArticulationPoints(i, d) visited[i] := true profondeur[i] := d bas[i] := d nombre d'enfants := 0 isArticulation := fauxpour chaque ni dans adj[i] faire si non visité[ni] alors parent[ni] := i ObtenirPointsArticulation(ni, d + 1) nombre d'enfants := nombre d'enfants + 1 si low[ni] ≥ depth[i] alors isArticulation := vrai bas[i] := Min (bas[i], bas[ni]) sinon si ni ≠ parent[i] alors bas[i] := Min (bas[i], profondeur[ni]) Si (parent[i] ≠ null et isArticulation) ou (parent[i] = null et childCount > 1) alors Afficher i comme point d'articulation
Main GetArticulationPoints(r,0) // r est une racine arbitraire
Notez que les termes enfant et parent désignent les relations dans l'arbre DFS, et non dans le graphe original.
Autres algorithmes
Une alternative simple à l'algorithme précédent utilise les décompositions en chaînes , qui sont des décompositions d'oreilles particulières dépendant des arbres DFS . Les décompositions en chaînes peuvent être calculées en temps linéaire grâce à la règle de parcours suivante . Soit Alors de degré minimal 2 et est le seul cycle de 2-connexité en temps linéaire et peut être étendu pour lister tous les sommets de coupe de d'un graphe connexe est incident à un pont ou La liste des sommets de coupe peut être utilisée pour construire l' arbre de coupe par blocs de ajouts de sommets et , où temps avec processeurs.
Un autre algorithme a été proposé par Harold Gabow, dans son article « Path-based depth-first search for strong and biconnected components » (2000).
Structures apparentées
relation d'équivalence
On peut définir une relation binaire sur les arêtes d'un graphe non orienté quelconque, selon laquelle deux arêtes sont en relation si et seulement si ou si le graphe contient un cycle simple passant par . Chaque arête est en relation avec elle-même, et une arête si et seulement si de la même manière . De façon moins évidente, il s'agit d'une relation transitive : s'il existe un cycle simple contenant les arêtes , et un autre cycle simple contenant les arêtes , alors on peut combiner ces deux cycles pour trouver un cycle simple passant par . Par conséquent, c'est une relation d'équivalence , et elle peut être utilisée pour partitionner les arêtes en classes d'équivalence, des sous-ensembles d'arêtes ayant la propriété que deux arêtes sont en relation si et seulement si elles appartiennent à la même classe d'équivalence . Les sous-graphes formés par les arêtes de chaque classe d'équivalence sont les composantes biconnexes du graphe donné. Ainsi, les composantes biconnexes partitionnent les arêtes du graphe ; cependant, elles peuvent partager des sommets.
Graphique en blocs
Le graphe par blocs d'un graphe , et une arête relie deux sommets si les deux blocs correspondants partagent un sommet. Un graphe si et seulement si tous les blocs de possédant cette propriété sont appelés graphes par blocs .
Arbre coupé en bloc
Un point de coupure , ou sommet de coupure , d'un graphe
