Gráfica de indiferencia

En teoría de grafos , una rama de las matemáticas, un grafo de indiferencia es un grafo no dirigido construido asignando un número real a cada vértice y conectando dos vértices por una arista cuando sus números están dentro de una unidad el uno del otro. ^[1] Los grafos de indiferencia también son los grafos de intersección de conjuntos de intervalos unitarios , o de intervalos anidados adecuadamente (intervalos ninguno de los cuales contiene a ningún otro). Con base en estos dos tipos de representaciones de intervalos, estos grafos también se denominan grafos de intervalos unitarios o grafos de intervalos adecuados ; forman una subclase de los grafos de intervalos .

Caracterizaciones equivalentes

Los gráficos de indiferencia finitos pueden caracterizarse de manera equivalente como

Los gráficos de intersección de intervalos unitarios , ^[1]
Los gráficos de intersección de conjuntos de intervalos en los que no hay dos anidados (uno contiene al otro), ^[1]^[2]
Los gráficos de intervalos sin garras , ^[1]^[2]
Los grafos que no tienen un subgrafo inducido isomorfo a una garra K _1,3 , red (un triángulo con un vértice de grado uno adyacente a cada uno de los vértices del triángulo), sol (un triángulo rodeado por otros tres triángulos que comparten cada uno una arista con el triángulo central), o agujero (ciclo de longitud cuatro o más), ^[3]
Los gráficos de incomparabilidad de los semiórdenes , ^[1]
Los grafos no dirigidos que tienen un orden lineal tal que, por cada tres vértices ordenados – – , si es una arista entonces también lo son y ^[4] ${\estilo de visualización u}$ ${\estilo de visualización v}$ ${\estilo de visualización w}$ ${\estilo de visualización uw}$ ${\estilo de visualización uv}$ ${\estilo de visualización vw}$
Los grafos sin triple astral , tres vértices conectados de a pares por caminos que evitan el tercer vértice y además no contienen dos vecinos consecutivos del tercer vértice, ^[5]
Los gráficos en los que cada componente conectado contiene un camino en el que cada camarilla máxima del componente forma un subcamino contiguo, ^[6]
Los gráficos cuyos vértices pueden numerarse de tal manera que cada camino más corto forme una secuencia monótona , ^[6]
Los grafos cuyas matrices de adyacencia pueden ordenarse de tal manera que, en cada fila y cada columna, los valores distintos de cero de la matriz formen un intervalo contiguo adyacente a la diagonal principal de la matriz. ^[7]
Los subgrafos inducidos de potencias de caminos sin cuerdas. ^[8]
Las hojas tienen una raíz que es una oruga. ^[8]

Para gráficos infinitos, algunas de estas definiciones pueden diferir.

Propiedades

Debido a que son casos especiales de grafos de intervalos , los grafos de indiferencia tienen todas las propiedades de los grafos de intervalos; en particular, son un caso especial de los grafos cordales y de los grafos perfectos . También son un caso especial de los grafos circulares , algo que no es cierto para los grafos de intervalos en general.

En el modelo Erdős–Rényi de grafos aleatorios , un grafo -vértice cuyo número de aristas es significativamente menor que será un grafo de indiferencia con alta probabilidad, mientras que un grafo cuyo número de aristas es significativamente mayor que no será un grafo de indiferencia con alta probabilidad. ^[9] ${\estilo de visualización n}$ $n^{2/3}$ $n^{2/3}$

El ancho de banda de un grafo arbitrario es uno menos que el tamaño de la camarilla máxima en un grafo de indiferencia que contiene como subgrafo y se elige para minimizar el tamaño de la camarilla máxima. ^[10] Esta propiedad es paralela a relaciones similares entre los grafos pathwidth y interval , y entre los grafos treewidth y chordal . Una noción más débil de ancho, el clique-width , puede ser arbitrariamente grande en grafos de indiferencia. ^[11] Sin embargo, cada subclase propia de los grafos de indiferencia que está cerrada bajo subgrafos inducidos tiene un ancho de camarilla acotado. ^[12] ${\estilo de visualización G}$ ${\estilo de visualización G}$

Todo gráfico de indiferencia conexo tiene un camino hamiltoniano . ^[13] Un gráfico de indiferencia tiene un ciclo hamiltoniano si y solo si es biconexo . ^[14]

Los gráficos de indiferencia obedecen a la conjetura de reconstrucción : están determinados únicamente por sus subgráficos con vértices eliminados. ^[15]

Algoritmos

Al igual que con los gráficos de disco unitario de dimensiones superiores , es posible transformar un conjunto de puntos en su gráfico de indiferencia, o un conjunto de intervalos unitarios en su gráfico de intervalo unitario, en tiempo lineal medido en términos del tamaño del gráfico de salida. El algoritmo redondea los puntos (o centros de intervalo) hacia abajo al entero más pequeño más cercano, utiliza una tabla hash para encontrar todos los pares de puntos cuyos enteros redondeados están dentro de uno del otro (el problema de vecinos cercanos de radio fijo ) y filtra la lista resultante de pares para aquellos cuyos valores no redondeados también están dentro de uno del otro. ^[16]

Es posible comprobar si un gráfico dado es un gráfico de indiferencia en tiempo lineal, utilizando árboles PQ para construir una representación de intervalo del gráfico y luego comprobar si un orden de vértices derivado de esta representación satisface las propiedades de un gráfico de indiferencia. ^[4] También es posible basar un algoritmo de reconocimiento para gráficos de indiferencia en algoritmos de reconocimiento de gráficos cordales . ^[14] Varios algoritmos alternativos de reconocimiento de tiempo lineal se basan en la búsqueda en amplitud o en la búsqueda en amplitud lexicográfica en lugar de en la relación entre gráficos de indiferencia y gráficos de intervalo. ^[17]^[18]^[19]^[20]

Una vez que los vértices han sido ordenados por los valores numéricos que describen un gráfico de indiferencia (o por la secuencia de intervalos unitarios en una representación de intervalo), se puede utilizar el mismo ordenamiento para encontrar una coloración gráfica óptima para estos gráficos, para resolver el problema del camino más corto y para construir caminos hamiltonianos y emparejamientos máximos , todo en tiempo lineal. ^[4] Se puede encontrar un ciclo hamiltoniano a partir de una representación de intervalo adecuada del gráfico en el tiempo , ^[13] pero cuando el gráfico en sí se proporciona como entrada, el mismo problema admite una solución en tiempo lineal que se puede generalizar a gráficos de intervalo. ^[21]^[22] $O(n\log n)$

La coloración de listas sigue siendo NP-completa incluso cuando se limita a gráficos de indiferencia. ^[23] Sin embargo, es manejable con parámetros fijos cuando se parametriza por el número total de colores en la entrada. ^[12]

Aplicaciones

En psicología matemática , los gráficos de indiferencia surgen de las funciones de utilidad , al escalar la función de modo que una unidad represente una diferencia en las utilidades lo suficientemente pequeña como para que se pueda suponer que los individuos son indiferentes a ella. En esta aplicación, los pares de elementos cuyas utilidades tienen una gran diferencia pueden ordenarse parcialmente por el orden relativo de sus utilidades, lo que da un semiorden . ^[1]^[24]

En bioinformática , el problema de ampliar un gráfico coloreado a un gráfico de intervalo unitario coloreado adecuadamente se puede utilizar para modelar la detección de falsos negativos en el ensamblaje de secuencias de ADN a partir de digestos completos . ^[25]

Véase también

Gráfico de umbral , un gráfico cuyos bordes están determinados por sumas de etiquetas de vértices en lugar de diferencias de etiquetas.
Gráfico trivialmente perfecto , gráficos de intervalos en los que cada par de intervalos está anidado o disjunto en lugar de intersecarse correctamente.
Gráfico de disco unitario , un análogo bidimensional de los gráficos de indiferencia

Referencias

^ abcdef Roberts, Fred S. (1969), "Gráficos de indiferencia", Técnicas de prueba en teoría de grafos (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Michigan, 1968) , Academic Press, Nueva York, págs. 139-146, MR 0252267.
^ ab Bogart, Kenneth P.; West, Douglas B. (1999), "Una breve prueba de que "propio = unidad"", Matemáticas discretas , 201 (1–3): 21–23, arXiv : math/9811036 , doi :10.1016/S0012-365X(98)00310-0, MR 1687858.
^ Wegner, G. (1967), Eigenschaften der Nerven homologisch-einfacher Familien im R ⁿ , Ph.D. tesis, Göttingen, Alemania: Universidad de GöttingenComo lo citan Hell y Huang (2004).
^ abc Looges, Peter J.; Olariu, Stephan (1993), "Algoritmos voraces óptimos para gráficos de indiferencia", Computers & Mathematics with Applications , 25 (7): 15–25, doi : 10.1016/0898-1221(93)90308-I , MR 1203643.
^ Jackowski, Zygmunt (1992), "Una nueva caracterización de los gráficos de intervalos propios", Discrete Mathematics , 105 (1–3): 103–109, doi : 10.1016/0012-365X(92)90135-3 , MR 1180196.
^ ab Gutierrez, M.; Oubiña, L. (1996), "Caracterizaciones métricas de grafos de intervalos propios y grafos de árbol-clique", Journal of Graph Theory , 21 (2): 199–205, doi :10.1002/(SICI)1097-0118(199602)21:2<199::AID-JGT9>3.0.CO;2-M, MR 1368745.
^ Mertzios, George B. (2008), "Una caracterización matricial de gráficos de intervalos y de intervalos propios", Applied Mathematics Letters , 21 (4): 332–337, doi :10.1016/j.aml.2007.04.001, MR 2406509.
^ ab Brandstädt, Andreas; Hundt, Christian; Mancini, Federico; Wagner, Peter (2010), "Los grafos de trayectorias dirigidas con raíz son potencias de hojas", Discrete Mathematics , 310 : 897–910, doi : 10.1016/j.disc.2009.10.006.
^ Cohen, Joel E. (1982), "La probabilidad asintótica de que un gráfico aleatorio sea un gráfico de intervalo unitario, un gráfico de indiferencia o un gráfico de intervalo propio", Discrete Mathematics , 40 (1): 21–24, doi : 10.1016/0012-365X(82)90184-4 , MR 0676708.
^ Kaplan, Haim; Shamir, Ron (1996), "Problemas de ancho de banda, ancho de ruta y completitud para gráficos de intervalos adecuados con camarillas pequeñas", SIAM Journal on Computing , 25 (3): 540–561, doi :10.1137/S0097539793258143, MR 1390027.
^ Golumbic, Martin Charles ; Rotics, Udi (1999), "El ancho de camarilla de los gráficos de intervalos unitarios no tiene límites", Actas de la 30.ª Conferencia Internacional del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Boca Raton, FL, 1999) , Congressus Numerantium, vol. 140, págs. 5-17, MR 1745205.
^ ab Lozin, Vadim V. (2008), "Del ancho de árbol al ancho de camarilla: excluyendo un gráfico de intervalo unitario", Algorithms and computation , Lecture Notes in Comput. Sci., vol. 5369, Springer, Berlín, págs. 871–882, doi :10.1007/978-3-540-92182-0_76, MR 2539978.
^ ab Bertossi, Alan A. (1983), "Encontrar circuitos hamiltonianos en gráficos de intervalos propios", Information Processing Letters , 17 (2): 97–101, doi :10.1016/0020-0190(83)90078-9, MR 0731128.
^ ab Panda, BS; Das, Sajal K. (2003), "Un algoritmo de reconocimiento de tiempo lineal para gráficos de intervalos adecuados", Information Processing Letters , 87 (3): 153–161, doi :10.1016/S0020-0190(03)00298-9, MR 1986780.
^ von Rimscha, Michael (1983), "Reconstructibilidad y grafos perfectos", Discrete Mathematics , 47 (2–3): 283–291, doi : 10.1016/0012-365X(83)90099-7 , MR 0724667.
^ Bentley, Jon L .; Stanat, Donald F.; Williams, E. Hollins Jr. (1977), "La complejidad de encontrar vecinos cercanos de radio fijo", Information Processing Letters , 6 (6): 209–212, doi :10.1016/0020-0190(77)90070-9, MR 0489084.
^ Corneil, Derek G. ; Kim, Hiryoung; Natarajan, Sridhar; Olariu, Stephan; Sprague, Alan P. (1995), "Reconocimiento lineal simple de tiempo de gráficos de intervalos unitarios", Information Processing Letters , 55 (2): 99–104, CiteSeerX 10.1.1.39.855 , doi :10.1016/0020-0190(95)00046-F, MR 1344787 .
^ Herrera de Figueiredo, Celina M.; Meidanis, João; Picinin de Mello, Célia (1995), "Un algoritmo de tiempo lineal para el reconocimiento adecuado de gráficos de intervalos", Information Processing Letters , 56 (3): 179–184, doi :10.1016/0020-0190(95)00133-W, MR 1365411.
^ Corneil, Derek G. (2004), "Un algoritmo LBFS simple de 3 barridos para el reconocimiento de gráficos de intervalos unitarios", Discrete Applied Mathematics , 138 (3): 371–379, doi : 10.1016/j.dam.2003.07.001 , MR 2049655.
^ Hell, Pavol ; Huang, Jing (2004), "Certificación de algoritmos de reconocimiento LexBFS para gráficos de intervalos propios y bigrafos de intervalos propios", SIAM Journal on Discrete Mathematics , 18 (3): 554–570, doi :10.1137/S0895480103430259, MR 2134416.
^ Keil, J. Mark (1985), "Encontrar circuitos hamiltonianos en gráficos de intervalos", Information Processing Letters , 20 (4): 201–206, doi :10.1016/0020-0190(85)90050-X, MR 0801816.
^ Ibarra, Louis (2009), "Un algoritmo simple para encontrar ciclos hamiltonianos en gráficos de intervalos propios", Information Processing Letters , 109 (18): 1105–1108, doi :10.1016/j.ipl.2009.07.010, MR 2552898.
^ Marx, Dániel (2006), "Extensión de precoloración en gráficos de intervalos unitarios", Discrete Applied Mathematics , 154 (6): 995–1002, doi : 10.1016/j.dam.2005.10.008 , MR 2212549.
^ Roberts, Fred S. (1970), "Sobre la indiferencia no transitiva", Journal of Mathematical Psychology , 7 : 243–258, doi :10.1016/0022-2496(70)90047-7, MR 0258486.
^ Goldberg, Paul W.; Golumbic, Martin C.; Kaplan, Haim; Shamir, Ron (2009), "Cuatro ataques contra el mapeo físico del ADN", Journal of Computational Biology , 2 (2), doi :10.1089/cmb.1995.2.139, PMID 7497116.

Enlaces externos

Sistema de información sobre inclusiones de clases de grafos: grafo de intervalo unitario