En teoría de grafos y análisis de redes sociales, la conectividad de un grafo o red social refiere al mínimo número de elementos (vértices "Vértice (teoría de grafos)") o aristas "Arista (teoría de grafos)")) que se necesitan para, al ser removidos, dividir al grafo o red en componentes "Componente (teoría de grafos)") aisladas. A estos vértices o aristas críticos se les denomina vértices de corte o aristas de corte, respectivamente.[1]​.

La conectividad de un grafo es una medida de su cohesión o robustez. Intuitivamente, un grafo es cohesivo si posee muchas aristas, si los vértices tienen grados "Grado (teoría de grafos)") relativamente altos, si tiene muchos caminos "Camino (teoría de grafos)") cortos entre pares de vértices, o si tiene distancias "Distancia (teoría de grafos)") pequeñas (y por tanto un diámetro "Distancia (teoría de grafos)") pequeño) en relación con su tamaño. Por el contrario, un grafo más «vulnerable» corre el riesgo de volverse inconexo si se le retiran unas pocas aristas o vértices.[1]​.

Contenido

La conectividad de vértices, nodos o puntos de un grafo , denotada , es el número mínimo para el que el grafo tiene un corte de nodos-.[2]​ Así, si el grafo es inconexo, entonces , porque no hay que quitar ningún vértice; si el grafo tiene un punto de corte, entonces , porque basta quitar un único vértice para que el grafo se vuelva inconexo, y así sucesivamente. Además, para cualquier valor , el grafo se dice que es -conexo o -conectado por nodos. Note que un grafo completo no tiene puntos de corte, y que la única forma de desconectarlo es quitando vértices, con lo que se obtiene el grafo trivial. Por lo tanto, κ.[1]​.

Análogamente, la conectividad de aristas o conectividad lineal, , es el número mínimo para el que el grafo tiene un corte de aristas-.[2]​ Además, para cualquier valor , el grafo se dice que es -linealmente conexo.[1]​.

Dado un grafo dirigido, un par de vértices está:[1]​.