En teoría de grafos , un subconjunto de vértices es un separador de vértices (o corte de vértice , conjunto separador ) para los vértices no adyacentes a y b si la eliminación de S del grafo separa a y b en componentes conexos distintos .
Considere un gráfico de cuadrícula con r filas y c 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 sola fila central y, de lo contrario, hay dos filas igualmente cercanas al centro; de manera similar, si c es impar, hay una sola columna central y, de lo contrario, hay dos columnas igualmente cercanas al centro. Elegir S como cualquiera de estas filas o columnas centrales y eliminar S del gráfico, 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, cada árbol libre T tiene un separador S que consiste en un único vértice, cuya eliminación divide a 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 bicentrado . [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 planar .
Sea S un ( a , b ) -separador, es decir, un subconjunto de vértices que separa dos vértices no adyacentes a y b . Entonces S es un ( a , b ) -separador mínimo si ningún subconjunto propio de S separa a y b . De manera más general, S se denomina un separador mínimo si es un separador mínimo para algún par ( a , b ) de vértices no adyacentes. Nótese que esto es diferente del conjunto separador mínimo que dice que ningún subconjunto propio de S es un ( u , v ) -separador mínimo para cualquier par de vértices ( u , v ) . El siguiente es un resultado bien conocido que caracteriza a los separadores mínimos: [3]
Lema. Un separador de vértices S en G es minimal si y solo si el grafo G – S , obtenido al eliminar S de G , tiene dos componentes conexas 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 grafo dado G , un separador ( a , b ) S puede considerarse como predecesor de otro separador ( a , b ) T , si cada camino de a a b se encuentra con S antes de encontrarse con T . Más rigurosamente, la relación predecesora se define de la siguiente manera: Sean S y T dos separadores ( a , b ) en G . Entonces S es un predecesor de T , en símbolos , si para cada x ∈ S \ T , cada camino que conecta x a b se encuentra con T . De la definición se deduce que la relación predecesora produce un preorden en el conjunto de todos los separadores ( a , b ) . 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 .
