Grafo k-vértice-conexo

Na teoria dos grafos, um grafo G é dito k-vértice-conexo (ou k-conexo) se tem mais de k vértices e permanece conexo sempre que são removidos k-1 vértices.

O vértice-conexo ou conexão, de um grafo é o maior k para que o grafo continua k-vértice-conexo.

Definições

Um grafo (que não seja um grafo completo) tem conectividade k se k é o tamanho do menor subconjunto de vértices em que o grafo se torna desconexo se forem removidos dele. Grafos completos não estão inclusos nesta versão da definição desde que eles não podem ser desconexos deletando vértices. Um grafo completo com n vértices tem conectividade n − 1, como diz a primeira definição.

Uma definição equivalente é que um grafo com no mínimo 2 vértices é k-conexo se, para cada par de vértices, é possível achar k caminhos de vértices-disjuntos, caminhos conectam estes vértices. Veja o Teorema de Menger (Diestel 2005, p. 55). Essa definição produz a mesma resposta, n − 1, para a conectividade de um completo grafo K_n.

Um grafo 1-conexo é chamado conexo; um grafo 2-conexo é chamado biconexo. Um grafo 3-conexo é chamado de triconexo.

Aplicações

Poliedro Combinatório

O 1-Esqueleto de qualquer k-dimensional poliedro convexo forma um grafo k-vértices-conexo (o Teorema de Balinski, Balinski 1961). Como uma resposta parcial, o teorema de Steinitz diz que um grafo planar de 3-vértices-conexo forma o esqueleto de um poliedro convexo.

Complexidade Computacional

A vértice-conexão de uma entrada de grafo G pode ser computada em tempo polinomial da seguinte maneira: Considere todas as possibilidades de pares $(s,t)$ de nós não adjacentes para desconexo, usando o teorema de Menger para justificar que o mínimo tamanho separado por $(s,t)$ é o número de pares vértice-independente caminhos entre eles, codificar a entrada dobrando cada vértice como aresta para reduzir a um cálculo de números pares de caminhos de arestas-independentes, e compute o número máximo de caminhos que computam o Problema da vazão máxima de grafos entre $s$ and $t$ com capacidade de 1 para cada aresta, notando que o fluxo de $k$ nesse grafo corresponde, pelo Teorema de Vazão Integral, para $k$ pares de caminhos de aresta-independente de $s$ to $t$.

Veja também

• grafo k-aresta-conectado
• Conectividade (teoria dos grafos)
• Teorema de Menger

Referências

• Diestel, Reinhard (2005), Graph Theory, ISBN 978-3-540-26183-4 3rd ed. , Berlin, New York: Springer-Verlag .