Corte (teoría de grafos)
La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 11 de agosto de 2021; las comprobaciones requieren 2 ediciones .Un gráfico cortado en problemas de flujo es un par de conjuntos de vértices (S,T) tales que
- , donde es el conjunto de vértices del gráfico
- , donde está la fuente, está el desagüe.
El tamaño del corte es la suma de las capacidades de tales filos que .
Otras definiciones de un corte (sección) de un gráfico
- Un corte de grafo es un conjunto de aristas que forman un subgrafo bipartito , cuya eliminación divide el grafo en dos o más componentes, que, en particular, pueden ser nodos aislados. Así como una línea que pasa por todos los bordes del corte del gráfico.
Características
- Las líneas de sección pueden cruzar un número arbitrario de aristas y cuerdas.
- Para obtener la sección principal del gráfico, es necesario dibujar la línea de sección del gráfico de tal manera que interseque solo una rama del gráfico en una intersección arbitraria de cuerdas.