Gráfico indiferente

Un grafo indiferente es un grafo no dirigido construido asignando un número real a cada vértice y conectando dos vértices con una arista cuando sus números difieren en no más de uno [1] . Los gráficos indiferentes también son gráficos de intersecciones de conjuntos de segmentos unitarios o intervalos con una determinada propiedad de incrustación (ningún intervalo contiene otro). Con base en estos dos tipos de representaciones de intervalos, estos gráficos también se denominan gráficos de segmentos unitarios o gráficos de intervalos propios . Los gráficos indiferentes forman una subclase de gráficos de intervalo .

Descripciones equivalentes

Los gráficos indiferentes finitos se pueden describir de manera equivalente como

Para grafos infinitos, algunas de estas definiciones pueden estar dadas por diferentes grafos.

Propiedades

Dado que los gráficos indiferentes son un caso especial de los gráficos de intervalo , los gráficos indiferentes tienen todas las propiedades de los gráficos de intervalo. En particular, son un caso especial de grafos cordales y grafos perfectos . Estos gráficos también son un caso especial de gráficos circulares , lo que no es cierto para los gráficos de intervalos generales.

En el modelo de grafos aleatorios de Erdős-Rényi , un grafo a partir de un vértice cuyo número de aristas sea sustancialmente menor será un grafo indiferente con una alta probabilidad, mientras que los grafos con un número de aristas sustancialmente mayor que no serán un grafo indiferente con un alta probabilidad [9] .

El ancho de la cinta de un gráfico arbitrarioes uno menos que el tamaño de la camarilla más grande en el gráfico indiferente que contienecomo subgráfico y se elige para minimizar el tamaño de la camarilla más grande [10] . Esta propiedad forma paralelos, similar a la conexión entre los gráficos de ancho de ruta y de intervalo , y entre los gráficos de ancho de árbol y cordales . Una noción más débil de ancho, ancho de camarilla , puede ser arbitrariamente grande en gráficos indiferentes [11] . Sin embargo, cualquier subclase propia de gráficos indiferentes que no esté cerrada con respecto a los subgráficos generados tiene un ancho de camarilla acotado [12] .

Cualquier gráfico indiferente conectado contiene un camino hamiltoniano [13] . Un grafo indiferente tiene un grafo hamiltoniano si y solo si es doblemente conexo [14] .

Los gráficos indiferentes satisfacen la conjetura de reconstrucción : están definidos de forma única por sus subgrafos con vértices eliminados [15] .

Algoritmos

Al igual que con los gráficos de discos unitarios multidimensionales , es posible transformar un conjunto de puntos en su gráfico indiferente o un conjunto de segmentos unitarios en su gráfico de segmento unitario en tiempo lineal , medido en términos del tamaño del gráfico de salida. El algoritmo redondea puntos (o centros de intervalos) al entero menor más cercano, usa una tabla hash para encontrar todos los pares de puntos cuyos valores redondeados difieren en no más de uno ( problema de vecino más cercano de radio fijo ) y selecciona pares en la lista resultante, cuyos valores no redondeados no son más que uno aparte [16] .

Uno puede probar si un gráfico dado es indiferente en tiempo lineal usando árboles PQ para construir representaciones de intervalo del gráfico y luego probar si el ordenamiento de vértices derivado de esta representación satisface las propiedades de un gráfico indiferente [4] . También se puede basar el algoritmo de reconocimiento para gráficos indiferentes en algoritmos de reconocimiento para el gráfico cordal [14] . Algunos algoritmos alternativos de reconocimiento de tiempo lineal se basan en la búsqueda primero en amplitud o en la búsqueda lexicográfica en amplitud , en lugar de en la relación entre gráficos indiferentes y gráficos de intervalo [17] [18] [19] [20] .

Una vez que se ordenan los vértices por sus valores numéricos que describen un gráfico indiferente (o por una secuencia de segmentos unitarios en una representación de intervalo), se puede usar el mismo orden para encontrar la coloración óptima de estos gráficos para resolver el problema del camino más corto , construcción de caminos hamiltonianos y mayores coincidencias en tiempo lineal [4] . Se puede encontrar un ciclo hamiltoniano a partir de un gráfico de representación de intervalo adecuado en el tiempo [13] , pero si el gráfico es una entrada para un problema, el mismo problema se puede resolver en tiempo lineal, que se puede generalizar a gráficos de intervalo [21] [ 22] .

La coloración prescrita sigue siendo NP-completa incluso cuando se restringe a gráficos indiferentes [23] . Sin embargo, se puede resolver de forma paramétrica fija si se parametriza por el número total de colores de entrada [12] .

Aplicaciones

En psicología matemática , los gráficos indiferentes surgen de las funciones de utilidad al escalar la función de modo que una unidad represente una diferencia en la utilidad lo suficientemente pequeña como para que la unidad pueda considerarse insignificante para el individuo. En esta aplicación, los pares de elementos cuyas utilidades son lo suficientemente grandes pueden ordenarse parcialmente por orden relativo de utilidad, dando como resultado el semiorden [1] [24] .

En bioinformática , la tarea de agregar un gráfico coloreado a un gráfico coloreado correctamente de segmentos unitarios puede usarse para modelar la detección de ensamblajes de genoma de ADN falsos negativos a partir de fragmentos [25] .

Véase también

Notas

  1. ↑ 1 2 3 4 5 6 Roberts, 1969 , pág. 139–146.
  2. ↑ 1 2 Bogart, West, 1999 , pág. 21–23.
  3. ↑ Wegner, 1967 .
  4. ↑ 1 2 3 Looges, Olariu, 1993 , p. 15–25.
  5. ↑ Jackowski, 1992 , pág. 103–109.
  6. ↑ 1 2 Gutiérrez, Oubina, 1996 , p. 199–205.
  7. ↑ Mertzios, 2008 , pág. 332–337.
  8. ↑ 1 2 Brandstädt, Hundt, Mancini, Wagner, 2010 , p. 897–910.
  9. ↑ Cohen, 1982 , pág. 21–24.
  10. ↑ Kaplan, Shamir, 1996 , pág. 540–561.
  11. ↑ Golumbic, Rotics, 1999 , p. 5–17.
  12. ↑ 1 2 Lozin, 2008 , pág. 871–882.
  13. ↑ 1 2 Bertossi, 1983 , p. 97–101.
  14. ↑ 1 2 Panda, Das, 2003 , p. 153–161.
  15. ↑ von Rimscha, 1983 , p. 283–291.
  16. ↑ Bentley, Stanat, Williams, 1977 , pág. 209–212.
  17. ↑ Corneil, Kim, Natarajan, Olariu, Sprague, 1995 , pág. 99–104.
  18. ↑ Herrera de Figueiredo, Meidanis, Picinin de Mello, 1995 , p. 179–184.
  19. ↑ Corneil, 2004 , pág. 371–379.
  20. ↑ Infierno, Huang, 2004 , p. 554–570.
  21. ↑ Keil, 1985 , pág. 201–206.
  22. ↑ Ibarra, 2009 , pág. 1105–1108.
  23. ↑ Marx, 2006 , pág. 995–1002.
  24. ↑ Roberts, 1970 , pág. 243–258.
  25. ↑ Goldberg, Golumbic, Kaplan, Shamir, 2009 .

Literatura

Enlaces