grafo conexo con k vértices

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.

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]$Estilo de visualización K_{n}$${\estilo de visualización 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.

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 .

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 .

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 .${\estilo de visualización (s,t)}$${\estilo de visualización (s,t)}$${\estilo de visualización s}$${\estilo de visualización t}$${\estilo de visualización k}$${\estilo de visualización k}$${\estilo de visualización s}$${\estilo de visualización t}$

Sea k≥2 .

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

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

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]${\estilo de visualización 2k}$${\estilo de visualización k}$${\estilo de visualización k}$${\displaystyle a_{1},\puntos ,a_{k}}$${\displaystyle b_{1},\puntos ,b_{k}}$${\estilo de visualización 2k}$${\estilo de visualización k}$${\estilo de visualización (2k-1)}$${\estilo de visualización 2k}$

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

• 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

• 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