En teoría de grafos , un subconjunto de vértices es un separador de vértices (o corte de vértices , conjunto de separación ) para los vértices a y b no adyacentes si la eliminación de S del gráfico separa a y b en componentes conectados distintos .
Considere un gráfico de cuadrícula con r filas yc columnas ; el número total n de vértices es r × c . Por ejemplo, en la ilustración, r = 5 , c = 8 y n = 40 . Si r es impar, hay una única fila central y, en caso contrario, hay dos filas igualmente cercanas al centro; de manera similar, si c es impar, hay una sola columna central y, en caso contrario, hay dos columnas igualmente cercanas al centro. Al elegir S como cualquiera de estas filas o columnas centrales y eliminar S del gráfico, se divide el gráfico en dos subgrafos conectados más pequeños A y B , cada uno de los cuales tiene como máximo n ⁄ 2 vértices. Si r ≤ c (como en la ilustración), entonces elegir una columna central dará un separador S con vértices, y de manera similar si c ≤ r entonces elegir una fila central dará un separador con como máximo vértices. Por lo tanto, cada gráfico de cuadrícula tiene un separador S de tamaño como máximo, cuya eliminación lo divide en dos componentes conectados, cada uno de tamaño como máximo n ⁄ 2 . [1]
Para dar otra clase de ejemplos, todo árbol libre T tiene un separador S que consta de un solo vértice, cuya eliminación divide T en dos o más componentes conectados, cada uno de tamaño como máximo n ⁄ 2 . Más precisamente, siempre hay exactamente uno o exactamente dos vértices, que equivalen a dicho separador, dependiendo de si el árbol está centrado o bicéntrico . [2]
A diferencia de estos ejemplos, no todos los separadores de vértices están equilibrados , pero esa propiedad es más útil para aplicaciones en informática, como el teorema del separador plano .
Sea S un separador ( a , b ) , es decir, un subconjunto de vértices que separa dos vértices no adyacentes a y b . Entonces S es un separador mínimo ( a , b ) si ningún subconjunto adecuado de S separa a y b . De manera más general, S se denomina separador mínimo si es un separador mínimo para algún par ( a , b ) de vértices no adyacentes. Observe que esto es diferente del conjunto separador mínimo que dice que ningún subconjunto propio de S es un separador mínimo ( u , v ) para cualquier par de vértices ( u , v ) . El siguiente es un resultado bien conocido que caracteriza los separadores mínimos: [3]
Lema. Un separador de vértices S en G es mínimo si y sólo si el gráfico G – S , obtenido eliminando S de G , tiene dos componentes conectados C 1 y C 2 tales que cada vértice en S es adyacente a algún vértice en C 1 y a algún vértice en C 2 .
Los separadores mínimos ( a , b ) también forman una estructura algebraica : para dos vértices fijos a y b de un gráfico dado G , un separador ( a , b ) S puede considerarse como un predecesor de otro ( a , b ). -separador T , si cada camino de aab encuentra S antes de encontrarse con T . Más rigurosamente, la relación predecesora se define de la siguiente manera: Sean S y T dos ( a , b ) -separadores en G. Entonces S es un predecesor de T , en símbolos , si para cada x ∈ S \ T , cada camino que conecta x con b encuentra a T. De la definición se deduce que la relación predecesora produce un preorden en el conjunto de todos los ( a , b ) -separadores. Además, Escalante (1972) demostró que la relación predecesora da lugar a una red completa cuando se restringe al conjunto de separadores mínimos ( a , b ) en G.
