En teoría de grafos , un subconjunto de vérticeses un separador de vértices (o corte de vértice , conjunto de separación ) para vértices no adyacentes y si la eliminación de del gráfico se separa y en distintos componentes conectados .
Ejemplos de
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 yn = 40. Si r es impar, hay una sola fila central y, de lo contrario, hay dos filas igualmente cerca del centro; de manera similar, si c es impar, hay una sola columna central y, de lo contrario, hay dos columnas igualmente cerca del centro. Al elegir S para que sea cualquiera de estas filas o columnas centrales, y eliminar S del gráfico, se divide el gráfico en dos subgráficos 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 r ≤ √ n vértices, y de manera similar si c ≤ r, entonces elegir una fila central dará un separador con un máximo de √ n vértices. Por lo tanto, cada gráfico de cuadrícula tiene un separador S de tamaño como máximo √ n , 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 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, lo que equivale a dicho separador, dependiendo de si el árbol está centrado o bicentro . [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 .
Separadores mínimos
Deje que S sea un (a, b) -separator, es decir, un subconjunto de vértices que separa dos vértices no adyacentes una y b . Entonces S es un (a, b) -separator mínimo si no subconjunto propio de S separa una 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 de separación mínimo que dice que ningún subconjunto adecuado 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 a 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 conectados y tal que cada vértice en S es adyacente a algún vértice en y a algún vértice en .
La mínima "(a, b)" - separadores también forman una estructura algebraica : Para dos vértices fijos una y B de un gráfico dado G , un (a, b) -separator S puede ser considerado como un predecesor de otro (a, b) -separator T , si cada camino desde una a b cumple S antes de que se reúne T . Más rigurosamente, la relación predecesora se define como sigue: Sean S y T dos separadores (a, b) en 'G'. Entonces S es un predecesor de T , en símbolos, si para cada , Cada vía de conexión x a b cumple 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) probó que la relación predecesor da lugar a un retículo completo cuando restringido al conjunto de un mínimo de (a, b) -separators en G .
Ver también
- Gráfico de cuerdas , un gráfico en el que cada separador mínimo es una camarilla .
- grafo conectado a k-vértices
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.
- ↑ Jordania (1869)
- ^ Golumbic (1980) .
Referencias
- Escalante, F. (1972). "Schnittverbände in Graphen". Abhandlungen aus dem Mathematischen Seminar der Universität Hamburg . 38 : 199–220. doi : 10.1007 / BF02996932 .
- George, J. Alan (1973), "Disección anidada de una malla regular de elementos finitos", SIAM Journal on Numerical Analysis , 10 (2): 345–363, doi : 10.1137 / 0710032 , JSTOR 2156361.
- Golumbic, Martin Charles (1980), Teoría algorítmica de gráficos y gráficos perfectos , Academic Press, ISBN 0-12-289260-7.
- Jordan, Camille (1869). "Sur les ensamblajes de líneas" . Journal für die reine und angewandte Mathematik (en francés). 70 (2): 185-190.
- Rosenberg, Arnold ; Heath, Lenwood (2002). Separadores de gráficos, con aplicaciones . Saltador. doi : 10.1007 / b115747 .