gráfico k-vértice-conectado
En la teoría de grafos , se dice que un grafo conexo G es conexo con k vértices (o conexo 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 la conectividad , de un gráfico es el k más grande para el cual el gráfico está conectado a los 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 grafos completos no se incluyen en esta versión de la definición ya que no se pueden desconectar eliminando vértices. El grafo completo con n vértices tiene conectividad n − 1, como implica la primera definición.
Una definición equivalente es que un gráfico con al menos dos vértices es k -conexo si, para cada par de sus vértices, es posible encontrar k caminos independientes de vértices que conectan 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 conexo a 1 se denomina conexo ; un grafo biconexo se llama biconexo . Un grafo triconectado se llama triconectado.
El esqueleto unidimensional de cualquier politopo convexo de dimensión k forma un grafo conectado por vértices k ( teorema de Balinski , Balinski 1961 ). Como inversa parcial, el teorema de Steinitz establece que cualquier gráfico plano conectado por 3 vértices forma el esqueleto de un poliedro convexo .
