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 . 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.
Ligações externas
Categoria:Conectividade de grafos
de:Schnitt (Graphentheorie)#Disjunkte Wege und Schnitte