Gráfico de indiferencia

Un gráfico de indiferencia, formado a partir de un conjunto de puntos en la línea real conectando pares de puntos cuya distancia es como máximo uno.

En la teoría de grafos , una rama de las matemáticas, un gráfico de indiferencia es un gráfico no dirigido que se construye asignando un número real a cada vértice y conectando dos vértices por un borde cuando sus números están dentro de una unidad entre sí. ^[1] Los gráficos de indiferencia son también los gráficos de intersección de conjuntos de intervalos unitarios , o de intervalos correctamente anidados (intervalos ninguno de los cuales contiene otro). Con base en estos dos tipos de representaciones de intervalo, estas gráficas también se denominan gráficas de intervalo unitario o gráficas de intervalo adecuado ; forman una subclase de los gráficos de intervalo .

Caracterizaciones equivalentes

Subgrafos inducidos prohibidos para los gráficos de indiferencia: la garra, el sol y la red (arriba, izquierda-derecha) y ciclos de cuatro o más de longitud (abajo)

Los gráficos de indiferencia finita se pueden caracterizar de manera equivalente como

• Los gráficos de intersección de intervalos unitarios , ^[1]
• Los gráficos de intersección de conjuntos de intervalos de los cuales no hay dos anidados (uno que contiene al otro), ^{[1] [2]}
• Los gráficos de intervalo sin garras , ^{[1] [2]}
• Los gráficos que no tienen un subgrafo inducido isomorfo a una garra K _1,3 , neto (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 uno borde con el triángulo central), o agujero (ciclo de longitud cuatro o más), ^[3]
• Los gráficos de incomparabilidad de los semiordenadores , ^[1]
• Los gráficos 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]${\displaystyle u}$${\displaystyle v}$${\displaystyle w}$${\displaystyle uw}$${\displaystyle uv}$${\displaystyle vw}$
• Las gráficas sin triple astral , tres vértices conectados por pares por caminos que evitan el tercer vértice y tampoco contienen dos vecinos consecutivos del tercer vértice, ^[5]
• Los gráficos en los que cada componente conectado contiene una ruta en la que cada camarilla máxima del componente forma una subruta contigua, ^[6]
• Los gráficos cuyos vértices se pueden numerar de tal manera que cada camino más corto forma una secuencia monótona , ^[6]
• Las gráficas cuyas matrices de adyacencia se pueden ordenar de manera que, en cada fila y cada columna, los no ceros de la matriz formen un intervalo contiguo adyacente a la diagonal principal de la matriz. ^[7]
• Los subgrafos inducidos de poderes de caminos sin cuerda. ^[8]
• Los poderes de la hoja tienen una raíz de hoja que es una oruga. ^[8]

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

Propiedades

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

En el modelo Erdős-Rényi de gráficos aleatorios , un gráfico -vertex cuyo número de aristas es significativamente menor que será un gráfico de indiferencia con alta probabilidad, mientras que un gráfico cuyo número de aristas sea significativamente mayor que no será un gráfico de indiferencia con alta probabilidad. ^[9]${\displaystyle n}$${\displaystyle n^{2/3}}$${\displaystyle n^{2/3}}$

El ancho de banda de un gráfico arbitrario es uno menos que el tamaño de la camarilla máxima en un gráfico de indiferencia que contiene como subgráfico y se elige para minimizar el tamaño de la camarilla máxima. ^[10] Esta propiedad es paralela a relaciones similares 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, el ancho de la camarilla , puede ser arbitrariamente grande en los gráficos de indiferencia. ^[11] Sin embargo, cada subclase propia de los gráficos de indiferencia que se cierra bajo los subgrafos inducidos tiene un ancho de camarilla limitado. ^[12]${\displaystyle G}$${\displaystyle G}$

Cada gráfico de indiferencia conectado tiene un camino hamiltoniano . ^[13] Un gráfico de indiferencia tiene un ciclo hamiltoniano si y solo si está biconectado . ^[14]

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

Algoritmos

Al igual que con los gráficos de disco unitarios de mayor dimensión , 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, usa una tabla hash para encontrar todos los pares de puntos cuyos enteros redondeados están dentro de cada uno (el problema de los vecinos cercanos de radio fijo ) y filtra el resultado lista de pares para aquellos cuyos valores no redondeados también están entre sí. ^[dieciséis]

Es posible probar 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 probar si un orden de vértice 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 primero o en la búsqueda lexicográfica en amplitud 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 usar el mismo orden para encontrar un color de gráfico óptimo para estos gráficos, para resolver el problema de la ruta más corta. y 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 de la gráfica en el tiempo , ^[13] pero cuando la gráfica en sí se da como entrada, el mismo problema admite una solución de tiempo lineal que puede generalizarse a gráficas de intervalo. ^{[21] [22]}${\displaystyle O(n\log n)}$

La coloración de la lista sigue siendo NP-completa incluso cuando se restringe a gráficos de indiferencia. ^[23] Sin embargo, es tratable 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 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, dando un semiorden . ^{[1] [24]}

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

Ver también

• Gráfico de umbral , un gráfico cuyos bordes están determinados por sumas de etiquetas de vértice en lugar de diferencias de etiquetas
• Gráfico trivialmente perfecto , gráficos de intervalo para los que cada par de intervalos está anidado o disjunto en lugar de intersecarse correctamente

Referencias

1. Roberts, Fred S. (1969), "Gráficos de indiferencia", Técnicas de prueba en teoría de grafos (Proc. Segunda Conf. Teoría de Grafos de Ann Arbor, Ann Arbor, Michigan, 1968) , Academic Press, Nuevo York, págs. 139-146, MR  0252267.
2. Bogart, Kenneth P .; West, Douglas B. (1999), "Una prueba breve de que" apropiado = unidad " ", Matemáticas discretas , 201 (1-3): 21-23, arXiv : math / 9811036 , doi : 10.1016 / S0012-365X (98 ) 00310-0 , MR 1687858 .
3. Wegner, G. (1967), Eigenschaften der Nerven homologisch-einfacher Familien im R ⁿ , Ph.D. tesis, Göttingen, Alemania: Universidad de Göttingen. Según lo citado por Hell & Huang (2004) .
4. Looges, Peter J .; Olariu, Stephan (1993), "Óptimos algoritmos codiciosos para gráficos de indiferencia", Computers & Mathematics with Applications , 25 (7): 15-25, doi : 10.1016 / 0898-1221 (93) 90308-I , MR 1203643 .
5. Jackowski, Zygmunt (1992), "Una nueva caracterización de los gráficos de intervalo adecuados", Matemáticas discretas , 105 (1-3): 103-109, doi : 10.1016 / 0012-365X (92) 90135-3 , MR 1180196 .
6. Gutiérrez, M .; Oubiña, L. (1996), "Caracterizaciones métricas de gráficos de intervalos adecuados y gráficos de grupos de árboles", 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 .
7. Mertzios, George B. (2008), "Una caracterización matricial de intervalos y gráficos de intervalo adecuado", Letras de matemáticas aplicadas , 21 (4): 332–337, doi : 10.1016 / j.aml.2007.04.001 , MR 2406509 .
8. Brandstädt, Andreas; Hundt, Christian; Mancini, Federico; Wagner, Peter (2010), "Los gráficos de trayectoria dirigidos con raíces son poderes de hoja", Matemáticas discretas , 310 : 897–910, doi : 10.1016 / j.disc.2009.10.006.
9. 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 adecuado", Matemáticas discretas , 40 (1): 21-24, doi : 10.1016 / 0012 -365X (82) 90184-4 , MR 0676708 .
10. Kaplan, Haim; Shamir, Ron (1996), "Problemas de ancho de ruta, ancho de banda y finalización para gráficos de intervalo adecuados con pequeños grupos", SIAM Journal on Computing , 25 (3): 540–561, doi : 10.1137 / S0097539793258143 , MR 1390027 .
11. Golumbic, Martin Charles ; Rotics, Udi (1999), "El ancho de la camarilla de los gráficos de intervalo unitario es ilimitado", Actas de la trigésima Conferencia Internacional del Sureste sobre Combinatoria, Teoría de Grafos y Computación (Boca Raton, FL, 1999) , Congressus Numerantium, 140 , págs. 5–17, MR 1745205 .
12. Lozin, Vadim V. (2008), "Desde el ancho del árbol al ancho de la camarilla: excluyendo un gráfico de intervalo unitario", Algoritmos y cálculo , Notas de clase en Computación. Sci., 5369 , Springer, Berlín, págs. 871–882, doi : 10.1007 / 978-3-540-92182-0_76 , MR 2539978 .
13. Bertossi, Alan A. (1983), "Encontrar circuitos hamiltonianos en gráficos de intervalo adecuados", Cartas de procesamiento de información , 17 (2): 97-101, doi : 10.1016 / 0020-0190 (83) 90078-9 , MR 0731128 .
14. 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 .
15. von Rimscha, Michael (1983), "Reconstructibilidad y gráficos perfectos", Matemáticas discretas , 47 (2-3): 283-291, doi : 10.1016 / 0012-365X (83) 90099-7 , MR 0724667 .
16. 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 .
17. Corneil, Derek G .; Kim, Hiryoung; Natarajan, Sridhar; Olariu, Stephan; Sprague, Alan P. (1995), "Reconocimiento de tiempo lineal simple 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  .
18. Herrera de Figueiredo, Celina M .; Meidanis, João; Picinin de Mello, Célia (1995), "Un algoritmo de tiempo lineal para el reconocimiento de gráficos de intervalo adecuado", Information Processing Letters , 56 (3): 179–184, doi : 10.1016 / 0020-0190 (95) 00133-W , MR 1365411 .
19. Corneil, Derek G. (2004), "Un algoritmo LBFS simple de 3 barridos para el reconocimiento de gráficos de intervalos unitarios", Matemáticas aplicadas discretas , 138 (3): 371-379, doi : 10.1016 / j.dam.2003.07. 001 , MR 2049655 .
20. Infierno, Pavol ; Huang, Jing (2004), "Certificación de algoritmos de reconocimiento LexBFS para gráficos de intervalo adecuados y bigrafos de intervalo adecuados", SIAM Journal on Discrete Mathematics , 18 (3): 554–570, doi : 10.1137 / S0895480103430259 , MR 2134416 .
21. Keil, J. Mark (1985), "Encontrar circuitos hamiltonianos en gráficos de intervalo", Cartas de procesamiento de información , 20 (4): 201-206, doi : 10.1016 / 0020-0190 (85) 90050-X , MR 0801816 .
22. Ibarra, Louis (2009), "Un algoritmo simple para encontrar ciclos hamiltonianos en gráficos de intervalo adecuados", Cartas de procesamiento de información , 109 (18): 1105-1108, doi : 10.1016 / j.ipl.2009.07.010 , MR 2552898 .
23. Marx, Dániel (2006), "Extensión de precoloración en gráficos de intervalo unitario", Matemáticas aplicadas discretas , 154 (6): 995-1002, doi : 10.1016 / j.dam.2005.10.008 , MR 2212549 .
24. 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 .
25. 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 gráficos : gráfico de intervalo unitario