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
- Gráficas de intersecciones de segmentos unitarios [1]
- Gráficos de intersección de conjuntos de intervalos, ninguno de los cuales está anidado [1] [2]
- Gráficos de intervalos sin garras [1] [2]
- Gráficos que no contienen subgrafos generados isomorfos a una garra K 1,3 , una "red" (un triángulo con tres vértices adicionales adjuntos a cada vértice del triángulo), un "sol" (un triángulo con tres triángulos adjuntos que comparten bordes con el triángulo central), o "agujeros" (ciclos de longitud de cuatro o más) [3]
- Gráficas de incomparabilidad de semiórdenes [1]
- Grafos no dirigidos que tienen un orden lineal , tal que para cada camino de tres vértices , cuyos vértices están ordenados - - , terminan los vértices y son adyacentes [4]
- Gráficos que no tienen triples astrales , tres vértices conectados en pares por caminos que no pasan por el tercer vértice, y tampoco contienen dos vértices adyacentes que son simultáneamente adyacentes a un vértice de la vecindad del tercer vértice [5] .
- Gráficos en los que cada componente contiene un camino en el que cada componente clique forma un subcamino continuo [6]
- Gráficos cuyos vértices se pueden numerar de tal manera que cualquier camino más corto forme una secuencia monótona [6]
- Gráficos cuyas matrices de adyacencia se pueden ordenar de tal manera que los elementos distintos de cero en cada fila y cada columna formen intervalos continuos adyacentes a las diagonales de la matriz [7]
- Subgrafos generados de grados de trayectorias sin cuerdas [8]
- Grados de hojas que tienen una raíz de hoja en forma de oruga [8]
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
- 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áficos trivialmente perfectos , gráficos de intervalos en los que cada par de intervalos está anidado o disjunto en lugar de intersecarse adecuadamente
Notas
- ↑ 1 2 3 4 5 6 Roberts, 1969 , pág. 139–146.
- ↑ 1 2 Bogart, West, 1999 , pág. 21–23.
- ↑ Wegner, 1967 .
- ↑ 1 2 3 Looges, Olariu, 1993 , p. 15–25.
- ↑ Jackowski, 1992 , pág. 103–109.
- ↑ 1 2 Gutiérrez, Oubina, 1996 , p. 199–205.
- ↑ Mertzios, 2008 , pág. 332–337.
- ↑ 1 2 Brandstädt, Hundt, Mancini, Wagner, 2010 , p. 897–910.
- ↑ Cohen, 1982 , pág. 21–24.
- ↑ Kaplan, Shamir, 1996 , pág. 540–561.
- ↑ Golumbic, Rotics, 1999 , p. 5–17.
- ↑ 1 2 Lozin, 2008 , pág. 871–882.
- ↑ 1 2 Bertossi, 1983 , p. 97–101.
- ↑ 1 2 Panda, Das, 2003 , p. 153–161.
- ↑ von Rimscha, 1983 , p. 283–291.
- ↑ Bentley, Stanat, Williams, 1977 , pág. 209–212.
- ↑ Corneil, Kim, Natarajan, Olariu, Sprague, 1995 , pág. 99–104.
- ↑ Herrera de Figueiredo, Meidanis, Picinin de Mello, 1995 , p. 179–184.
- ↑ Corneil, 2004 , pág. 371–379.
- ↑ Infierno, Huang, 2004 , p. 554–570.
- ↑ Keil, 1985 , pág. 201–206.
- ↑ Ibarra, 2009 , pág. 1105–1108.
- ↑ Marx, 2006 , pág. 995–1002.
- ↑ Roberts, 1970 , pág. 243–258.
- ↑ Goldberg, Golumbic, Kaplan, Shamir, 2009 .
Literatura
- Fred S. Roberts. Gráficos de indiferencia // Técnicas de prueba en teoría de gráficos (Proc. Second Ann Arbor Graph Theory Conf., Ann Arbor, Mich., 1968). - Academic Press, Nueva York, 1969. - S. 139-146.
- Kenneth P. Bogart, Douglas B. West. Una breve prueba de que "proper=unit" // Matemáticas discretas . - 1999. - T. 201 , nº. 1-3 . — P. 21–23 . - doi : 10.1016/S0012-365X(98)00310-0 .
- Wegner G. Eigenschaften der Nerven homologisch-einfacher Familien im R n . - Göttingen, Alemania: Universidad de Göttingen, 1967. - (Tesis doctoral). . Como se cita en Plantilla:Harnb
- Peter J. Looges, Stephan Olariu. Algoritmos codiciosos óptimos para gráficos de indiferencia // Informática y Matemáticas con Aplicaciones. - 1993. - T. 25 , núm. 7 . — P. 15–25 . - doi : 10.1016/0898-1221(93)90308-I .
- Zygmunt Jackowski. Una nueva caracterización de grafos de intervalos propios // Matemáticas discretas . - 1992. - T. 105 , núm. 1-3 . — S. 103–109 . - doi : 10.1016/0012-365X(92)90135-3 .
- Gutierrez M., Oubiña L. Caracterizaciones métricas de gráficos de intervalos propios y gráficos de clique de árbol // Journal of Graph Theory. - 1996. - T. 21 , núm. 2 . — S. 199–205 . -doi : 10.1002 / (SICI)1097-0118(199602)21:2<199::AID-JGT9>3.0.CO;2-M .
- George B. Mertzios. Una caracterización matricial de gráficos de intervalos e intervalos propios // Letras de Matemáticas Aplicadas. - 2008. - T. 21 , núm. 4 . — S. 332–337 . -doi : 10.1016/ j.aml.2007.04.001 .
- Andreas Brandstädt, Christian Hundt, Federico Mancini, Peter Wagner. Los gráficos de ruta dirigida enraizados son potencias de hoja // Matemáticas discretas. - 2010. - T. 310 . — S. 897–910 . -doi : 10.1016/ j.disco.2009.10.006 .
- Joel E Cohen. 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 // Matemáticas discretas . - 1982. - T. 40 , núm. 1 . — P. 21–24 . - doi : 10.1016/0012-365X(82)90184-4 .
- Haim Kaplan, Ron Shamir. Problemas de ancho de ruta, ancho de banda y finalización para gráficos de intervalos adecuados con pequeñas camarillas // SIAM Journal on Computing. - 1996. - T. 25 , núm. 3 . — S. 540–561 . -doi : 10.1137/ S0097539793258143 .
- Martín Charles Golumbic, Udi Rotics. El ancho de camarilla de los gráficos de intervalo unitario es ilimitado // Actas de la Trigésima Conferencia Internacional del Sureste sobre Combinatoria, Teoría de Gráficos y Computación (Boca Raton, FL, 1999). - 1999. - T. 140. - S. 5–17. — (Congressus Numerantium).
- Vadim V. Lozin. Del ancho del árbol al ancho de la camarilla: excluyendo un gráfico de intervalo unitario // Algoritmos y computación. - Springer, Berlín, 2008. - T. 5369. - S. 871-882. - (Apuntes de conferencias en Informática. Sci.). -doi : 10.1007 / 978-3-540-92182-0_76 .
- Alan A. Bertossi. Encontrar circuitos hamiltonianos en gráficos de intervalos propios // Cartas de procesamiento de información. - 1983. - T. 17 , núm. 2 . — S. 97–101 . - doi : 10.1016/0020-0190(83)90078-9 .
- Panda BS, Das SK Un algoritmo de reconocimiento de tiempo lineal para gráficos de intervalos adecuados // Cartas de procesamiento de información. - 2003. - T. 87 , núm. 3 . — S. 153–161 . - doi : 10.1016/S0020-0190(03)00298-9 .
- Michael von Rimscha. Reconstructibilidad y grafos perfectos // Matemática Discreta. - 1983. - T. 47 , núm. 2-3 . — S. 283–291 . - doi : 10.1016/0012-365X(83)90099-7 .
- Jon L. Bentley, Donald F. Stanat, E. Hollins Williams, Jr. La complejidad de encontrar vecinos cercanos de radio fijo // Cartas de procesamiento de información . - 1977. - T. 6 , núm. 6 _ — S. 209–212 . - doi : 10.1016/0020-0190(77)90070-9 .
- Derek G. Corneil, Hiryoung Kim, Sridhar Natarajan, Stephan Olariu, Alan P. Sprague. Reconocimiento de tiempo lineal simple de gráficos de intervalos unitarios // Cartas de procesamiento de información. - 1995. - T. 55 , núm. 2 . — S. 99–104 . -doi : 10.1016 / 0020-0190(95)00046-F .
- Celina M. Herrera de Figueiredo, João Meidanis, Célia Picinin de Mello. Un algoritmo de tiempo lineal para el reconocimiento adecuado de gráficos de intervalos // Cartas de procesamiento de información. - 1995. - T. 56 , núm. 3 . — S. 179–184 . - doi : 10.1016/0020-0190(95)00133-W .
- Derek G. Corneil. Un algoritmo LBFS simple de 3 barridos para el reconocimiento de gráficos de intervalos unitarios // Matemáticas aplicadas discretas. - 2004. - T. 138 , núm. 3 . — S. 371–379 . -doi : 10.1016/ j.dam.2003.07.001 .
- Infierno Pavol, Jing Huang. Certificación de algoritmos de reconocimiento LexBFS para gráficos de intervalos adecuados y bígrafos de intervalos adecuados // SIAM Journal on Discrete Mathematics . - 2004. - T. 18 , núm. 3 . — S. 554–570 . -doi : 10.1137/ S0895480103430259 .
- J. Mark Keil. Encontrar circuitos hamiltonianos en gráficos de intervalo // Cartas de procesamiento de información. - 1985. - T. 20 , núm. 4 . — S. 201–206 . -doi : 10.1016 / 0020-0190(85)90050-X .
- Luis Ibarra. Un algoritmo simple para encontrar ciclos hamiltonianos en gráficos de intervalos adecuados // Cartas de procesamiento de información. - 2009. - T. 109 , núm. 18 _ — S. 1105–1108 . -doi : 10.1016/ j.ipl.2009.07.010 .
- daniel marx. Extensión de precoloreado en gráficos de intervalos unitarios // Matemáticas aplicadas discretas. - 2006. - T. 154 , núm. 6 _ — S. 995–1002 . -doi : 10.1016/ j.dam.2005.10.008 .
- Fred S. Roberts. Sobre la indiferencia no transitiva // Journal of Mathematical Psychology. - 1970. - T. 7 . — S. 243–258 . - doi : 10.1016/0022-2496(70)90047-7 .
- Paul W. Goldberg, Martin C. Golumbic, Haim Kaplan, Ron Shamir. Cuatro golpes contra el mapeo físico del ADN // Journal of Computational Biology. - 2009. - Vol. 2 , número. 2 . -doi : 10.1089/ cmb.1995.2.139 . —PMID 7497116 .
Enlaces