stringtranslate.com

Dividir gráfico

Un gráfico dividido, dividido en una camarilla y un conjunto independiente.

En teoría de grafos , una rama de las matemáticas, un gráfico dividido es un gráfico en el que los vértices se pueden dividir en una camarilla y un conjunto independiente . Los gráficos divididos fueron estudiados por primera vez por Földes y Hammer (1977a, 1977b), y Tyshkevich y Chernyak (1979)  los introdujeron de forma independiente , donde llamaron a estos gráficos "gráficos polares" ( ruso : полярные графы ). [1]

Un gráfico dividido puede tener más de una partición en una camarilla y un conjunto independiente; por ejemplo, la ruta a – b – c es un gráfico dividido, cuyos vértices se pueden dividir de tres maneras diferentes:

  1. la camarilla { a , b } y el conjunto independiente { c }
  2. la camarilla { b , c } y el conjunto independiente { a }
  3. la camarilla { b } y el conjunto independiente { a , c }

Los gráficos 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 ciclo de 4). [2]

Relación con otras familias de gráficos

Según la definición, los gráficos 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 gráficos cordales son los gráficos de intersección de subárboles de árboles, los gráficos divididos son los gráficos de intersección de distintas subestrellas de gráficos estelares . [5] Casi todos los gráficos cordales son gráficos divididos; es decir, en el límite cuando n llega al infinito, la fracción de gráficos cordales de n -vértices que se dividen se acerca a uno. [6]

Debido a que las gráficas cordales son perfectas , también lo son las gráficas divididas. Los gráficos de doble división , una familia de gráficos derivados de gráficos divididos al duplicar cada vértice (de modo que la camarilla llega a inducir un antiemparejamiento y el conjunto independiente llega a inducir un emparejamiento), ocupan un lugar destacado como una de las cinco clases básicas de gráficos perfectos de los cuales todos los demás pueden formarse en la prueba de Chudnovsky et al. (2006) del Teorema del grafo perfecto fuerte .

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

Problemas algorítmicos

Sea G un gráfico dividido, dividido en una camarilla C y un conjunto independiente i . Entonces, cada camarilla máxima en un gráfico dividido es C en sí o la vecindad de un vértice en i . Por lo tanto, es fácil identificar la camarilla máxima y, complementariamente, el conjunto independiente máximo en un gráfico dividido. En cualquier gráfico dividido, una de las siguientes tres posibilidades debe ser cierta: [10]

  1. Existe un vértice x en i tal que C ∪ { x } está completo. En este caso, C ∪ { x } es una camarilla máxima e i es un conjunto máximo independiente.
  2. Existe un vértice x en C tal que i ∪ { x } es independiente. En este caso, i ∪ { x } es un conjunto máximo independiente y C es una camarilla máxima.
  3. C es una camarilla máxima y i es un conjunto independiente máximo. En este caso, G tiene una partición única ( C , i ) en una camarilla y un conjunto independiente, C es la camarilla máxima e i es el conjunto independiente máximo.

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

secuencias de grados

Una propiedad notable de los gráficos divididos es que pueden reconocerse únicamente por sus secuencias de grados . Sea la secuencia de grados de un gráfico G d 1 ≥ d 2 ≥ … ≥ d n , y sea m el valor más grande de i tal que d i ≥ i – 1 . Entonces G es un gráfico dividido si y sólo si

Si este es el caso, entonces los m vértices con los grados más grandes forman una camarilla máxima en G , y los vértices restantes constituyen un conjunto independiente. [13]

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

Contando gráficos divididos

Royle (2000) demostró que los gráficos divididos de n -vértices ( sin etiquetar ) están en correspondencia uno a uno 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, ... (secuencia A048194 en el OEIS ).

Este resultado enumerativo también fue demostrado anteriormente por Tyshkevich y Chernyak (1990).

Notas

  1. ^ Földes y Hammer (1977a) tenían una definición más general, en la que las gráficas que llamaron gráficas divididas también incluían gráficas bipartitas (es decir, gráficas que se dividen en dos conjuntos independientes) y los complementos de gráficas bipartitas (es decir, gráficas que puede dividirse en dos camarillas). Földes y Hammer (1977b) utilizan la definición dada aquí, que ha sido seguida en la literatura posterior; por ejemplo, es Brandstädt, Le & Spinrad (1999), Definición 3.2.3, p.41.
  2. ^ Földes y martillo (1977a); Golumbic (1980), Teorema 6.3, pág. 151.
  3. ^ Golumbic (1980), Teorema 6.1, pág. 150.
  4. ^ Földes y martillo (1977a); Golumbic (1980), Teorema 6.3, pág. 151; Brandstädt, Le y Spinrad (1999), Teorema 3.2.3, pág. 41.
  5. ^ McMorris y Shier (1983); Voss (1985); Brandstädt, Le y Spinrad (1999), Teorema 4.4.2, pág. 52.
  6. ^ Bender, Richmond y Wormald (1985).
  7. ^ Földes y martillo (1977b); Golumbic (1980), Teorema 9.7, página 212.
  8. ^ Brandstädt, Le & Spinrad (1999), Corolario 7.1.1, p. 106 y teorema 7.1.2, pág. 107.
  9. ^ Kézdy, Snevily y Wang (1996).
  10. ^ Martillo y Simeone (1981); Golumbic (1980), Teorema 6.2, pág. 150.
  11. ^ Muller (1996)
  12. ^ Bertossi (1984)
  13. ^ Martillo y Simeone (1981); Tyshkevich (1980); Tyshkevich, Melnikow y Kotov (1981); Golumbic (1980), Teorema 6.7 y Corolario 6.8, p. 154; Brandstädt, Le y Spinrad (1999), Teorema 13.3.2, pág. 203. Merris (2003) investiga más a fondo las secuencias de grados de gráficos divididos.
  14. ^ Martillo y Simeone (1981).

Referencias

Otras lecturas