Teorema de Menger

Em teoria dos grafos e áreas relacionadas da matemática, o teorema de Menger é um resultado básico sobre conectividade em grafos finitos não direcionados. Foi provada a K-aresta-conectividade e K-vértice-conectividade por Karl Menger em 1927. A versão para aresta-conectividade do teorema de Menger foi generalizada mais tarde pelo teorema do fluxo máximo e corte mínimo.

A versão do teorema de Menger para aresta-conectividade funciona da seguinte forma:

G é um grafo finito não direcionado e x e y são dois vértices distintos. Então o teorema afirma que o tamanho mínimo de arestas que precisam ser removidas para desconectar x e y é igual ao número máximo de caminhos aresta-independentes emparelhados de x para y.
Estendendo para subgrafos: um subgrafo maximal desconectado por não menos que k-arestas de corte é idêntico aos subgrafo maximal com um número mínimo de k caminhos aresta-independente entre qualquer par de nós x, y no subgrafo.

A versão do teorema de Menger para vértice-conectividade funciona da seguinte forma:

G é um grafo finito não direcionado e x e y são dois vértices não adjacentes. Então o teorema afirma que o número mínimo de vértices que precisam ser removidos para desconectar x e y é igual ao número máximo de caminhos vértice-independentes emparelhados de x para y.
Estendendo para subgrafos: um subgrafo maximal desconectado por não menos que k-vértices de corte é idêntico ao subgrafo maximal com um número mínimo de k caminhos vértice-independente entre qualquer par de nós x, y no subgrafo.

Grafos infinitos

O teorema de Menger é valido para grafos infinitos, e nesse contexto se aplica ao corte mínimo entre quaisquer dois elementos que ou são vértices, ou extremidades do grafo (Halin 1974). O resultado a seguir é um resultado de Ron Aharoni e Eli Berger e foi originalmente uma conjectura proposta por Paul Erdős, e antes de ser provada ficou conhecida como A conjectura Erdős–Menger. É equivalente ao teorema de Menger quando o grafo é finito.

A e B são conjuntos de vértices em um (possivelmente infinito) digrafo G. Então existe uma família P de A-B-caminhos disjuntos e um conjunto separador de exatamente um vértice para cada caminho em P.

Referências

  • Menger, Karl (1927). «Zur allgemeinen Kurventheorie». Fund. Math. 10: 96–115 
  • Aharoni, Ron and Berger, Eli (2009). «Menger's Theorem for infinite graphs». Inventiones Mathematicae (em inglês). 176: 1–62. doi:10.1007/s00222-008-0157-3 
  • Halin, R. (1974), «A note on Menger's theorem for infinite locally finite graphs», Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg, 40: 111–114, MR 0335355 

Ligações externas

Este artigo é emitido por Wikipédia. O texto é licenciado sob Creative Commons Attribution-Share Alike 4.0. Termos adicionais podem ser aplicados aos arquivos de mídia.