Número de mincuts de um gráfico sem usar o algoritmo de Karger

Sabemos que o algoritmo de mincut de Karger pode ser usado para provar (de maneira não construtiva) que o número máximo de possíveis mincuts que um gráfico pode ter é $n \choose 2$ .

Fiquei imaginando se de alguma forma poderíamos provar essa identidade, fornecendo uma prova bijetiva (bastante injetiva) do conjunto de mincuts para outro conjunto de cardinalidade $n \choose 2$ . Sem razões específicas, é apenas uma curiosidade. Eu tentei fazer isso sozinho, mas até agora não tive nenhum sucesso. Eu não gostaria que alguém desperdiçasse tempo com isso e, se a pergunta parecer inútil, solicitaria aos moderadores que tomem medidas em conformidade.

Best -Akash

O $\binom{n}{2}$ obrigado Eu acho que foi originalmente comprovada por Dinitz, Karzanov e Lomonosov em 1976, em "A estrutura para o sistema de todos os cortes mínimos de um gráfico". Talvez você possa encontrar o que está procurando neste artigo, mas não tenho certeza se está online.

Informalmente, pode-se argumentar que, para ter o número máximo de min-recortes, todos os nós em um gráfico devem ter o mesmo grau.

Deixe um corte dividir um gráfico em dois conjuntos de nós e modo que . Seja o número de min-recortes em um gráfico indicado como .$G$$C$$\bar C$$C \cap \bar C=\emptyset$$mc(G)$

Considere um gráfico conectado com vértices em que cada vértice possui o grau dois. Esse deve ser o gráfico do ciclo e o corte mínimo é de duas arestas. É óbvio que cortar duas arestas resultará em um corte e que esse corte será um corte mínimo. Como existem pares distintos de arestas, há cortes mínimos.$n$$n(n-1)/2$$n(n-1)/2$

Faça um novo gráfico removendo uma aresta do gráfico de ciclo. O corte mínimo do novo gráfico é uma aresta e cortar qualquer aresta será suficiente: existem desses cortes que podem ser feitos.$n-1$

Faça um novo gráfico adicionando uma aresta ao gráfico de ciclo. Agora, dois nós têm grau três e nós têm grau dois. O grau três nós deve ambos pertencem ao ou ambos pertencem a . Note-se que no caso do gráfico de ciclo, não há nós foram restritos a aparecem juntos em ou . A implicação é que a adição de uma aresta adiciona uma restrição, o que reduz o número de cortes mínimos.$n-2$$C$$\bar C$$C$$\bar C$

A promoção de mais nós para o grau três adiciona restrições adicionais até o ponto em que há apenas um corte mínimo do grau dois.

O exposto acima mostra que o gráfico de ciclo é (pelo menos) um máximo local de .$mc$

Considere o conjunto de gráficos em que cada nó possui o grau três. A remoção de uma aresta produz um gráfico com um único min-cut de dois. Adicionar uma aresta, como acima, produz dois nós que mais aparecem no mesmo lado do corte.

Isso sugere que os gráficos nos quais cada nó é de grau são máximos locais de . Observar que o gráfico completo possui cortes de tamanho sugere que essa é uma função em declínio.$k$$mc$$mc=n$$n-1$

Não pensei muito em se é possível formalizar o que foi dito acima, mas isso representa uma abordagem possível.

Além disso, acho que o artigo de Bixby que Jelani Nelson menciona no comentário de sua resposta é intitulado "O número mínimo de arestas e vértices em um gráfico com conectividade de borda nem M n-ligações" ( link )