grafo conexo con k vértices

Gráfico que permanece conectado cuando se eliminan k nodos o menos

Un gráfico con conectividad 4.

En teoría de grafos , se dice que un grafo conexo G es k -vértice-conexo (o k -conexo ) 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 el k más grande para el cual el gráfico está k -conexo-vértice.

Definiciones

Un grafo (que no sea un grafo completo ) tiene conectividad k si k es el tamaño del subconjunto más pequeño de vértices tal que el grafo se desconecte si los elimina. ^[1] En los grafos completos , no hay ningún subconjunto cuya eliminación desconecte el grafo. Algunas fuentes modifican la definición de conectividad para manejar este caso, definiéndola como el tamaño del subconjunto más pequeño de vértices cuya eliminación da como resultado un grafo desconectado o un solo vértice. Para esta variación, la conectividad de un grafo completo es . ^[2] ${\displaystyle K_{n}}$ ${\displaystyle n-1}$

Una definición equivalente es que un grafo con al menos dos vértices es k -conexo si, para cada par de sus vértices, es posible encontrar k caminos independientes de los 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 grafo completo K _n . ^[1]

Un grafo 1-conexo se llama conexo ; un grafo 2-conexo se llama biconexo . Un grafo 3-conexo se llama triconexo.

Aplicaciones

Componentes

Cada gráfico se descompone en una unión disjunta de componentes 1-conectados . Los gráficos 1-conectados se descomponen en un árbol de componentes biconectados . Los gráficos 2-conectados se descomponen en un árbol de componentes triconectados .

Combinatoria poliédrica

El esqueleto 1 de cualquier politopo convexo de dimensión k forma un grafo conexo por vértices k ( teorema de Balinski ). ^[3] Como recíproco parcial, el teorema de Steinitz establece que cualquier grafo plano conexo por vértices 3 forma el esqueleto de un poliedro convexo .

Complejidad computacional

La conectividad de vértices de un grafo de entrada G se puede calcular en tiempo polinomial de la siguiente manera ^[4] 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 para es el número de caminos independientes del 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 dichos caminos calculando el flujo máximo en el grafo entre y con capacidad 1 para cada borde, notando que un flujo de en este grafo corresponde, por el teorema de flujo integral , a caminos independientes del borde por pares de a . ${\displaystyle (s,t)}$ ${\displaystyle (s,t)}$ ${\displaystyle s}$ ${\displaystyle t}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle s}$ ${\displaystyle t}$

Propiedades

Sea k≥2 .

• Todo grafo -conexo de orden contiene al menos un ciclo de longitud al menos ${\displaystyle k}$ ${\displaystyle 2k}$ ${\displaystyle 2k}$
• En un gráfico -conexo, todos los vértices en se encuentran en un ciclo común . ^[5] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle G}$

El espacio de ciclos de un gráfico -conexo se genera mediante sus ciclos inducidos no separadores . ^[6] ${\displaystyle 3}$

a-gráfico enlazado

Un grafo con al menos vértices se llama -enlazado si existen caminos disjuntos para cualquier secuencia y de vértices distintos. Todo grafo -enlazado es un grafo -conexo, pero no necesariamente -conexo. ^[7] ${\displaystyle 2k}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle a_{1},\dots ,a_{k}}$ ${\displaystyle b_{1},\dots ,b_{k}}$ ${\displaystyle 2k}$ ${\displaystyle k}$ ${\displaystyle (2k-1)}$ ${\displaystyle 2k}$

Si un gráfico está -conexo y tiene un grado promedio de al menos , entonces está -ligado. ^[8] ${\displaystyle 2k}$ ${\displaystyle 16k}$ ${\displaystyle k}$

Véase también

• gráfico con conexión de k aristas
• Conectividad (teoría de grafos)
• Teorema de Menger
• Cohesión estructural
• Todas las incrustaciones
• Separador de vértices

Notas

1. Schrijver (12 de febrero de 2003), Optimización combinatoria, Springer, ISBN 9783540443896
2. Beineke, Lowell W.; Bagga, Jay S. (2021), Gráficos de líneas y dígrafos de líneas, Developments in Mathematics, vol. 68, Springer Nature, pág. 87, ISBN 9783030813864
3. Balinski, ML (1961), "Sobre la estructura gráfica de poliedros convexos en el espacio n ", Pacific Journal of Mathematics , 11 (2): 431–434, doi : 10.2140/pjm.1961.11.431.
4. El manual de diseño de algoritmos , pág. 506, y Matemáticas discretas computacionales: combinatoria y teoría de grafos con Mathematica , págs. 290-291
5. Diestel (2016), pág. 84
6. Diestel (2012), pág.65.
7. Diestel (2016), pág. 85
8. Diestel (2016), pág. 75

Referencias

• Diestel, Reinhard (2005), Teoría de grafos (3.ª ed.), Berlín, Nueva York: Springer-Verlag, ISBN 978-3-540-26183-4
• Diestel, Reinhard (2012), Teoría de grafos (corregida 4ª ed. electrónica)
• Diestel, Reinhard (2016), Teoría de grafos (5.a ed.), Berlín, Nueva York: Springer-Verlag, ISBN 978-3-662-53621-6