En teoría de grafos , se dice que un gráfico conectado G está conectado con vértices k (o conectado con k ) si tiene más de k vértices y permanece conectado siempre que se eliminen menos de k vértices.
La conectividad de vértices , o simplemente conectividad , de un gráfico es la k más grande para la cual el gráfico está k conectado por vértices.
Un gráfico (que no sea un gráfico completo ) tiene conectividad k si k es el tamaño del subconjunto más pequeño de vértices, de modo que el gráfico se desconecta si los elimina. [1] Los gráficos completos no se incluyen en esta versión de la definición ya que no se pueden desconectar eliminando vértices. [ cita necesaria ]
Una definición equivalente es que un gráfico con al menos dos vértices está k -conectado si, para cada par de sus vértices, es posible encontrar k caminos independientes de los vértices que conecten estos vértices; ver el teorema de Menger (Diestel 2005, p. 55). Esta definición produce la misma respuesta, n − 1, para la conectividad del gráfico completo K n . [1] Claramente, el gráfico completo con n vértices tiene conectividad n − 1 según esta definición.
Un gráfico 1-conexo se llama conectado ; un grafo biconexo se llama biconexo . Un grafo de 3 conexos se llama triconexo.
Cada gráfico se descompone en un árbol de componentes uniconexos . Los gráficos 1-conexos se descomponen en un árbol de componentes biconexos . Los gráficos biconexos se descomponen en un árbol de componentes triconexos .
El esqueleto unidimensional de cualquier politopo convexo de k dimensiones forma un gráfico conectado con k vértices ( teorema de Balinski ). [2] Como recíproco parcial, el teorema de Steinitz establece que cualquier gráfico plano conectado con 3 vértices forma el esqueleto de un poliedro convexo .
La conectividad de vértices de un gráfico de entrada G se puede calcular en tiempo polinómico de la siguiente manera [3] considere todos los pares posibles de nodos no adyacentes para desconectar, usando el teorema de Menger para justificar que el separador de tamaño mínimo es el número de vértices por pares -caminos independientes entre ellos, codificar la entrada duplicando cada vértice como un borde para reducir a un cálculo del número de caminos independientes de los bordes por pares, y calcular el número máximo de dichos caminos calculando el flujo máximo en el gráfico entre y con capacidad 1 a cada borde, teniendo en cuenta que un flujo de en este gráfico corresponde, según el teorema de flujo integral , a caminos independientes de los bordes por pares desde a .
