separador de vértices

En teoría de grafos , un subconjunto de vértices $S\subset V$ ⁠ es un separador de vértices (o corte de vértices , conjunto separador ) para vértices no adyacentes $a$ y $b$ si la eliminación de $S$ del grafo separa $a$ y $b$ en componentes conexas distintas .

Ejemplos

Consideremos un grafo de cuadrícula con $r$ filas y $c$ columnas; el número total $n$ de vértices es $r \times c$ . Por ejemplo, en la ilustración, $r = 5$ , $c = 8$ y $n = 40.$ Si $r$ es impar, hay una única fila central, y de lo contrario hay dos filas igualmente cerca del centro; de manera similar, si $c$ es impar, hay una única columna central, y de lo contrario hay dos columnas igualmente cerca del centro. Eligiendo $S$ como cualquiera de estas filas o columnas centrales, y eliminando $S$ del grafo, se particiona el grafo 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 \leq c$ (como en la ilustración), entonces elegir una columna central dará un separador $S$ con $r\leq {\sqrt {n}}$ vértices, y de manera similar si $c \leq r$ entonces elegir una fila central dará un separador con como máximo ${\sqrt {n}}$ vértices. Por lo tanto, cada grafo de cuadrícula tiene un separador $S$ de tamaño como máximo ${\sqrt {n}},$ La eliminación de la cual lo divide en dos componentes conexas, cada una de tamaño como máximo $n$ $⁄$ $2$ . ^[¹^]

A la izquierda, un árbol centrado; a la derecha, uno bicéntrico. Los números indican la excentricidad de cada nodo.

Para dar otro ejemplo, todo árbol libre $T$ tiene un separador $S$ que consiste en un solo vértice, cuya eliminación divide $T$ en dos o más componentes conexas, cada una de tamaño como máximo $n$ $/$ $2$ . Más precisamente, siempre hay exactamente uno o exactamente dos vértices que constituyen dicho separador, dependiendo de si el árbol es centrado o bicéntrico . ^[²^]

A diferencia de estos ejemplos, no todos los separadores de vértices están equilibrados , pero esa propiedad es muy útil para aplicaciones en ciencias de la computación, como el teorema del separador planar .

separadores mínimos

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 (a, b) mínimo si ningún subconjunto propio de S separa a y b$ $.$ De $manera$ más $general$ , S $se$ $llama$ $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 separador$ $($ $u$ $,$ $v$ $)$ mínimo para cualquier par de vértices $($ $u$ $,$ $v$ $)$ . El siguiente es un resultado bien conocido que caracteriza a los separadores mínimos: ^[³^]

Lema. Un separador de vértices $S$ en $G$ es mínimo 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 $G$ dado , un separador $(a, b)$ $S$ puede considerarse un predecesor de otro separador $(a, b)$ $T$ , si todo camino de $a$ a $b$ encuentra $a S$ antes de encontrar $a T.$ De forma más rigurosa, la relación de predecesor se define como sigue: sean $S$ y $T$ dos separadores $(a, b)$ en $G.$ Entonces $S$ es un predecesor de $T$ , en símbolos $S\sqsubseteq _{a,b}^{G}T$ , si para cada $x ∈ S \ T$ , cada camino que conecta $x$ con $b$ pasa por $T$ . De la definición se deduce que la relación de predecesor produce un preorden en el conjunto de todos los $(a, b)$ -separadores. Además, Escalante (1972) demostró que la relación de predecesor da lugar a un retículo completo cuando se restringe al conjunto de los $($ $a$ $,$ $b$ $) -separadores$ mínimos en $G$ .

Véase también

Grafo cordal , un grafo en el que cada separador mínimo es una camarilla .
grafo k-vértice-conectado

Notas

↑ George (1973) . En lugar de usar una fila o columna de un gráfico de cuadrícula, George divide el gráfico en cuatro partes usando la unión de una fila y una columna como separador.
↑ Jordán (1869)
↑ Golumbic (1980) .

Referencias

Escalante, F. (1972). "Schnittverbände en Graphen". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg . 38 : 199–220 . doi : 10.1007/BF02996932 .
George, J. Alan (1973), "Análisis anidado de una malla de elementos finitos regular", SIAM Journal on Numerical Analysis , 10 (2): 345–363 , Bibcode : 1973SJNA...10..345G , doi : 10.1137/0710032 , JSTOR 2156361 .
Golumbic, Martin Charles (1980), Teoría algorítmica de grafos y grafos perfectos , Academic Press, ISBN 0-12-289260-7.
Jordania, Camille (1869). "Sur les assemblages de lignes" . Journal für die reine und angewandte Mathematik (en francés). 70 (2): 185-190 .
Rosenberg, Arnold ; Heath, Lenwood (2002). Separadores de grafos, con aplicaciones . Fronteras de la informática. Springer. doi : 10.1007/b115747 . ISBN 0-306-46464-0.

[g73-1] George (1973) . En lugar de usar una fila o columna de un gráfico de cuadrícula, George divide el gráfico en cuatro partes usando la unión de una fila y una columna como separador.

[Jordan-2] Jordán (1869)

[3] Golumbic (1980) .

[

[

[