Connectivité (théorie des graphes) - Connectivity (graph theory)

Ce graphique se déconnecte lorsque le nœud le plus à droite dans la zone grise à gauche est supprimé
Ce graphique se déconnecte lorsque le bord en pointillé est supprimé.

En mathématiques et en informatique , la connectivité est l'un des concepts de base de la théorie des graphes : elle demande le nombre minimum d'éléments (nœuds ou arêtes) qui doivent être supprimés pour séparer les nœuds restants en deux ou plusieurs sous-graphes isolés . Elle est étroitement liée à la théorie des problèmes de flux de réseau . La connectivité d'un graphe est une mesure importante de sa résilience en tant que réseau.

Sommets et graphes connectés

Avec le sommet 0, ce graphe est déconnecté. Le reste du graphique est connexe.

Dans un graphe non orienté G , deux sommets u et v sont dits connectés si G contient un chemin de u à v . Sinon, ils sont appelés déconnectés . Si les deux sommets sont en outre reliés par un chemin de longueur 1 , c'est-à-dire par une seule arête, les sommets sont dits adjacents .

Un graphe est dit connexe si chaque paire de sommets du graphe est connexe. Cela signifie qu'il existe un chemin entre chaque paire de sommets. Un graphe non orienté qui n'est pas connecté est appelé déconnecté . Un graphe non orienté G est donc déconnecté s'il existe deux sommets dans G tels qu'aucun chemin dans G n'a ces sommets comme extrémités. Un graphe avec un seul sommet est connecté. Un graphe sans arêtes avec deux sommets ou plus est déconnecté.

Un graphe orienté est appelé faiblement connecté si le remplacement de toutes ses arêtes dirigées par des arêtes non orientées produit un graphe connecté (non orienté). Il est unilatéralement connexe ou unilatéral (appelé aussi semi-connexe ) s'il contient un chemin dirigé de u vers v ou un chemin dirigé de v vers u pour chaque paire de sommets u, v . Il est fortement connexe , ou simplement fort, s'il contient un chemin dirigé de u à v et un chemin dirigé de v à u pour chaque paire de sommets u, v .

Composants et coupes

Une composante connexe est un sous-graphe connexe maximal d'un graphe non orienté. Chaque sommet appartient à exactement un composant connecté, tout comme chaque arête. Un graphe est connexe si et seulement s'il a exactement une composante connexe.

Les composantes fortes sont les sous-graphes maximaux fortement connectés d'un graphe orienté.

Une coupe de sommets ou un ensemble séparateur d'un graphe connexe G est un ensemble de sommets dont la suppression rend G déconnecté. La connectivité de sommet κ ( G ) (où G n'est pas un graphe complet ) est la taille d'une coupe de sommet minimale. Un graphe est appelé k -vertex-connected ou k -connected si sa connectivité de sommets est k ou supérieure.

Plus précisément, tout graphe G (complet ou non) est dit k -connexe aux sommets s'il contient au moins k +1 sommets, mais ne contient pas un ensemble de k − 1 sommets dont la suppression déconnecte le graphe ; et κ ( G ) est défini comme le plus grand k tel que G soit k- connexe. En particulier, un graphe complet à n sommets, noté K n , n'a aucune coupe de sommet, mais κ ( K n ) = n − 1 .

Un sommet coupé pour deux sommets u et v est un ensemble de sommets dont la suppression du graphe déconnecte u et v . La connectivité locale κ ( u , v ) est la taille d' une plus petite coupe de sommet séparant u et v . La connectivité locale est symétrique pour les graphes non orientés ; c'est-à-dire κ ( u , v ) = κ ( v , u ) . De plus, sauf pour les graphes complets, κ ( G ) est égal au minimum de κ ( u , v ) sur toutes les paires de sommets non adjacentes u, v .

La 2- connectivité est aussi appelée biconnectivité et la 3- connectivité est aussi appelée triconnectivité . Un graphe G qui est connexe mais pas 2- connexe est parfois appelé séparable .

Des concepts analogues peuvent être définis pour les arêtes. Dans le cas simple où couper une seule arête spécifique déconnecterait le graphe, cette arête est appelée un pont . Plus généralement, une coupe d'arêtes de G est un ensemble d'arêtes dont la suppression rend le graphe déconnecté. La connectivité d'arête λ ( G ) est la taille d'une plus petite coupure d'arête, et la connectivité d'arête locale λ ( u , v ) de deux sommets u, v est la taille d'une plus petite coupure d'arête déconnectant u de v . Encore une fois, la connectivité périphérique locale est symétrique. Un graphe est appelé k -edge-connected si sa connectivité de bord est k ou supérieure.

Un graphe est dit connecté au maximum si sa connectivité est égale à son degré minimum. Un graphe est dit au maximum connecté aux arêtes si sa connectivité aux arêtes est égale à son degré minimum.

Super et hyper-connectivité

Un graphe est dit super-connexe ou super-κ si chaque coupe de sommet minimum isole un sommet. Un graphe est dit hyper-connecté ou hyper-κ si la suppression de chaque coupe de sommet minimum crée exactement deux composants, dont l'un est un sommet isolé. Un graphe est semi-hyper-connecté ou semi-hyper-κ si une coupe de sommet minimum sépare le graphe en exactement deux composants.

Plus précisément : un graphe connexe G est dit super-connexe ou super-κ si toutes les coupes de sommets minimales sont constituées des sommets adjacents à un sommet (de degré minimum). Un graphe G connexe est dit super-arête-connexe ou super-λ si toutes les coupes d'arêtes minimales sont constituées des arêtes incidentes sur un sommet (de degré minimum).

Un cutset X de G est appelé cutset non trivial si X ne contient pas le voisinage N(u) d'un sommet u X . Alors la superconnectivité κ1 de G est :

1(G) = min{|X| : X est un cutset non trivial}.

Une coupure de bord non triviale et la superconnectivité de bord λ1(G) sont définies de manière analogue.

théorème de Menger

L'un des faits les plus importants sur la connectivité dans les graphes est le théorème de Menger , qui caractérise la connectivité et la connectivité des arêtes d'un graphe en termes de nombre de chemins indépendants entre les sommets.

Si u et v sont des sommets d'un graphe G , alors une collection de chemins entre u et v est dite indépendante si deux d'entre eux ne partagent pas un sommet (autre que u et v eux-mêmes). De même, la collection est indépendante des bords si deux chemins qu'elle contient ne partagent pas de bord. Le nombre de chemins mutuellement indépendants entre u et v s'écrit κ′ ( u , v ) , et le nombre de chemins mutuellement indépendants entre u et v s'écrit λ′ ( u , v ) .

Le théorème de Menger affirme que pour sommets distincts u , v , λ ( u , v ) est égal à λ ' ( u , v ) , et si u est également non adjacente à v puis κ ( u , v ) est égal à κ' ( u , v ) . Ce fait est en fait un cas particulier du théorème max-flow min-cut .

Aspects informatiques

Le problème consistant à déterminer si deux sommets d'un graphe sont connectés peut être résolu efficacement à l'aide d'un algorithme de recherche , tel que la recherche en largeur d'abord . Plus généralement, il est facile de déterminer par calcul si un graphe est connecté (par exemple, en utilisant une structure de données à ensemble disjoint ), ou de compter le nombre de composants connectés. Un algorithme simple pourrait être écrit en pseudo-code comme suit :

  1. Commencer à n'importe quel nœud arbitraire du graphe, G
  2. Procédez à partir de ce nœud en utilisant la recherche en profondeur d'abord ou en largeur d'abord, en comptant tous les nœuds atteints.
  3. Une fois le graphe entièrement parcouru, si le nombre de nœuds comptés est égal au nombre de nœuds de G , le graphe est connecté ; sinon il est déconnecté.

D'après le théorème de Menger, pour deux sommets u et v quelconques dans un graphe connexe G , les nombres κ ( u , v ) et λ ( u , v ) peuvent être déterminés efficacement en utilisant l' algorithme max-flow min-cut . La connectivité et la connectivité de bord de G peuvent alors être calculées comme les valeurs minimales de κ ( u , v ) et λ ( u , v ) , respectivement.

Dans la théorie de la complexité computationnelle, SL est la classe de problèmes log-space réductible au problème de déterminer si deux sommets d'un graphe sont connectés, ce qui a été prouvé être égal à L par Omer Reingold en 2004. Par conséquent, la connectivité de graphe non dirigée peut être résolu dans l' espace O(log n ) .

Le problème du calcul de la probabilité qu'un graphe aléatoire de Bernoulli soit connecté est appelé fiabilité du réseau et le problème du calcul de la connexion de deux sommets donnés est le problème de fiabilité ST. Les deux sont #P -difficiles.

Nombre de graphes connectés

Le nombre de graphes étiquetés distincts connectés avec n nœuds est tabulé dans l' Encyclopédie en ligne des séquences entières sous la forme A001187 . Les premiers termes non triviaux sont

m graphiques
2 1
3 4
4 38
5 728
6 26704
7 1866256
8 251548592

Exemples

  • Les connectivités de sommet et d'arête d'un graphe déconnecté sont toutes deux égales à 0 .
  • 1 -connexité est équivalente à la connexité pour les graphes d'au moins 2 sommets.
  • Le graphe complet sur n sommets a une connectivité d'arête égale à n − 1 . Tout autre graphe simple sur n sommets a une connectivité de bord strictement plus petite.
  • Dans un arbre , la connectivité de bord locale entre chaque paire de sommets est de 1 .

Limites de connectivité

  • La connectivité des sommets d'un graphe est inférieure ou égale à sa connectivité des bords. C'est-à-dire κ ( G ) ≤ λ ( G ) . Les deux sont inférieurs ou égaux au degré minimum du graphe, car la suppression de tous les voisins d'un sommet de degré minimum déconnectera ce sommet du reste du graphe.
  • Pour un graphe vertex-transitif de degré d , on a : 2( d + 1)/3 κ ( G ) ≤ λ ( G ) = d .
  • Pour un graphe vertex-transitif de degré d 4 , ou pour tout graphe de Cayley minimal (non orienté) de degré d , ou pour tout graphe symétrique de degré d , les deux types de connectivité sont égaux : κ ( G ) = λ ( G ) = d .

Autres propriétés

Voir également

Les références