Mostrar código-fonte de 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.<ref name="Schrijver">{{Citation|autor=Schrijver|título=Combinatorial Optimization|publicado=Springer}}</ref> 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''&nbsp;&minus;&nbsp;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, [[Caminho (teoria dos grafos)|caminhos]] conectam estes vértices. Veja o [[Teorema de Menger]] {{Harv|Diestel|2005| p=55}}. Essa definição produz a mesma resposta, ''n''&nbsp;&minus;&nbsp;1, para a conectividade de um completo grafo ''K''<sub>''n''</sub>.<ref name="Schrijver"/>

Um grafo 1-conexo é chamado [[Conectividade (teoria dos grafos)|conexo]]; um grafo 2-conexo é chamado biconexo. Um grafo 3-conexo é chamado de triconexo.

== Aplicações ==

=== Poliedro Combinatório ===

O 1-[[N-esqueleto|Esqueleto]] de qualquer ''k''-dimensional [[poliedro]] convexo forma um grafo ''k''-vértices-conexo (o Teorema de Balinski, {{harvnb|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<ref>''The algorithm design manual'', p 506, and ''Computational discrete mathematics: combinatorics and graph theory with Mathematica'', p. 290-291</ref>: Considere todas as possibilidades de pares <math>(s, t)</math> de nós não adjacentes para desconexo, usando o [[teorema de Menger]] para justificar que o mínimo tamanho separado por <math>(s, t)</math> é 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 <math>s</math> and <math>t</math> com capacidade de 1 para cada aresta, notando que o fluxo de <math>k</math> nesse grafo corresponde, pelo Teorema de Vazão Integral, para <math>k</math> pares de caminhos de aresta-independente de <math>s</math> to <math>t</math>.

==Veja também==
* [[grafo k-aresta-conectado]]
* [[Conectividade (teoria dos grafos)]]
* [[Teorema de Menger]]

==Notes==
{{Reflist}}

==Referências==
*{{citation
 |último= Diestel |primeiro= Reinhard
 |edição= 3rd
 | isbn = 978-3-540-26183-4
 |local= Berlin, New York
 |publicado= Springer-Verlag
 |título= Graph Theory
 | url = http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/
 |ano= 2005}}.

[[Categoria:Famílias de grafos]]