Teorema de Menger

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

Na disciplina Matemática de Teoria dos grafos e áreas relacionadas, o teorema de Menger é um resultado básico sobre conectividade em um grafos finitos não direcionados. Foi provado para 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 minimo de arestas que precisam ser removidas para desconectar x e y é igual ao número máximo de caminhos aresta-indepentes emparelhados de x para y.
Extendendo para subgrafos: um subgrafo maximal desconectado por não menos que k-arestas de corte é identico 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-indepentes emparelhados de x para y.
Extendendo 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 | editar código-fonte]

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 familia P de A-B-caminhos disjuntos e um conjunto separador de exatamente um vértice para cada caminho em P.

Veja também[editar | editar código-fonte]

Referências[editar | editar código-fonte]

Links externos[editar | editar código-fonte]