En teoría de grafos , una división de las matemáticas , un gráfico de mediana es un gráfico no dirigido en el que cada tres vértices a , b y c tienen una mediana única : un vértice m ( a , b , c ) que pertenece a los caminos más cortos entre cada par. de a , b y c .
El concepto de gráficos de medianas ha sido estudiado durante mucho tiempo, por ejemplo por Birkhoff y Kiss (1947) o (más explícitamente) por Avann (1961), pero el primer artículo en llamarlos "gráficos de medianas" parece ser Nebeský (1971). Como escriben Chung , Graham y Saks, "los gráficos de medianas surgen de forma natural en el estudio de conjuntos ordenados y redes distributivas discretas , y cuentan con una extensa literatura". [1] En filogenética , el gráfico de Buneman que representa todos los árboles evolutivos de máxima parsimonia es un gráfico de mediana. [2] Los gráficos de mediana también surgen en la teoría de la elección social : si un conjunto de alternativas tiene la estructura de un gráfico de mediana, es posible derivar de manera inequívoca una preferencia mayoritaria entre ellas. [3]
Klavžar & Mulder (1999), Bandelt & Chepoi (2008) y Knuth (2008) ofrecen estudios adicionales de gráficos de medianas.
Cada árbol es un gráfico mediano. Para ver esto, observe que en un árbol, la unión de los tres caminos más cortos entre pares de los tres vértices a , b y c es en sí mismo un camino o un subárbol formado por tres caminos que se encuentran en un solo nodo central con grado tres. Si la unión de los tres caminos es en sí misma un camino, la mediana m ( a , b , c ) es igual a uno de a , b o c , cualquiera de estos tres vértices que esté entre los otros dos del camino. Si el subárbol formado por la unión de los tres caminos no es un camino, la mediana de los tres vértices es el nodo central de grado tres del subárbol. [4]
Los gráficos de cuadrícula proporcionan ejemplos adicionales de gráficos de mediana . En un gráfico de cuadrícula, las coordenadas de la mediana m ( a , b , c ) se pueden encontrar como la mediana de las coordenadas de a , b y c . A la inversa, resulta que, en todo gráfico de medianas, se pueden etiquetar los vértices mediante puntos en una red de números enteros de tal manera que las medianas se puedan calcular en coordenadas de esta manera. [5]
Los gráficos cuadrados , gráficos planos en los que todas las caras interiores son cuadriláteros y todos los vértices interiores tienen cuatro o más aristas incidentes, son otra subclase de los gráficos medianos. [6] Un poliominó es un caso especial de gráfico cuadrado y, por lo tanto, también forma un gráfico de mediana. [7]
El gráfico simplex κ( G ) de un gráfico arbitrario no dirigido G tiene un vértice para cada camarilla (subgrafo completo) de G ; dos vértices de κ( G ) están unidos por una arista si las camarillas correspondientes difieren en un vértice de G . El gráfico simplex es siempre un gráfico de mediana, en el que la mediana de un triple dado de camarillas se puede formar utilizando la regla de la mayoría para determinar qué vértices de las camarillas incluir. [8]
Ningún gráfico de ciclo de longitud distinta de cuatro puede ser un gráfico de mediana. Cada uno de estos ciclos tiene tres vértices a , b y c, de modo que los tres caminos más cortos rodean todo el ciclo sin tener una intersección común. Para tal triplete de vértices, no puede haber mediana.
En un gráfico arbitrario, para cada dos vértices a y b , el número mínimo de aristas entre ellos se llama distancia , denotada por d ( x , y ). El intervalo de vértices que se encuentran en los caminos más cortos entre a y b se define como
Un gráfico de mediana se define por la propiedad de que, por cada tres vértices a , b y c , estos intervalos se cruzan en un solo punto:
De manera equivalente, por cada tres vértices a , b y c se puede encontrar un vértice m ( a , b , c ) tal que las distancias no ponderadas en el gráfico satisfagan las igualdades.
y m ( a , b , c ) es el único vértice para el cual esto es cierto.
También es posible definir gráficas de medianas como conjuntos de soluciones de problemas de 2-satisfacibilidad , como retracciones de hipercubos , como gráficas de álgebras de medianas finitas , como gráficas de Buneman de sistemas divididos de Helly y como gráficas de windex 2; consulte las secciones siguientes.
En teoría de la red , la gráfica de una red finita tiene un vértice para cada elemento de la red y una arista para cada par de elementos en la relación de cobertura de la red. Las celosías se presentan comúnmente visualmente mediante diagramas de Hasse , que son dibujos de gráficos de celosías. Estas gráficas, especialmente en el caso de redes distributivas , resultan estar estrechamente relacionadas con las gráficas de medianas.
En una red distributiva, la operación mediana ternaria autodual de Birkhoff [9]
satisface ciertos axiomas clave, que comparte con la mediana habitual de números en el rango de 0 a 1 y con álgebras de medianas en general:
La ley distributiva podrá ser sustituida por una ley asociativa: [10]
La operación mediana también se puede utilizar para definir una noción de intervalos para redes distributivas:
La gráfica de una red distributiva finita tiene una arista entre los vértices a y b siempre que I ( a , b ) = { a , b }. Para cada dos vértices a y b de este gráfico, el intervalo I ( a , b ) definido en términos de teoría de celosía anteriormente consiste en los vértices en los caminos más cortos de a a b y, por lo tanto, coincide con los intervalos de teoría de grafos definidos anteriormente. Por cada tres elementos de la red a , b y c , m ( a , b , c ) es la intersección única de los tres intervalos I ( a , b ), I ( a , c ) e I ( b , c ) . [12] Por lo tanto, la gráfica de una red distributiva finita arbitraria es una gráfica mediana. Por el contrario, si un gráfico mediano G contiene dos vértices 0 y 1 tales que cada dos vértices se encuentra en el camino más corto entre los dos (de manera equivalente, m (0, a , 1) = a para todo a ), entonces podemos definir una gráfica distributiva celosía en la que a ∧ b = m ( a ,0, b ) y a ∨ b = m ( a ,1, b ), y G será la gráfica de esta celosía. [13]
Duffus y Rival (1983) caracterizan los gráficos de redes distributivas directamente como retracciones de hipercubos que preservan el diámetro. De manera más general, cada gráfico mediano da lugar a una operación ternaria m que satisface idempotencia, conmutatividad y distributividad, pero posiblemente sin los elementos de identidad de una red distributiva. Toda operación ternaria sobre un conjunto finito que satisface estas tres propiedades (pero que no necesariamente tiene 0 y 1 elementos) da lugar de la misma manera a una gráfica mediana. [14]
En un gráfico de mediana, se dice que un conjunto S de vértices es convexo si, por cada dos vértices a y b pertenecientes a S , todo el intervalo I ( a , b ) es un subconjunto de S. De manera equivalente, dadas las dos definiciones de intervalos anteriores, S es convexo si contiene todos los caminos más cortos entre dos de sus vértices, o si contiene la mediana de cada conjunto de tres puntos de los cuales al menos dos son de S. Observe que la intersección de cada par de conjuntos convexos es en sí misma convexa. [15]
Los conjuntos convexos en un gráfico mediano tienen la propiedad de Helly : si F es una familia arbitraria de conjuntos convexos que se cruzan por pares, entonces todos los conjuntos en F tienen una intersección común. [16] Porque, si F tiene solo tres conjuntos convexos S , T y U , con a en la intersección del par S y T , b en la intersección del par T y U , y c en la intersección de el par S y U , entonces cada camino más corto de a a b debe estar dentro de T por convexidad, y de manera similar cada camino más corto entre los otros dos pares de vértices debe estar dentro de los otros dos conjuntos; pero m ( a , b , c ) pertenece a caminos entre los tres pares de vértices, por lo que se encuentra dentro de los tres conjuntos y forma parte de su intersección común. Si F tiene más de tres conjuntos convexos, el resultado se obtiene por inducción del número de conjuntos, ya que se puede reemplazar un par arbitrario de conjuntos en F por su intersección, usando el resultado de triples de conjuntos para mostrar que la familia reemplazada todavía se cruza por pares.
Una familia particularmente importante de conjuntos convexos en un gráfico mediano, que desempeña un papel similar al de los semiespacios en el espacio euclidiano, son los conjuntos.
definido para cada borde uv del gráfico. En palabras, W uv consta de los vértices más cercanos a u que a v , o de manera equivalente, los vértices w tales que algún camino más corto de v a w pasa por u . Para demostrar que W uv es convexo, sea w 1 w 2 ... w k un camino arbitrario más corto que comienza y termina dentro de W uv ; entonces w 2 también debe estar dentro de W uv , porque de lo contrario los dos puntos m 1 = m ( u , w 1 , w k ) y m 2 = m ( m 1 , w 2 ... w k ) podrían mostrarse (mediante considerando las posibles distancias entre los vértices) como medianas distintas de u , w 1 y w k , contradiciendo la definición de un gráfico de medianas que requiere que las medianas sean únicas. Por lo tanto, cada vértice sucesivo en un camino más corto entre dos vértices de W uv también se encuentra dentro de W uv , por lo que W uv contiene todos los caminos más cortos entre sus nodos, una de las definiciones de convexidad.
La propiedad de Helly para los conjuntos W uv juega un papel clave en la caracterización de gráficas de medianas como la solución de instancias de 2-satisfacibilidad, a continuación.
Los gráficos de medianas tienen una estrecha conexión con los conjuntos de soluciones de problemas de 2-satisfacibilidad que pueden usarse tanto para caracterizar estos gráficos como para relacionarlos con mapas de hipercubos que preservan la adyacencia. [17]
Una instancia de 2-satisfacibilidad consta de una colección de variables booleanas y una colección de cláusulas , restricciones sobre ciertos pares de variables que requieren que esas dos variables eviten ciertas combinaciones de valores. Por lo general, estos problemas se expresan en forma normal conjuntiva , en la que cada cláusula se expresa como una disyunción y todo el conjunto de restricciones se expresa como una conjunción de cláusulas, como
Una solución a tal instancia es una asignación de valores de verdad a las variables que satisfaga todas las cláusulas, o de manera equivalente, que haga que la expresión en forma normal conjuntiva de la instancia se vuelva verdadera cuando los valores de las variables se sustituyen en ella. La familia de todas las soluciones tiene una estructura natural como álgebra de medianas, donde la mediana de tres soluciones se forma eligiendo cada valor de verdad como la función mayoritaria de los valores de las tres soluciones; es sencillo verificar que esta solución mediana no puede violar ninguna de las cláusulas. Por lo tanto, estas soluciones forman un gráfico de mediana, en el que el vecino de cada solución se forma negando un conjunto de variables que están obligadas a ser iguales o desiguales entre sí.
Por el contrario, cada gráfico mediano G puede representarse de esta manera como el conjunto de soluciones para un caso de 2-satisfacibilidad. Para encontrar dicha representación, cree una instancia de 2-satisfacibilidad en la que cada variable describa la orientación de uno de los bordes del gráfico (una asignación de una dirección al borde que hace que el gráfico se vuelva dirigido en lugar de no dirigido) y cada restricción permita dos aristas comparten un par de orientaciones solo cuando existe un vértice v tal que ambas orientaciones se encuentran a lo largo de caminos más cortos desde otros vértices hasta v . Cada vértice v de G corresponde a una solución de esta instancia de 2-satisfacibilidad en la que todas las aristas están dirigidas hacia v . Cada solución al caso debe provenir de algún vértice v de esta manera, donde v es la intersección común de los conjuntos W uw para aristas dirigidas de w a u ; esta intersección común existe debido a la propiedad de Helly de los conjuntos W uw . Por lo tanto, las soluciones a este caso de 2-satisfacibilidad corresponden uno por uno con los vértices de G.
Una retracción de un gráfico G es un mapa que preserva la adyacencia de G a uno de sus subgrafos. [18] Más precisamente, es un homomorfismo gráfico φ de G a sí mismo tal que φ( v ) = v para cada vértice v en el subgrafo φ(G). La imagen de la retracción se llama retracción de G. Las retracciones son ejemplos de aplicaciones métricas : la distancia entre φ( v ) y φ( w ), para cada v y w , es como máximo igual a la distancia entre v y w , y es igual siempre que v y w pertenezcan a φ( G ). Por lo tanto, una retracción debe ser un subgrafo isométrico de G : las distancias en la retracción son iguales a las de G.
Si G es una gráfica mediana, y a , b y c son tres vértices arbitrarios de una retracción φ( G ), entonces φ( m ( a , b , c )) debe ser una mediana de a , b y c. , por lo que debe ser igual a m ( a , b , c ). Por lo tanto, φ( G ) contiene medianas de todos los triples de sus vértices y también debe ser una gráfica de medianas. En otras palabras, la familia de gráficos de mediana se cierra bajo la operación de retracción. [19]
Un gráfico de hipercubo , en el que los vértices corresponden a todos los posibles vectores de bits de k bits y en el que dos vértices son adyacentes cuando los vectores de bits correspondientes difieren en un solo bit, es un caso especial de un gráfico de cuadrícula de k dimensiones y, por lo tanto, es una mediana. grafico. La mediana de tres vectores de bits a , b y c se puede calcular calculando, en cada posición de bit, la función mayoritaria de los bits de a , b y c . Dado que las gráficas medianas están cerradas bajo retracción e incluyen los hipercubos, cada retracción de un hipercubo es una gráfica mediana.
Por el contrario, todo gráfico mediano debe ser la retracción de un hipercubo. [20] Esto puede verse a partir de la conexión, descrita anteriormente, entre las gráficas de la mediana y la satisfacibilidad 2: sea G la gráfica de soluciones para un caso de satisfacibilidad 2; sin pérdida de generalidad, este ejemplo se puede formular de tal manera que no haya dos variables siempre iguales o siempre desiguales en cada solución. Entonces el espacio de todas las asignaciones de verdad a las variables de esta instancia forma un hipercubo. Para cada cláusula, formada como la disyunción de dos variables o sus complementos, en el caso de 2-satisfacibilidad, se puede formar una retracción del hipercubo en el que las asignaciones de verdad que violan esta cláusula se asignan a asignaciones de verdad en las que ambas variables satisfacen la cláusula. sin cambiar las otras variables en la asignación de verdad. La composición de las retracciones formadas de esta manera para cada una de las cláusulas da una retracción del hipercubo en el espacio de solución de la instancia y, por lo tanto, da una representación de G como la retracción de un hipercubo. En particular, las gráficas de medianas son subgrafías isométricas de hipercubos y, por tanto, son cubos parciales . Sin embargo, no todos los cubos parciales son gráficos de medianas; por ejemplo, un gráfico de ciclo de seis vértices es un cubo parcial pero no es un gráfico de mediana.
Como describen Imrich y Klavžar (2000), se puede construir una incrustación isométrica de un gráfico mediano en un hipercubo en el tiempo O ( m log n ), donde n y m son los números de vértices y aristas del gráfico respectivamente. [21]
Los problemas de probar si una gráfica es una gráfica mediana y si una gráfica no tiene triángulos habían sido bien estudiados cuando Imrich, Klavžar y Mulder (1999) observaron que, en cierto sentido, son computacionalmente equivalentes. [22] Por lo tanto, el límite de tiempo más conocido para probar si un gráfico no tiene triángulos, O ( m 1,41 ), [23] se aplica también a probar si un gráfico es un gráfico de mediana y cualquier mejora en los algoritmos de prueba de gráficos de mediana. También conduciría a una mejora en los algoritmos para detectar triángulos en gráficos.
En una dirección, supongamos que a uno se le da como entrada un gráfico G y se debe probar si G no tiene triángulos. A partir de G , construya un nuevo gráfico H que tenga como vértices cada conjunto de cero, uno o dos vértices adyacentes de G. Dos de estos conjuntos son adyacentes en H cuando difieren exactamente en un vértice. Una descripción equivalente de H es que se forma dividiendo cada arista de G en un camino de dos aristas y agregando un nuevo vértice conectado a todos los vértices originales de G. Este gráfico H es por construcción un cubo parcial, pero es un gráfico mediano solo cuando G no tiene triángulos: si a , b y c forman un triángulo en G , entonces { a , b }, { a , c }, y { b , c } no tienen mediana en H , ya que dicha mediana tendría que corresponder al conjunto { a , b , c }, pero los conjuntos de tres o más vértices de G no forman vértices en H. Por lo tanto, G no tiene triángulos si y sólo si H es una gráfica mediana. En el caso de que G no tenga triángulos, H es su gráfico simplex . Mediante esta construcción, también se podría utilizar un algoritmo para probar eficientemente si H es una gráfica mediana para probar si G no tiene triángulos. Esta transformación preserva la complejidad computacional del problema, ya que el tamaño de H es proporcional al de G.
La reducción en la otra dirección, desde la detección de triángulos hasta la prueba de gráficos de mediana, es más complicada y depende del algoritmo anterior de reconocimiento de gráficos de mediana de Hagauer, Imrich y Klavžar (1999), que prueba varias condiciones necesarias para los gráficos de mediana en un tiempo casi lineal. . El nuevo paso clave implica utilizar una búsqueda en amplitud para dividir los vértices del gráfico en niveles de acuerdo con sus distancias desde algún vértice raíz elegido arbitrariamente, formando un gráfico a partir de cada nivel en el que dos vértices son adyacentes si comparten un vecino común en el nivel anterior. y buscando triángulos en estas gráficas. La mediana de cualquier triángulo debe ser vecina común de los tres vértices del triángulo; si este vecino común no existe, la gráfica no es una gráfica mediana. Si todos los triángulos encontrados de esta manera tienen medianas, y el algoritmo anterior encuentra que la gráfica satisface todas las demás condiciones para ser una gráfica de mediana, entonces en realidad debe ser una gráfica de mediana. Este algoritmo requiere, no sólo la capacidad de probar si existe un triángulo, sino también una lista de todos los triángulos en el gráfico de niveles. En gráficos arbitrarios, enumerar todos los triángulos a veces requiere Ω ( m 3/2 ) de tiempo, ya que algunos gráficos tienen esa cantidad de triángulos; sin embargo, Hagauer et al. muestran que el número de triángulos que surgen en los gráficos de niveles de su reducción es casi lineal, lo que permite a Alon et al. Se utilizará una técnica rápida basada en la multiplicación de matrices para encontrar triángulos.
La filogenia es la inferencia de árboles evolutivos a partir de las características observadas de las especies ; dicho árbol debe colocar la especie en vértices distintos y puede tener vértices latentes adicionales , pero se requiere que los vértices latentes tengan tres o más aristas incidentes y también deben estar etiquetados con características. Una característica es binaria cuando tiene sólo dos valores posibles, y un conjunto de especies y sus características exhiben una filogenia perfecta cuando existe un árbol evolutivo en el que los vértices (especies y vértices latentes) etiquetados con cualquier valor característico particular forman un subárbol contiguo. Si no es posible obtener un árbol con una filogenia perfecta, a menudo se desea encontrar uno que exhiba la máxima parsimonia o, equivalentemente, minimizar el número de veces que los puntos finales de un borde de árbol tienen valores diferentes para una de las características, sumadas sobre todos los bordes y todas las características.
Buneman (1971) describió un método para inferir filogenias perfectas para características binarias, cuando existen. Su método se generaliza naturalmente a la construcción de un gráfico de mediana para cualquier conjunto de especies y características binarias, al que se le ha llamado red de mediana o gráfico de Buneman [24] y es un tipo de red filogenética . Cada árbol evolutivo de máxima parsimonia se integra en el gráfico de Buneman, en el sentido de que los bordes del árbol siguen caminos en el gráfico y el número de cambios de valores característicos en el borde del árbol es el mismo que el número en el camino correspondiente. El gráfico de Buneman será un árbol si y sólo si existe una filogenia perfecta; esto sucede cuando no hay dos características incompatibles para las cuales se observen las cuatro combinaciones de valores característicos.
Para formar el gráfico de Buneman para un conjunto de especies y características, primero, elimine las especies redundantes que no se pueden distinguir de otras especies y las características redundantes que siempre son las mismas que alguna otra característica. Luego, forme un vértice latente para cada combinación de valores característicos de modo que cada dos de los valores existan en alguna especie conocida. En el ejemplo mostrado, hay ratones pequeños de cola marrón, ratones pequeños de cola plateada, ratones pequeños de cola marrón, ratones grandes de cola marrón y ratones grandes de cola plateada; El método del gráfico de Buneman formaría un vértice latente correspondiente a una especie desconocida de pequeños ratones de cola plateada, porque cada combinación por pares (pequeño y plateado, pequeño y con cola, y plateado y con cola) se observa en algunas otras especies conocidas. Sin embargo, el método no inferiría la existencia de grandes ratones marrones sin cola, porque no se sabe de ningún ratón que tenga ambos rasgos grandes y sin cola. Una vez determinados los vértices latentes, forme una arista entre cada par de especies o vértices latentes que difieran en una sola característica.
De manera equivalente, se puede describir una colección de características binarias como un sistema dividido , una familia de conjuntos que tiene la propiedad de que el conjunto complementario de cada conjunto de la familia también está en la familia. Este sistema dividido tiene un conjunto para cada valor característico, formado por las especies que tienen ese valor. Cuando se incluyen los vértices latentes, el sistema dividido resultante tiene la propiedad de Helly : cada subfamilia que se cruza por pares tiene una intersección común. En cierto sentido, los gráficos de mediana se caracterizan por provenir de sistemas divididos de Helly: los pares ( W uv , W vu ) definidos para cada borde uv de un gráfico de mediana forman un sistema dividido de Helly, por lo que si se aplica la construcción del gráfico de Buneman a este sistema no Se necesitarán vértices latentes y el resultado será el mismo que el gráfico inicial. [25]
Bandelt et al. (1995) y Bandelt, Macaulay y Richards (2000) describen técnicas para el cálculo manual simplificado del gráfico de Buneman y utilizan esta construcción para visualizar las relaciones genéticas humanas.
