Separador de vértices (teoría de grafos)

En la teoría de grafos, un subconjunto de vértices se denomina separador de vértices para vértices no adyacentes y , si la eliminación del gráfico separa y en dos componentes conectados .

Ejemplos

Supongamos que dada una red con r filas y c columnas, entonces el número total de n vértices es r*c . Por ejemplo, en la figura, r  = 5, c  = 8 y n  = 40. Si r es impar, hay una fila central, de lo contrario, hay dos filas igualmente cerca del centro. De la misma manera, si c es impar, hay una columna central, de lo contrario, hay dos columnas igualmente cerca del centro. Eligiendo una de estas filas o columnas como S , y eliminando S del gráfico, obtenemos una partición del gráfico en dos subgráficos conectados más pequeños A y B , cada uno de los cuales contiene como máximo n / 2 vértices. Si r  ≤  c (como en la ilustración), elegir la columna central dará un separador S con r  ≤ √ n vértices y, de manera similar, si c  ≤  r , elegir la fila central dará un separador con √ n vértices como máximo . Por lo tanto, cualquier gráfico-retículo tiene un separador S con tamaño como máximo √ n , cuya eliminación divide el gráfico en dos componentes conectados, cada uno con tamaño como máximo n /2 [1] .

Otra clase de ejemplos es un árbol libre T que tiene un separador S de un solo vértice cuya eliminación divide a T en dos (o más) componentes conectados, cada uno de tamaño máximo n /2. Más precisamente, hay exactamente uno o dos vértices, dependiendo de si el árbol está centrado o bicéntrico [2] .

Al contrario de los ejemplos dados, no todos los separadores de vértices están balanceados , pero esta propiedad es más útil para aplicaciones informáticas.

Separadores mínimos

Sea S un separador (a,b) , es decir, un subconjunto de vértices que separan dos vértices a y b no adyacentes . Entonces S es un separador mínimo (a,b) si ningún subconjunto de S separa a y b . Un conjunto S se llama separador mínimo si es un separador mínimo para cualquier par (a,b) de vértices no adyacentes. A continuación se muestra un resultado bien conocido sobre la caracterización de los separadores mínimos [3] :

Lema. Un separador de vértices S en G es mínimo si y solo si el gráfico obtenido al eliminar S de G tiene dos componentes conexas y tal que cada vértice en S está conectado a algún vértice en y algún vértice en .

Los separadores mínimos forman un sistema algebraico : para dos vértices fijos a y b de un grafo dado G , un separador (a,b) S puede considerarse un predecesor de otro separador (a,b) T si cualquier camino de a a b golpea S antes que para llegar a T . Más estrictamente, la relación de precedencia se define como sigue: Sean S y T dos (a,b) -separadores en 'G'. Entonces S es el predecesor de T , que se denota como si, para cualquier vértice , cualquier camino entre x y b contuviera un vértice desde T . De la definición se sigue que la relación de precedencia es un orden previo en el conjunto de todos los separadores (a,b) . Además, Escalante [4] demostró que la relación de precedencia se convierte en un retículo completo si nos restringimos al conjunto de mínimos (a,b) -separadores G .

Véase también

Notas

  1. ↑ J. Alan George. Disección anidada de una malla regular de elementos finitos // SIAM Journal on Numerical Analysis. - 1973. - T. 10 , núm. 2 . - S. 345-363 . -doi : 10.1137/ 0710032 . — . . En lugar de usar las filas y las columnas del gráfico, George divide el gráfico en cuatro partes combinando las filas y las columnas como separador.
  2. ↑ Camille Jordán. Sur les assemblages de lignes  (francés)  // Journal für die reine und angewandte Mathematik . - 1869. - T. 70 , núm. 2 . - S. 185-190 .
  3. ↑ Martín Charles Golumbic. Teoría de grafos algorítmicos y grafos perfectos. - Prensa académica, 1980. - ISBN 0-12-289260-7 .
  4. ↑ F. Escalante. Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg. - 1972. - T. 38. - S. 199-220. -doi : 10.1007/ BF02996932 .

Literatura