Une composante connectée est un sous-graphe connecté maximal d’un graphe non orienté. Chaque sommet appartient à exactement une composante connectée, de même que chaque arête. Un graphe est connecté si et seulement s’il a exactement une composante connectée.
Les composantes fortes sont les sous-graphes fortement connectés maximaux d’un graphe dirigé.
Une coupe de sommets ou un ensemble séparateur d’un graphe connecté G est un ensemble de sommets dont l’enlèvement rend G déconnecté. La connectivité des sommets κ(G) (où G n’est pas un graphe complet) est la taille d’une coupe de sommets minimale. Un graphe est dit k-vertex-connecté ou k-connecté si sa connectivité des sommets est supérieure ou égale à k.
Plus précisément, tout graphe G (complet ou non) est dit k-vertex-connecté s’il contient au moins k+1 sommets, mais ne contient pas un ensemble de k – 1 sommets dont l’enlèvement déconnecte le graphe ; et κ(G) est défini comme le plus grand k tel que G est k-connecté. En particulier, un graphe complet à n sommets, noté Kn, n’a pas du tout de coupes de sommets, mais κ(Kn) = n – 1.
Une coupe de sommets 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 sommets 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 non adjacentes de sommets u, v.
2-connectivité est aussi appelée biconnectivité et 3-connectivité est aussi appelée triconnectivité. Un graphe G qui est connecté mais pas 2-connecté 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 connexité des arêtes λ(G) est la taille de la plus petite coupure d’arête, et la connexité locale des arêtes λ(u, v) de deux sommets u, v est la taille de la plus petite coupure d’arête déconnectant u de v. Encore une fois, la connexité locale des arêtes est symétrique. Un graphe est dit k-edge-connecté si sa connectivité d’arête est k ou plus.
Un graphe est dit maximalement connecté si sa connectivité est égale à son degré minimum. Un graphe est dit maximalement connecté par les bords si sa connectivité par les bords est égale à son degré minimum.
Super-connectivité et hyper-connectivitéEdit
Un graphe est dit super-connecté ou super-κ si chaque coupe minimale de sommet isole un sommet. Un graphe est dit hyper-connecté ou hyper-κ si la suppression de chaque coupe de sommet minimum crée exactement deux composantes, dont l’une est un sommet isolé. Un graphe est semi-hyper-connecté ou semi-hyper-κ si toute coupe de sommet minimum sépare le graphe en exactement deux composantes.
Plus précisément : un graphe connecté G est dit super-connecté ou super-κ si toutes les coupes de sommet minimum sont constituées des sommets adjacents à un sommet (de degré minimum).Un graphe connecté G est dit super-connecté ou super-λ si toutes les coupes d’arêtes minimales consistent en les arêtes incidentes à un sommet (de degré minimum).
Un cutset X de G est appelé un cutset non-trivial si X ne contient pas le voisinage N(u) de tout sommet u ∉ X. Alors la superconnectivité κ1 de G est:
κ1(G) = min{|X| : X est un cutset non-trivial}.
Une coupe non triviale de bord et la superconnectivité de bord λ1(G) sont définies de manière analogue.
