En teoría de grafos , se dice que un grafo conectado G está k -conectado al vértice (o k -conectado ) si tiene más de k vértices y permanece conectado siempre que se eliminan menos de k vértices.
La conectividad de vértice , o simplemente la conectividad , de un gráfico es el k más grande para el cual el gráfico está k conectado al vértice.
Definiciones
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. El gráfico completo con n vértices tiene conectividad n - 1, como implica la primera definición.
Una definición equivalente es que un grafo con al menos dos vértices está k -conectado si, para cada par de sus vértices, es posible encontrar k caminos independientes de vértices que conecten estos vértices; véase 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]
Un gráfico conectado con 1 se llama conectado ; un gráfico de 2 conexiones se llama biconectado . Un gráfico de 3 conexiones se llama triconectado.
Aplicaciones
Combinatoria poliédrica
El esqueleto 1 de cualquier politopo convexo k -dimensional forma un grafo conectado al k -vértice ( teorema de Balinski , Balinski 1961 ). Como recíproco parcial, el teorema de Steinitz establece que cualquier gráfico plano conectado de 3 vértices forma el esqueleto de un poliedro convexo .
Complejidad computacional
La conectividad de vértice de un gráfico de entrada G se puede calcular en tiempo polinomial de la siguiente manera [2] considere todos los pares posiblesde nodos no adyacentes para desconectar, utilizando el teorema de Menger para justificar que el separador de tamaño mínimo paraes el número de caminos independientes de vértice por pares entre ellos, codifique la entrada duplicando cada vértice como un borde para reducir a un cálculo del número de caminos independientes del borde por pares, y calcule el número máximo de tales caminos calculando el flujo máximo en el gráfico entre y con capacidad 1 a cada borde, notando que un flujo de en este gráfico corresponde, por el teorema de flujo integral , a caminos independientes de los bordes por pares desde a .
Ver también
Notas
- ^ a b Schrijver (12 de febrero de 2003), Optimización combinatoria , Springer, ISBN 9783540443896
- ^ El manual de diseño de algoritmos , p 506, y Matemáticas discretas computacionales: combinatoria y teoría de grafos con Mathematica , p. 290-291
Referencias
- Balinski, ML (1961), "Sobre la estructura gráfica de poliedros convexos en n- espacio", Pacific Journal of Mathematics , 11 (2): 431–434, doi : 10.2140 / pjm.1961.11.431.
- Diestel, Reinhard (2005), Graph Theory (3.a ed.), Berlín, Nueva York: Springer-Verlag, ISBN 978-3-540-26183-4.