Corte (teoría de grafos)

Partición de los nodos de un gráfico en dos subconjuntos disjuntos

En teoría de grafos , un corte es una partición de los vértices de un grafo en dos subconjuntos disjuntos . ^[1] Cualquier corte determina un conjunto de cortes , el conjunto de aristas que tienen un punto final en cada subconjunto de la partición. Se dice que estas aristas cruzan el corte. En un grafo conexo , cada conjunto de cortes determina un corte único y, en algunos casos, los cortes se identifican con sus conjuntos de cortes en lugar de con sus particiones de vértices.

En una red de flujo , un corte s–t es un corte que requiere que la fuente y el sumidero estén en subconjuntos diferentes, y su conjunto de cortes solo consta de aristas que van del lado de la fuente al lado del sumidero. La capacidad de un corte s–t se define como la suma de la capacidad de cada arista en el conjunto de cortes .

Definición

Un corte $C = (S, T)$ es una partición de $V$ de un grafo $G = (V, E)$ en dos subconjuntos $S$ y $T$ . El conjunto de corte de un corte $C = (S, T)$ es el conjunto ${(u, v) \in E | u \in S, v \in T}$ de aristas que tienen un extremo en $S$ y el otro extremo en $T$ . Si $s$ y $t$ son vértices especificados del grafo $G$ , entonces un corte $s$ – $t$ es un corte en el que $s$ pertenece al conjunto $S$ y $t$ pertenece al conjunto $T$ .

En un gráfico no ponderado y no dirigido, el tamaño o peso de un corte es la cantidad de aristas que cruzan el corte. En un gráfico ponderado , el valor o peso se define por la suma de los pesos de las aristas que cruzan el corte.

Un enlace es un conjunto de cortes que no tiene ningún otro conjunto de cortes como subconjunto propio.

Corte mínimo

Un corte es mínimo si el tamaño o el peso del corte no es mayor que el tamaño de cualquier otro corte. La ilustración de la derecha muestra un corte mínimo: el tamaño de este corte es 2 y no hay ningún corte de tamaño 1 porque el gráfico no tiene puente .

El teorema de corte mínimo y flujo máximo demuestra que el flujo máximo de la red y la suma de los pesos de los bordes de corte de cualquier corte mínimo que separa la fuente y el sumidero son iguales. Existen métodos de tiempo polinomial para resolver el problema del corte mínimo, en particular el algoritmo de Edmonds-Karp . ^[2]

Corte máximo

Un corte es máximo si el tamaño del corte no es menor que el tamaño de cualquier otro corte. La ilustración de la derecha muestra un corte máximo: el tamaño del corte es igual a 5, y no hay ningún corte de tamaño 6, o | E | (el número de aristas), porque el gráfico no es bipartito (hay un ciclo impar ).

En general, encontrar un corte máximo es computacionalmente difícil. ^[3] El problema del corte máximo es uno de los 21 problemas NP-completos de Karp . ^[4] El problema del corte máximo también es APX-duro , lo que significa que no hay un esquema de aproximación de tiempo polinomial para él a menos que P = NP . ^[5] Sin embargo, se puede aproximar dentro de una relación de aproximación constante utilizando programación semidefinida . ^[6]

Obsérvese que el corte mínimo y el corte máximo no son problemas duales en el sentido de la programación lineal , aunque se pasa de un problema a otro cambiando el mínimo por el máximo en la función objetivo . El problema del flujo máximo es el dual del problema del corte mínimo . ^[7]

Corte más escaso

El problema del corte más disperso consiste en biparticionar los vértices de modo de minimizar la relación entre el número de aristas que atraviesan el corte y el número de vértices en la mitad más pequeña de la partición. Esta función objetivo favorece las soluciones que son dispersas (pocas aristas que cruzan el corte) y equilibradas (cercanas a una bisección). Se sabe que el problema es NP-hard, y el algoritmo de aproximación más conocido es una aproximación debida a Arora, Rao y Vazirani (2009). ^[8] $O({\sqrt {\log n}})$

Espacio de corte

La familia de todos los conjuntos de corte de un grafo no dirigido se conoce como el espacio de corte del grafo. Forma un espacio vectorial sobre el cuerpo finito de dos elementos de la aritmética módulo dos, con la diferencia simétrica de dos conjuntos de corte como la operación de adición vectorial, y es el complemento ortogonal del espacio de ciclo . ^[9]^[10] Si a los bordes del grafo se les dan pesos positivos, la base de peso mínimo del espacio de corte se puede describir mediante un árbol en el mismo conjunto de vértices que el grafo, llamado árbol de Gomory-Hu . ^[11] Cada borde de este árbol está asociado con un enlace en el grafo original, y el corte mínimo entre dos nodos s y t es el enlace de peso mínimo entre los asociados con el camino de s a t en el árbol.

Véase también

Referencias

^ "Documentación de NetworkX 2.6.2". networkx.algorithms.cuts.cut_size . Archivado desde el original el 2021-11-18 . Consultado el 2021-12-10 . Un corte es una partición de los nodos de un gráfico en dos conjuntos. El tamaño del corte es la suma de los pesos de los bordes "entre" los dos conjuntos de nodos.
^ Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), Introducción a los algoritmos (2.ª ed.), MIT Press y McGraw-Hill, pág. 563, 655, 1043, ISBN 0-262-03293-7.
^ Garey, Michael R.; Johnson , David S. (1979), Computadoras e intratabilidad: una guía para la teoría de la NP-completitud , WH Freeman, A2.2: ND16, pág. 210, ISBN 0-7167-1045-5.
^ Karp, RM (1972), "Reducibilidad entre problemas combinatorios", en Miller, RE; Thacher, JW (eds.), Complejidad de la computación informática , Nueva York: Plenum Press, págs. 85-103.
^ Khot, S. ; Kindler, G.; Mossel, E.; O'Donnell, R. (2004), "¿Resultados de inaproximabilidad óptima para MAX-CUT y otros CSP de dos variables?" (PDF) , Actas del 45.º Simposio IEEE sobre fundamentos de la informática , págs. 146-154, archivado (PDF) del original el 15 de julio de 2019 , consultado el 29 de agosto de 2019.
^ Goemans, MX ; Williamson, DP (1995), "Algoritmos de aproximación mejorados para problemas de corte máximo y satisfacibilidad utilizando programación semidefinida", Journal of the ACM , 42 (6): 1115–1145, doi : 10.1145/227683.227684 .
^ Vazirani, Vijay V. (2004), Algoritmos de aproximación , Springer, págs. 97–98, ISBN 3-540-65367-8.
^ Arora, Sanjeev ; Rao, Satish; Vazirani, Umesh (2009), "Flujos de expansión, incrustaciones geométricas y particionamiento de grafos", J. ACM , 56 (2), ACM: 1–37, doi :10.1145/1502793.1502794, S2CID 263871111 .
^ Gross, Jonathan L.; Yellen, Jay (2005), "4.6 Gráficos y espacios vectoriales", Teoría de grafos y sus aplicaciones (2.ª ed.), CRC Press, págs. 197-207, ISBN 9781584885054.
^ Diestel, Reinhard (2012), "1.9 Algo de álgebra lineal", Teoría de grafos, Textos de posgrado en matemáticas, vol. 173, Springer, págs. 23-28.
^ Korte, BH ; Vygen, Jens (2008), "8.6 Árboles de Gomory–Hu", Optimización combinatoria: teoría y algoritmos , Algorithms and Combinatorics, vol. 21, Springer, págs. 180–186, ISBN 978-3-540-71844-4.

[networkx.algorithms.cuts.cut_size-1] "Documentación de NetworkX 2.6.2". networkx.algorithms.cuts.cut_size . Archivado desde el original el 2021-11-18 . Consultado el 2021-12-10 . Un corte es una partición de los nodos de un gráfico en dos conjuntos. El tamaño del corte es la suma de los pesos de los bordes "entre" los dos conjuntos de nodos.

[2] Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2001), Introducción a los algoritmos (2.ª ed.), MIT Press y McGraw-Hill, pág. 563, 655, 1043, ISBN 0-262-03293-7.

[3] Garey, Michael R.; Johnson , David S. (1979), Computadoras e intratabilidad: una guía para la teoría de la NP-completitud , WH Freeman, A2.2: ND16, pág. 210, ISBN 0-7167-1045-5.

[4] Karp, RM (1972), "Reducibilidad entre problemas combinatorios", en Miller, RE; Thacher, JW (eds.), Complejidad de la computación informática , Nueva York: Plenum Press, págs. 85-103.

[5] Khot, S. ; Kindler, G.; Mossel, E.; O'Donnell, R. (2004), "¿Resultados de inaproximabilidad óptima para MAX-CUT y otros CSP de dos variables?" (PDF) , Actas del 45.º Simposio IEEE sobre fundamentos de la informática , págs. 146-154, archivado (PDF) del original el 15 de julio de 2019 , consultado el 29 de agosto de 2019.

[6] Goemans, MX ; Williamson, DP (1995), "Algoritmos de aproximación mejorados para problemas de corte máximo y satisfacibilidad utilizando programación semidefinida", Journal of the ACM , 42 (6): 1115–1145, doi : 10.1145/227683.227684 .

[7] Vazirani, Vijay V. (2004), Algoritmos de aproximación , Springer, págs. 97–98, ISBN 3-540-65367-8.

[8] Arora, Sanjeev ; Rao, Satish; Vazirani, Umesh (2009), "Flujos de expansión, incrustaciones geométricas y particionamiento de grafos", J. ACM , 56 (2), ACM: 1–37, doi :10.1145/1502793.1502794, S2CID 263871111 .

[gy-9] Gross, Jonathan L.; Yellen, Jay (2005), "4.6 Gráficos y espacios vectoriales", Teoría de grafos y sus aplicaciones (2.ª ed.), CRC Press, págs. 197-207, ISBN 9781584885054.

[diestel-10] Diestel, Reinhard (2012), "1.9 Algo de álgebra lineal", Teoría de grafos, Textos de posgrado en matemáticas, vol. 173, Springer, págs. 23-28.

[11] Korte, BH ; Vygen, Jens (2008), "8.6 Árboles de Gomory–Hu", Optimización combinatoria: teoría y algoritmos , Algorithms and Combinatorics, vol. 21, Springer, págs. 180–186, ISBN 978-3-540-71844-4.