Sabemos que el algoritmo de mincut de Karger se puede usar para demostrar (de manera no constructiva) que el número máximo de mincuts posibles que puede tener un gráfico es .
Me preguntaba si podríamos de alguna manera probar esta identidad al dar una prueba biyectiva (más bien inyectiva) del conjunto de mincuts a otro conjunto de cardinalidad . No hay razones específicas, es solo una curiosidad. Intenté hacerlo por mi cuenta, pero hasta ahora no he tenido ningún éxito. No quisiera que nadie desperdiciara el tiempo en esto y, por lo tanto, si la pregunta parece inútil, pediría a los moderadores que tomen las medidas correspondientes.
El mejor -Akash
Respuestas:
El límite(n2) creo que fue originalmente probado por Dinitz, Karzanov y Lomonosov en 1976, en "Una estructura para el sistema de todos los cortes mínimos de un gráfico". Quizás pueda encontrar lo que está buscando en este documento, pero no estoy seguro de si está en línea.
fuente
Informalmente, se puede argumentar que para tener el número máximo de cortes mínimos, todos los nodos en un gráfico deben tener el mismo grado.
Deje que un corte divida un gráfico en dos conjuntos de nodos y modo que . Deje que el número de cortes mínimos en un gráfico se denote como .C ˉ C C ∩ ˉ C = ∅ m c ( G )G C C¯ C∩C¯=∅ mc(G)
Considere un gráfico conectado con vértices en el que cada vértice tiene grado dos. Este debe ser el gráfico del ciclo y el corte mínimo es de dos aristas. Es obvio que cortar cualquiera de los dos bordes dará como resultado un corte y que tal corte es un corte mínimo. Como hay pares de bordes distintos, hay cortes mínimos.n n(n−1)/2 n(n−1)/2
Haga un nuevo gráfico eliminando un borde del gráfico del ciclo. El corte mínimo del nuevo gráfico es un borde y será suficiente cortar cualquier borde: hay tales cortes que se pueden hacer.n−1
Haga un nuevo gráfico agregando un borde al gráfico del ciclo. Ahora dos nodos tienen grado tres y nodos tienen grado dos. El grado tres nodos deben tanto pertenecen a o ambos pertenecen a . Obsérvese que en el caso del gráfico de ciclo, no hay nodos se restringieron a aparecer juntos en o . La implicación es que agregar un borde agrega una restricción, lo que reduce el número de cortes mínimos.n−2 C C¯ C C¯
La promoción de más nodos al grado tres agrega restricciones adicionales hasta el punto donde solo hay un corte mínimo de grado dos.
Lo anterior muestra que el gráfico del ciclo es (al menos) un máximo local de .mc
Considere el conjunto de gráficos en el que cada nodo es de grado tres. Al eliminar un borde se obtiene un gráfico con un solo corte mínimo de dos. Agregar un borde, como arriba, produce dos nodos que aparecen más en el mismo lado del corte.
Esto sugiere que los gráficos en los que cada nodo es de grado son máximos locales de . Observar que el gráfico completo tiene cortes de tamaño sugiere que esta es una función decreciente.k mc mc=n n−1
No he pensado demasiado en si es posible formalizar lo anterior, pero representa un posible enfoque.
Además, creo que el artículo de Bixby que Jelani Nelson menciona en el comentario a su respuesta se titula "El número mínimo de bordes y vértices en un gráfico con conectividad de borde n y M n-enlaces" ( enlace )
fuente