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–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 é identico aos 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 editar
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 conjunto 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.
Ver também editar
Referências editar
- 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. 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.