Grafo dividido

De testwiki
Ir a la navegación Ir a la búsqueda
Un grafo dividido, dividido en un clique y un conjunto independiente.

En la teoría de grafos, una rama de las matemáticas, un grafo dividido (o el grafo split) es un grafo en el que los vértices se pueden dividir en una clique y un conjunto independiente . Los grafos divididos fueron estudiados por primera vez por Földes y Hammer (1977), e introducido independientemente por Tyshkevich y Cherniak (1979).[1]

Un grafo dividido puede tener más de una partición en un clique y un conjunto independiente; por ejemplo, el camino Plantilla:Math es un grafo dividido, cuyos vértices se pueden dividir de tres maneras diferentes:

  1. el clique Plantilla:Math} y el conjunto independiente Plantilla:Math}
  2. el clique Plantilla:Math} y el conjunto independiente Plantilla:Math}
  3. el clique Plantilla:Math} y el conjunto independiente Plantilla:Math}

Los grafos divididos se pueden caracterizar en términos de sus subgrafos inducidos prohibidos : un gráfico se divide si y solo si ningún subgrafo inducido es un ciclo en cuatro o cinco vértices, o un par de aristas disjuntas (el complemento de un 4-ciclo).[2]

Relación con otras familias de grafos

A partir de la definición, los grafos divididos están claramente cerrados bajo complementación .[3] Otra caracterización de los grafos divididos implica la complementación: son grafos cordales cuyos complementos también son cordales.[4] Así como los grafos cordales son los grafos de intersección de los subárboles de los árboles, los grafos divididos son los grafos de intersección de distintas subestrellas de los grafos de estrellas .[5] Casi todos los grafos cordales son grafos divididos; es decir, en el límite cuando n tiende a infinito, la fracción de gráficos cordales de n vértices que se dividen se aproxima a uno.[6]

Debido a que los grafos cordales son perfectos, también lo son los grafos divididos. Los grafos de división doble, una familia de grafos derivados de grafos divididos al duplicar cada vértice (de modo que la camarilla llega a inducir un antiemparejamiento y el conjunto independiente viene a inducir un emparejamiento), figura de manera destacada como una de las cinco clases básicas de grafos perfectos de los cuales todos los demás pueden formarse en la prueba de Plantilla:Harvtxt del teorema del gráfico perfecto fuerte .

Si un grafos es a la vez un grafos dividido y un grafos de intervalos, entonces su complemento es tanto un gráfico dividido como un grafo de comparabilidad, y viceversa. Los grafos de comparabilidad dividida y, por lo tanto, también los grafos de intervalo dividido, se pueden caracterizar en términos de un conjunto de tres subgrafos inducidos prohibidos.[7] Los cografos divididos son exactamente los grafos de umbral . Los grafos de permutación dividida son exactamente los grafos de intervalo que tienen complementos de grafo de intervalo;[8] estos son los grafos de permutación de permutaciones combinadas sesgadas . [9] Los grafos divididos tienen el número cocromático 2.

Problemas algorítmicos

Sea Plantilla:Mvar un grafo dividido, dividido en una camarilla Plantilla:Mvar y un conjunto independiente Plantilla:Mvar . Entonces, cada clique máximo en un grafo dividido es Plantilla:Mvar en sí mismo o la vecindad de un vértice en Plantilla:Mvar . Por lo tanto, es fácil identificar el clique máximo y, complementariamente, el conjunto independiente máximo en un grafo dividido. En cualquier grafo dividido, una de las siguientes tres posibilidades debe ser verdadera:[9]

  1. Existe un vértice Plantilla:Mvar en Plantilla:Mvar tal que Plantilla:Math} es completo. En este caso, Plantilla:Math} es un clique máxima e Plantilla:Mvar es un conjunto independiente máximo.
  2. Existe un vértice Plantilla:Mvar en Plantilla:Mvar tal que Plantilla:Math} es independiente. En este caso, Plantilla:Math} es un conjunto independiente máximo y Plantilla:Mvar es un clique máxima.
  3. Plantilla:Mvar es un clique máximo e Plantilla:Mvar es un conjunto independiente máximo. En este caso, Plantilla:Mvar tiene una partición única Plantilla:Math en un clique y un conjunto independiente, Plantilla:Mvar es el clique máximo e Plantilla:Mvar es el conjunto independiente máximo.

Algunos otros problemas de optimización que son NP-completos en familias de grafos más generales, incluida la coloración de grafos, son igualmente sencillos en grafos divididos. Encontrar un ciclo hamiltoniano sigue siendo NP-completo incluso para grafos divididos que son grafos fuertemente cordales .[10] También es bien sabido que el problema del Conjunto Dominante Mínimo sigue siendo NP-completo para grafos divididos.[11]

Secuencias de grado

Una propiedad notable de los grafos divididos es que pueden reconocerse únicamente a partir de sus secuencias de grados . Sea la secuencia de grados de un gráfico Plantilla:Mvar d1≥d2≥…≥dn, y sea Plantilla:Mvar el mayor valor de Plantilla:Mvar tal que di≥i−1 . Entonces Plantilla:Mvar es un grafo dividido si y solo si

∑i=1mdi=m(m−1)+∑i=m+1ndi.

Si este es el caso, entonces los Plantilla:Mvar vértices con los grados más grandes forman un clique máxima en Plantilla:Mvar, y los vértices restantes constituyen un conjunto independiente.[12]

La división de un grafo arbitrario mide hasta qué punto esta desigualdad no se cumple. Si un grafo no es un grafo dividido, entonces se puede obtener la secuencia más pequeña de inserciones y eliminaciones de bordes que lo convierten en un gráfico dividido sumando todos los bordes que faltan entre los Plantilla:Mvar vértices con los grados más grandes y eliminando todos los bordes entre pares de los vértices restantes; la división cuenta el número de operaciones en esta secuencia. [14]

Contando gráficos divididos

Royle (2000) mostró que los grafos divididos en n vértices con n tienen una correspondencia biunívoca con ciertas familias de Sperner. Utilizando este hecho, determinó una fórmula para el número de gráficos divididos no isomorfos en n vértices. Para valores pequeños de n, a partir de n = 1, estos números son

1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696,... Plantilla:OEIS .

Este resultado enumerativo también fue probado anteriormente por Plantilla:Harvtxt .

Referencias

Plantilla:Listaref

Bibliografía

Plantilla:Refbegin

Plantilla:Refend

Otras lecturas

  • Un capítulo sobre gafos divididos aparece en el libro de Martin Charles Golumbic, "Teoría de grafos algorítmicos y grafos perfectos".

Plantilla:Control de autoridades

  1. ↑ Plantilla:Harvtxt had a more general definition, in which the graphs they called split graphs also included bipartite graphs (that is, graphs that be partitioned into two independent sets) and the complements of bipartite graphs (that is, graphs that can be partitioned into two cliques).Plantilla:Harvtxt use the definition given here, which has been followed in the subsequent literature; for instance, it is Plantilla:Harvtxt, Definition 3.2.3, p.41.
  2. ↑ Plantilla:Harvtxt;Plantilla:Harvtxt, Theorem 6.3, p. 151.
  3. ↑ Plantilla:Harvtxt, Theorem 6.1, p. 150.
  4. ↑ Plantilla:Harvtxt;Plantilla:Harvtxt, Theorem 6.3, p. 151;Plantilla:Harvtxt, Theorem 3.2.3, p. 41.
  5. ↑ Plantilla:Harvtxt;Plantilla:Harvtxt;Plantilla:Harvtxt, Theorem 4.4.2, p. 52.
  6. ↑ Plantilla:Harvtxt.
  7. ↑ Plantilla:Harvtxt;Plantilla:Harvtxt, Theorem 9.7, page 212.
  8. ↑ Plantilla:Harvtxt, Corollary 7.1.1, p. 106, and Theorem 7.1.2, p. 107.
  9. ↑ Plantilla:Harvtxt;Plantilla:Harvtxt, Theorem 6.2, p. 150.
  10. ↑ Plantilla:Harvtxt
  11. ↑ Plantilla:Harvtxt
  12. ↑ Plantilla:Harvtxt;Plantilla:Harvtxt;Plantilla:Harvtxt;Plantilla:Harvtxt, Theorem 6.7 and Corollary 6.8, p. 154;Plantilla:Harvtxt, Theorem 13.3.2, p. 203.Plantilla:Harvtxt further investigates the degree sequences of split graphs.
Obtenido de «https://es.wiki.beta.math.wmflabs.org/w/index.php?title=Grafo_dividido&oldid=12766»