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 . Essa definição produz a mesma resposta, n − 1, para a conectividade de um completo grafo Kn.

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, ). 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 maneiraThe algorithm design manual, p 506, and Computational discrete mathematics: combinatorics and graph theory with Mathematica, p. 290-291: Considere todas as possibilidades de pares de nós não adjacentes para desconexo, usando o teorema de Menger para justificar que o mínimo tamanho separado por é 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 and com capacidade de 1 para cada aresta, notando que o fluxo de nesse grafo corresponde, pelo Teorema de Vazão Integral, para pares de caminhos de aresta-independente de to .

Ver também grafo k-aresta-conectado Conectividade (teoria dos grafos) Teorema de Menger

Notes

Referências .

Categoria:Famílias de grafos