Gráfico de indiferencia

En la 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 mediante una arista cuando sus números están dentro de una unidad de diferencia entre sí. ^{[ 1 ]} Un grafo de indiferencia es también el grafo de intersección de un conjunto de intervalos unitarios , o de intervalos anidados propiamente (intervalos que no contienen a ningún otro). Basándose en estos dos tipos de representaciones de intervalos, estos grafos también se denominan grafos de intervalos unitarios ^{[ 2 ]} o grafos de intervalos propios ; forman una subclase de los grafos de intervalos .

Un grafo de indiferencia finito puede caracterizarse de forma equivalente como:

• El grafo de intersección de un conjunto de intervalos unitarios . ^{[ 1 ]}
• El grafo de intersección de un conjunto de intervalos de la misma longitud. ^{[ 2 ]}
• El grafo de intersección de un conjunto de intervalos, ninguno de los cuales está anidado (uno contiene al otro). ^{[ 1 ] [ 3 ]}
• Un gráfico de intervalos sin garras . ^{[ 1 ] [ 3 ]}
• Un grafo que no tiene un subgrafo inducido isomorfo a una garra${\displaystyle 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). ^{[ 4 ]}
• Un grafo de incomparabilidad de semiorden . ^{[ 1 ]}
• Un grafo no dirigido que tiene un orden lineal tal que, para cada tres vértices ordenados${\displaystyle u}$–${\displaystyle v}$–${\displaystyle w}$, si${\displaystyle uw}$es una ventaja entonces también lo son${\displaystyle uv}$y${\displaystyle vw}$. ^{[ 5 ]}
• Un grafo sin triplete astral , tres vértices conectados de dos en dos por caminos que evitan el tercer vértice y que tampoco contienen dos vecinos consecutivos del tercer vértice. ^{[ 6 ]}
• Un grafo en el que cada componente conexo contiene un camino en el que cada camarilla máxima del componente forma un subcamino contiguo. ^{[ 7 ]}
• Un grafo cuyos vértices pueden numerarse de tal manera que cada camino más corto forma una secuencia monótona . ^{[ 7 ]}
• Un grafo cuya matriz de adyacencia se puede ordenar de tal manera que, en cada fila y cada columna, los elementos no nulos de la matriz forman un intervalo contiguo adyacente a la diagonal principal de la matriz. ^{[ 8 ]}
• Un subgrafo inducido de una potencia de un camino sin cuerdas. ^{[ 9 ]}
• Un poder de hoja que tiene una raíz de hoja que es una oruga. ^{[ 9 ]}

En el caso de un grafo infinito, algunas de estas definiciones pueden diferir.

Debido a que es un caso especial de un grafo de intervalos , un grafo de indiferencia posee todas las propiedades de un grafo de intervalos; en particular, es un caso especial de un grafo cordal y de un grafo perfecto . También es un caso especial de un grafo circular , algo que no es cierto para un grafo de intervalos en general.

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

El ancho de banda de un gráfico arbitrario${\displaystyle G}$es${\displaystyle 1}$menor que el tamaño de la camarilla máxima en un gráfico de indiferencia que contiene${\displaystyle G}$como un subgrafo y se elige para minimizar el tamaño de la clique máxima. ^{[ 11 ]} Esta propiedad es paralela a relaciones similares entre el ancho de camino y los grafos de intervalo , y entre el ancho de árbol y los grafos cordales . Una noción más débil de ancho, el ancho de clique , puede ser arbitrariamente grande en los grafos de indiferencia. ^{[ 12 ]} Sin embargo, cualquier subclase propia (es decir, estrictamente más pequeña) de grafos de indiferencia que sea cerrada bajo subgrafos inducidos tiene una cota superior en el ancho de clique de sus grafos. ^{[ 13 ]}

Un grafo de indiferencia conexo tiene un camino hamiltoniano . ^{[ 14 ]} Un grafo de indiferencia tiene un ciclo hamiltoniano si y solo si es biconexo . ^{[ 15 ]}

Un grafo de indiferencia obedece la conjetura de reconstrucción : está determinado unívocamente por sus subgrafos sin vértices. ^{[ 16 ]}

Al igual que con los grafos de disco unitario de dimensiones superiores , es posible transformar un conjunto de puntos en su grafo de indiferencia, o un conjunto de intervalos unitarios en su grafo de intervalo unitario, en tiempo lineal medido en términos del tamaño del grafo de salida. El algoritmo redondea los puntos (o centros de intervalo) al entero menor más cercano, utiliza una tabla hash para encontrar todos los pares de puntos cuyos enteros redondeados están dentro de${\displaystyle 1}$de entre sí (el problema de los vecinos cercanos de radio fijo ), y filtra la lista resultante de pares para aquellos cuyos valores sin redondear también están dentro${\displaystyle 1}$del otro. ^{[ 17 ]}

Es posible comprobar si un grafo dado es un grafo de indiferencia en tiempo lineal, utilizando árboles PQ para construir una representación de intervalos del grafo y luego comprobando si un ordenamiento de vértices derivado de esta representación satisface las propiedades de un grafo de indiferencia. ^{[ 5 ]} También es posible basar un algoritmo de reconocimiento para grafos de indiferencia en algoritmos de reconocimiento de grafos cordales . ^{[ 15 ]} Varios algoritmos alternativos de reconocimiento en tiempo lineal se basan en la búsqueda en anchura o la búsqueda en anchura lexicográfica en lugar de en la relación entre grafos de indiferencia y grafos de intervalos. ^{[ 18 ] [ 19 ] [ 20 ] [ 21 ]}

Una vez que los vértices se han ordenado según los valores numéricos que describen un grafo de indiferencia (o según la secuencia de intervalos unitarios en una representación de intervalos), se puede utilizar el mismo ordenamiento para encontrar una coloración óptima para estos grafos, resolver el problema del camino más corto y construir caminos hamiltonianos y emparejamientos máximos , todo en tiempo lineal. ^{[ 5 ]} Se puede encontrar un ciclo hamiltoniano a partir de una representación de intervalos adecuada del grafo en tiempo${\displaystyle O(n\log n)}$, ^{[ 14 ]} pero cuando se proporciona el propio grafo como entrada, el mismo problema admite una solución de tiempo lineal que puede generalizarse a grafos de intervalos. ^{[ 22 ] [ 23 ]}

La coloración de listas sigue siendo NP-completa incluso cuando se restringe a grafos de indiferencia. ^{[ 24 ]} Sin embargo, es tratable con parámetros fijos cuando se parametriza por el número total de colores en la entrada. ^{[ 13 ]}

En psicología matemática , los gráficos de indiferencia surgen de las funciones de utilidad , escalando la función de manera 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 según el orden relativo de sus utilidades, dando lugar a un semiorden . ^{[ 1 ] [ 25 ]}

En bioinformática , el problema de aumentar un gráfico coloreado a un gráfico de intervalo unitario coloreado correctamente se puede utilizar para modelar la detección de falsos negativos en el ensamblaje de secuencias de ADN a partir de digestiones completas . ^{[ 26 ]}

• Grafos umbral , grafos 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 propiamente.
• Gráficos de discos unitarios , análogos bidimensionales de los gráficos de indiferencia.

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