Corte (teoria gráfico) - Cut (graph theory)

Em teoria gráfico , um corte é uma partição dos vértices de um grafo em dois subconjuntos disjuntos . Qualquer corte determina um corte de conjunto , o conjunto de arestas que têm um ponto de extremidade em cada subconjunto da partição. Estas arestas são ditos atravessar o corte. Em um grafo conexo , cada corte-set determina um corte único, e em alguns casos, os cortes são identificados com seus cut-conjuntos em vez de com as suas partições de vértice.

Em uma rede de fluxo , um corte de s-t é um corte que requer a fonte e o dissipador ser em diferentes subconjuntos, e o seu limite definido apenas consiste de bordas que a partir do lado da fonte para o lado do dissipador. A capacidade de um corte de s-t é definido como a soma da capacidade de cada bordo na corte-conjunto .

Definição

Um corte é uma partição de de um gráfico em dois subconjuntos S e T . O cut-definida de um corte é o conjunto de arestas que têm um ponto de extremidade em S e a outra extremidade em T . Se s e t são especificados vértices do gráfico G , em seguida, um s - t corte é um corte em que s pertence ao conjunto S e T pertence ao conjunto do T . ${\ Displaystyle C = (S, T)}$${\ V} displaystyle$${\ Displaystyle G = (V, E)}$${\ Displaystyle C = (S, T)}$${\ Displaystyle \ {(u, v) \ em E \ meados u \ em S, v \ em T \}}$

Em um gráfico undirected não ponderada, o tamanho ou o peso de um corte é o número de arestas de corte que cruzam a. Em um gráfico ponderado , o valor ou o peso é definido pela soma dos pesos das arestas que atravessam o corte.

A ligação é um cut-set que não tem qualquer outra cut-set como um subconjunto adequado.

corte mínimo

Um corte mínimo.

Um corte é mínimo se o tamanho ou o peso do corte não é maior do que o tamanho de qualquer outro corte. A figura da direita mostra um corte mínimo: o tamanho de este corte é 2, e não há corte de tamanho 1, porque o gráfico é sem ponte .

O max-min de fluxo de corte teorema prova que o máximo de fluxo de rede e a soma dos pesos de corte de ponta de qualquer corte mínima que separa a fonte e o dissipador são iguais. Há -de tempo polinomial métodos para resolver o problema de corte min, nomeadamente o algoritmo de Edmonds-Karp .

corte máxima

Um corte máximo.

Um corte é máximo , se o tamanho do corte não é menor do que o tamanho de qualquer outro corte. A ilustração à direita mostra um corte máxima: o tamanho do corte é igual a 5, e não há corte de tamanho 6, ou | E | (o número de arestas), porque o gráfico não é bipartido (há um ciclo estranho ).

Em geral, encontrar um corte máximo é computacionalmente difícil. O problema de corte máximo é um dos 21 problemas NP-completos de Karp . O problema de corte máximo também é APX-duro , o que significa que não existe qualquer regime de aproximação de tempo polinomial por isso a menos que P = NP. No entanto, ele pode ser aproximado dentro de uma constante relação de aproximação utilizando programação semidefinida .

Note-se que min-cut e max-cut são não duais problemas na programação linear sentido, mesmo que se obtém de um problema para outro, alterando min a max na função objetivo . O problema de fluxo máximo é o dual do problema de corte min.

Sparsest corte

O problema corte sparsest é para bipartição os vértices, de modo a minimizar a proporção do número de arestas de todo o corte dividida pelo número de vértices na metade inferior da partição. Esta função objectivo favorece soluções que são ambos esparsos (poucas arestas que atravessam o corte) e equilibrada (perto de uma bissecção). O problema é conhecido por ser NP-difícil, eo algoritmo de aproximação mais conhecido é uma aproximação devido a Arora, Rao & Vazirani (2009) .${\ Displaystyle O ({\ sqrt {\ log n}})}$

espaço Cut

A família de todos os conjuntos de corte de um gráfico undirected é conhecida como o espaço de corte do gráfico. Ele forma um espaço vectorial sobre o elemento de duas campo finito de aritmética de módulo dois, com a diferença simétrica de dois conjuntos de corte como o vector de operação de adição e é o complemento ortogonal do espaço ciclo . Se as bordas do gráfico são dadas pesos positivos, o peso mínimo de base do espaço de corte pode ser descrito por uma árvore no mesmo vértice definido como o gráfico, chamado de árvore Gomory-Hu . Cada extremidade desta árvore está associada com uma ligação no gráfico original, e o corte mínima entre dois nós de s e t é o título mínimo de peso entre os associados com o caminho de s a t na árvore.

Veja também

• Conectividade (teoria gráfico)
• cortes Gráfico em visão por computador
• Split (teoria dos grafos)
• separador de Vertex

Referências