En la teoría de grafos , una división de las matemáticas , un gráfico de la mediana es un grafo no dirigido en el que cada tres vértices de un , b , y c de tienen un único mediana : un vértice m ( un , b , c ) que pertenece a rutas más cortas entre cada par de un , b , y c .
El concepto de gráficas 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 llamarlas "gráficas medianas" parece ser Nebeský (1971) . Como escriben Chung , Graham y Saks, "las gráficas medianas surgen naturalmente en el estudio de conjuntos ordenados y retículas distributivas discretas , y tienen 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 mediano. [2] Las gráficas de medianas también surgen en la teoría de la elección social.: si un conjunto de alternativas tiene la estructura de un gráfico mediano, es posible derivar de manera inequívoca una preferencia mayoritaria entre ellas. [3]
Klavžar y Mulder (1999) , Bandelt y Chepoi (2008) y Knuth (2008) ofrecen encuestas adicionales de gráficos de medianas .
Ejemplos de
Cada árbol es un gráfico de mediana. [4] Para ver esto, observamos que en un árbol, la unión de los tres caminos más cortos entre pares de los tres vértices de un , b , y c es ya sea en sí mismo un camino, o un subárbol formado por tres caminos reunidos en un solo centro nodo con grado tres. Si la unión de los tres caminos es en sí mismo un camino, la mediana m ( a , b , c ) es igual a uno de a , b o c , cualquiera de estos tres vértices se encuentra 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.
Los gráficos de cuadrícula proporcionan ejemplos adicionales de gráficas de medianas . En un gráfico de la red, las coordenadas de la mediana m ( un , b , c ) se pueden encontrar como la mediana de las coordenadas de un , b , y c . A la inversa, resulta que, en cada gráfico de mediana, se pueden etiquetar los vértices por puntos en una red de números enteros de tal manera que las medianas se pueden calcular por coordenadas de esta manera. [5]
Las gráficas cuadradas , gráficas planas en las 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 las gráficas medianas. [6] Un poliomino es un caso especial de una gráfica cuadrada y, por lo tanto, también forma una gráfica 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értice de κ ( G ) están unidas por un borde si las camarillas correspondientes difieren por 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 puede formarse 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 que no sea cuatro puede ser un gráfico de mediana. Cada tales ciclo tiene tres vértices de un , b , y c de tal manera que los tres caminos más cortos envolver todo el camino alrededor del ciclo sin tener una intersección común. Para tal triple de vértices, no puede haber mediana.
Definiciones equivalentes
En una gráfica arbitraria, por cada dos vértices a y b , el número mínimo de bordes entre ellos se llama su distancia , denotado por d ( x , y ). El intervalo de vértices que se encuentran en las trayectorias más cortas entre una y b se define como
- Yo ( a , b ) = { v | d ( a , b ) = d (a, v) + d (v, b) }.
Un gráfico de la mediana se define por la propiedad de que, por cada tres vértices de un , b , y c , estos intervalos se intersecan en un solo punto:
- Para todos un , b , y c , | Yo ( a , b ) ∩ Yo ( a , c ) ∩ Yo ( b , c ) | = 1.
De manera equivalente, por cada tres vértices de un , b , y c se puede encontrar un vértice m ( un , b , c ) de tal manera que los no ponderados distancias en el gráfico satisfacen las igualdades
- re ( a , segundo ) = re ( a , metro ( a , segundo , c )) + re ( metro ( a , segundo , c ), segundo )
- re ( a , c ) = re ( a , metro ( a , segundo , c )) + re ( metro ( a , segundo , c ), c )
- re ( segundo , c ) = re ( segundo , metro ( a , segundo , c )) + re ( metro ( a , segundo , c ), c )
y m ( a , b , c ) es el único vértice para el que esto es cierto.
También es posible definir gráficas medianas como conjuntos de solución de problemas de satisfacibilidad 2 , como retracciones de hipercubos , como gráficas de álgebras medianas finitas , como gráficas de Buneman de sistemas divididos de Helly y como gráficas de windex 2; consulte las secciones siguientes.
Rejillas distributivas y álgebras medianas
En la teoría de la celosía , el gráfico de una celosía finita tiene un vértice para cada elemento de celosía y un borde para cada par de elementos en la relación de cobertura de la celosía. Las celosías se presentan comúnmente visualmente a través de diagramas de Hasse , que son dibujos de gráficos de celosías. Estos gráficos, especialmente en el caso de las celosías distributivas , resultan estar estrechamente relacionados con los gráficos medianos.
En una red distributiva, la operación mediana ternaria autodual de Birkhoff [9]
- m ( un , b , c ) = ( a ∧ b ) ∨ ( una ∧ c ) ∨ ( b ∧ c ) = ( a ∨ b ) ∧ ( una ∨ c ) ∧ ( b ∨ c ),
satisface ciertos axiomas clave, que comparte con la mediana habitual de números en el rango de 0 a 1 y con las álgebras medianas de manera más general:
- Idempotencia : m (a, a, b) = una para todos una y b .
- Conmutatividad : m ( a , b , c ) = m (a, c, b) = m (b, a, c) = m (b, c, a) = m (c, a, b) = m (c , b, a) para todos un , b , y c .
- Distributividad : m (a, m (b, c, d), e) = m (m (a, b, e), c, m (a, d, e)) para todo a , b , c , d , y e .
- Elementos de identidad : m (0, a , 1) = a para todos a .
La ley distributiva puede ser reemplazada por una ley asociativa: [10]
- Asociatividad : m ( x , w , m ( y , w , z )) = m ( m ( x , w , y ), w , z )
La operación mediana también se puede usar para definir una noción de intervalos para celosías distributivas:
- Yo ( a , b ) = { x | m (a, x, b) = x } = { x | a ∧ b ≤ x ≤ a ∨ b }. [11]
La gráfica de una finito distributiva de celosía tiene un borde entre los vértices a y b cuando I ( un , b ) = { a , b }. Por cada dos vértices de una y b de este gráfico, el intervalo I ( un , b ) definido en términos de celosía-teórico anterior consta de los vértices en los caminos más cortos de un a b , y de este modo coincide con los intervalos de gráfico-teórico definidos anteriormente. Por cada tres elementos de entramado una , b , y c , m ( un , b , c ) es la intersección única de los tres intervalos I ( un , b ), I ( una , c ) y 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 una gráfica mediana G contiene dos vértices 0 y 1 de manera que todos los demás vértices se encuentran en un camino más corto entre los dos (de manera equivalente, m (0, a , 1) = a para todo a ), entonces podemos definir un 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 celosías distributivas directamente como retracciones de hipercubos que preservan el diámetro. De manera más general, todo gráfico mediano da lugar a una operación ternaria m que satisface la 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 tiene necesariamente elementos 0 y 1) da lugar de la misma forma a un gráfico mediano. [14]
Conjuntos convexos y familias Helly
En un gráfico de la mediana, un conjunto S se dice de vértices para ser convexa si, por cada dos vértices de una y b perteneciente a S , todo el intervalo I ( un , b ) es un subconjunto de S . De manera equivalente, da las dos definiciones de intervalos anteriores, S es convexa si contiene cada camino más corto entre dos de sus vértices, o si contiene la mediana de cada conjunto de tres puntos al menos dos de los cuales son de S . Observe que la intersección de cada par de conjuntos convexos es en sí misma convexa. [15]
Los conjuntos convexos en una gráfica mediana tienen la propiedad de Helly : si F es una familia arbitraria de conjuntos convexos que se intersecan 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 , yc en la intersección de el par S y U , entonces cada camino más corto desde a hasta 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 trayectorias 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 sigue por inducción sobre el número de conjuntos, ya que uno puede reemplazar un par arbitrario de conjuntos en F por su intersección, usando el resultado para 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ñan un papel similar al de los medios espacios en el espacio euclidiano, son los conjuntos
- W uv = { w | d ( w , u ) < d ( w , v )}
definido para cada borde uv del gráfico. En palabras, W uv consiste en los vértices más cercanos a u que a v , o lo que es lo mismo, los vértices w de manera que algún camino más corto de v a w pasa por u . Para mostrar 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 (por considerando las posibles distancias entre los vértices) como medianas distintas de u , w 1 y w k , lo que contradice la definición de un gráfico de mediana 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 medianas como la solución de instancias de 2-satisfacibilidad, a continuación.
2-satisfacibilidad
Los gráficos de mediana tienen una estrecha conexión con los conjuntos de soluciones de problemas de satisfacibilidad 2 que se pueden utilizar tanto para caracterizar estos gráficos como para relacionarlos con mapas de hipercubos que preservan la adyacencia. [17]
Una instancia de 2-satisfiability consiste en una colección de variables booleanas y una colección de cláusulas , restricciones en 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 para 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 de forma normal conjuntiva para la instancia se convierta en verdadera cuando los valores de las variables se sustituyen en ella. La familia de todas las soluciones tiene una estructura natural como un álgebra mediana, donde la mediana de tres soluciones se forma eligiendo cada valor de verdad como la función mayoritaria de los valores en 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 una gráfica mediana, en la que el vecino de cada solución se forma negando un conjunto de variables que están todas restringidas a ser iguales o desiguales entre sí.
A la inversa, cada gráfico G de mediana puede representarse de esta manera como el conjunto de soluciones en una instancia de satisfacibilidad 2. Para encontrar tal representación, cree una instancia de 2-satisfacibilidad en la que cada variable describe la orientación de uno de los bordes en el 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 permite dos aristas para compartir un par de orientaciones solo cuando existe un vértice v tal que ambas orientaciones se encuentran a lo largo de las rutas más cortas desde otros vértices hasta v . Cada vértice v de G corresponde a una solución a esta instancia de satisfacibilidad 2 en la que todas las aristas se dirigen hacia v . Cada solución a la instancia 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 Helly de los conjuntos W uw . Por lo tanto, las soluciones a este 2-satisfacibilidad ejemplo corresponden uno a uno con los vértices de G .
Se retrae de hipercubos
Una retracción de un gráfico G es un mapa que preserva la adyacencia de G a uno de sus subgráficos. [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 una retracción del G . Las retracciones son ejemplos de mapas métricos : 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 pertenecen a φ ( G ). Por lo tanto, un retracto debe ser un subgrafo isométrica de G : distancias en la retracción son iguales a los de G .
Si G es una gráfica la mediana y una , b , y c son un arbitrarias tres vértices de un φ de retracción ( G ), entonces φ ( m ( un , b , c )) debe ser una mediana de un , 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 un gráfico de mediana. En otras palabras, la familia de gráficos medianos se cierra bajo la operación de retracción. [19]
Un gráfico hipercubo , en el que los vértices corresponden a todas las posibles k bits bitvectors y en el que dos vértices son adyacentes cuando los bitvectors correspondientes difieren en sólo un único bit, es un caso especial de un k gráfico de la red dimensional y por lo tanto es una mediana grafico. La mediana de tres bitvectors un , b , y c puede ser calculada mediante el cálculo, en cada posición de bit, la función mayoritaria de los bits de un , b , y c . Dado que los gráficos medianos se cierran bajo retracción e incluyen los hipercubos, cada retracción de un hipercubo es un gráfico mediano.
Por el contrario, cada gráfico de mediana debe ser la retracción de un hipercubo. [20] Esto puede verse a partir de la conexión, descrita anteriormente, entre gráficos de mediana y 2-satisfacibilidad: sea G el gráfico de soluciones para una instancia de 2-satisfacibilidad; sin pérdida de generalidad, esta instancia puede formularse 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 sobre 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, los gráficos medianos son subgráficos isométricos de hipercubos y, por lo tanto, son cubos parciales . Sin embargo, no todos los cubos parciales son gráficos medianos; por ejemplo, un gráfico de ciclo de seis vértices es un cubo parcial, pero no es un gráfico de mediana.
Como Imrich y Klavžar (2000) describen, una inmersión isométrica de un gráfico de la mediana en un hipercubo se puede construir en el tiempo O ( m log n ), donde n y m son los números de vértices y los bordes de la gráfica respectivamente. [21]
Gráficos sin triángulos y algoritmos de reconocimiento
Los problemas de probar si una gráfica es una gráfica mediana y si una gráfica no tiene triángulos , ambos 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 para 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, suponga que a uno se le da como entrada un gráfico G , y debe probar si G está libre de triángulos. De G , construir un nuevo gráfico de H que tiene como vértices de 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 está formada por la división de cada borde de G en un camino de dos bordes, y la adición de 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 mediana sólo cuando G es-triángulo libre: si una , b , y c forman un triángulo en G , entonces { a , b }, { a , c }, y { b , c } no tienen mediana en H , por ejemplo una mediana tendría que corresponden al conjunto { a , b , c }, pero conjuntos de tres o más vértices de G no forman vértices en H . Por lo tanto, G está libre de triángulos si y solo si H es una gráfica mediana. En el caso de que G no tenga triángulos, H es su gráfica símplex . Mediante esta construcción, un algoritmo para probar de manera eficiente si H es un gráfico mediano también podría usarse para probar si G está libre de triángulos. Esta transformación preserva la complejidad computacional del problema, para el tamaño de H es proporcional a la de G .
La reducción en la otra dirección, desde la detección de triángulos hasta las pruebas de gráficos medianos, es más complicada y depende del algoritmo anterior de reconocimiento de gráficos medianos de Hagauer, Imrich y Klavžar (1999) , que prueba varias condiciones necesarias para gráficos medianos en tiempo casi lineal. . El nuevo paso clave consiste en utilizar una primera búsqueda de 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 de cada nivel en el que dos vértices son adyacentes si comparten un vecino común en el nivel anterior. y buscar triángulos en estos gráficos. La mediana de cualquier triángulo de este tipo debe ser un vecino 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 mediana, entonces en realidad debe ser una gráfica mediana. Este algoritmo requiere, no solo la capacidad de probar si existe un triángulo, sino una lista de todos los triángulos en el gráfico de nivel. En gráficos arbitrarios, enumerar todos los triángulos a veces requiere un tiempo de Ω ( m 3/2 ), ya que algunos gráficos tienen tantos triángulos, sin embargo Hagauer et al. muestran que el número de triángulos que surgen en los gráficos de nivel de su reducción es casi lineal, lo que permite que Alon et al. Técnica basada en la multiplicación rápida de matrices para encontrar triángulos que se utilizarán.
Árboles evolutivos, gráficos de Buneman y sistemas divididos de Helly
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 etiquetarse con características. Una característica es binaria cuando tiene solo 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 un árbol con una filogenia perfecta no es posible, a menudo se desea encontrar uno que exhiba la máxima parsimonia , o lo que es lo mismo, minimizar el número de veces que los puntos finales del borde de un árbol tienen diferentes valores para una de las características, sumados en todos los bordes y en todos caracteristicas.
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 mediano para cualquier conjunto de especies y características binarias, que se ha denominado red mediana o gráfico de Buneman [24] y es un tipo de red filogenética . Cada árbol evolutivo de máxima parsimonia se incrusta en el gráfico de Buneman, en el sentido de que los bordes del árbol siguen rutas en el gráfico y el número de cambios de valor característico en el borde del árbol es el mismo que el número en la ruta correspondiente. El gráfico de Buneman será un árbol si y solo si existe una filogenia perfecta; esto sucede cuando no hay dos características incompatibles para las que se observan 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 son indistinguibles de algunas otras especies y las características redundantes que son siempre las mismas que alguna otra característica. Luego, forme un vértice latente para cada combinación de valores característicos de manera que cada dos de los valores existan en algunas especies conocidas. En el ejemplo que se muestra, hay pequeños ratones marrones sin cola, pequeños ratones plateados sin cola, pequeños ratones con cola marrón, ratones grandes con cola marrón y ratones grandes con 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, plateada 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 que ningún ratón tenga los rasgos grandes y sin cola. Una vez que se determinan los vértices latentes, forme un borde 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 en la familia también está en la familia. Este sistema de división tiene un conjunto para cada valor característico, compuesto por las especies que tienen ese valor. Cuando se incluyen los vértices latentes, el sistema de división resultante tiene la propiedad Helly : cada subfamilia que se cruza por pares tiene una intersección común. En cierto sentido, los gráficos medianos se caracterizan por provenir de sistemas divididos de Helly: los pares ( W uv , W vu ) definidos para cada borde uv de un gráfico mediano 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 del gráfico inicial. [25]
Bandelt y col. (1995) y Bandelt, Macaulay & 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.
Propiedades adicionales
- El producto cartesiano de cada dos gráficas de mediana es otra gráfica de mediana. Las medianas en el gráfico del producto pueden calcularse encontrando independientemente las medianas en los dos factores, al igual que las medianas en los gráficos de cuadrícula se pueden calcular encontrando independientemente la mediana en cada dimensión lineal.
- El windex de un gráfico mide la cantidad de anticipación necesaria para resolver de manera óptima un problema en el que a uno se le da una secuencia de vértices de gráfico s i , y debe encontrar como salida otra secuencia de vértices t i minimizando la suma de las distancias d ( s i , t i ) y d ( t i - 1 , t i ) . Las gráficas de mediana son exactamente las gráficas que tienen windex 2. En una gráfica de mediana, la opción óptima es establecer t i = m ( t i - 1 , s i , s i + 1 ) . [1]
- La propiedad de tener una mediana única también se denomina propiedad única del punto de Steiner . [1] Un óptima árbol de Steiner para tres vértices de un , b , y c en un gráfico de la mediana se puede obtener como la unión de tres caminos más cortos, de un , b , y c a m ( un , b , c ). Bandelt y Barthélémy (1984) estudian de manera más general el problema de encontrar el vértice minimizando la suma de distancias a cada uno de un conjunto dado de vértices, y muestran que tiene una solución única para cualquier número impar de vértices en una gráfica mediana. También muestran que esta mediana de un conjunto S de vértices en una mediana satisface gráfico del criterio de Condorcet para el ganador de una elección : en comparación con cualquier otro vértice, que está más cerca de la mayoría de los vértices en S .
- Al igual que con los cubos parciales de manera más general, cada gráfica mediana con n vértices tiene como máximo ( n / 2) log 2 n aristas. Sin embargo, el número de aristas no puede ser demasiado pequeño: Klavžar, Mulder y Škrekovski (1998) prueban que en cada gráfica mediana se cumple la desigualdad 2 n - m - k ≤ 2 , donde m es el número de aristas yk es la dimensión de el hipercubo del que se retrae el gráfico. Esta desigualdad es una igualdad si y solo si el gráfico de la mediana no contiene cubos. Esto es una consecuencia de otra identidad para los gráficos medianos: la característica de Euler Σ (-1) dim ( Q ) es siempre igual a uno, donde la suma se toma sobre todos los subgrafos Q del hipercubo del gráfico mediano dado. [26]
- Los únicos gráficos medianos regulares son los hipercubos. [27]
- Cada gráfico de mediana es un gráfico modular . Los gráficos modulares son una clase de gráficos en los que cada triple de vértices tiene una mediana, pero no se requiere que las medianas sean únicas. [28]
Notas
- ↑ a b c Chung, Graham y Saks (1987) .
- ^ Buneman (1971) ; Dress et al. (1997) ; Vestido, Huber y Moulton (1997) .
- ^ Bandelt y Barthélémy (1984) ; Day y McMorris (2003) .
- ^ Imrich y Klavžar (2000) , Proposición 1.26, p. 24.
- ^ Esto se deduce inmediatamente de la caracterización de los gráficos medianos como retracciones de hipercubos, que se describe a continuación.
- ^ Soltan, Zambitskii y Prisăcaru (1973) ; Chepoi, Dragan y Vaxès (2002) ; Chepoi, Fanciullini y Vaxès (2004) .
- ^ Klavžar y Škrekovski (2000) .
- ^ Barthélemy, Leclerc y Monjardet (1986) , página 200.
- ↑ Birkhoff & Kiss (1947) atribuyen la definición de esta operación a Birkhoff, G. (1940), Lattice Theory , American Mathematical Society, p. 74.
- ^ Knuth (2008) , p. 65 y ejercicios 75 y 76 en las págs. 89–90. Knuth afirma que se desconoce una prueba simple de que la asociatividad implica la distributividad.
- ^ La equivalencia entre las dos expresiones en esta ecuación, una en términos de la operación mediana y la otra en términos de operaciones de celosía y desigualdades es el Teorema 1 de Birkhoff y Kiss (1947) .
- ^ Birkhoff y Kiss (1947) , Teorema 2.
- ^ Birkhoff y Kiss (1947) , p. 751.
- ^ Avann (1961) .
- ↑ Knuth (2008) llama a este conjunto un ideal , pero un conjunto convexo en el gráfico de una red distributiva no es lo mismo que un ideal de la red .
- ^ Imrich y Klavžar (2000) , Teorema 2.40, p. 77.
- ^ Bandelt y Chepoi (2008) , Proposición 2.5, p. 8; Chung, Graham y Saks (1989) ; Feder (1995) ; Knuth (2008) , Teorema S, pág. 72.
- ^ Infierno (1976) .
- ^ Imrich y Klavžar (2000) , Proposición 1.33, p. 27.
- ^ Bandelt (1984) ; Imrich y Klavžar (2000) , Teorema 2.39, p. 76; Knuth (2008) , pág. 74.
- ↑ La técnica, que culmina en el Lema 7.10 de la p. 218 de Imrich y Klavžar, consiste en aplicar un algoritmo de Chiba & Nishizeki (1985) para listar los 4 ciclos en el gráfico G , formando un gráfico no dirigido que tiene como vértices los bordes de G y teniendo como bordes los lados opuestos de un ciclo de 4, y usando los componentes conectados de este gráfico derivado para formar coordenadas de hipercubo. Un algoritmo equivalente es Knuth (2008) , Algoritmo H, p. 69.
- ^ Para los algoritmos de reconocimiento de gráficos medianos anteriores, consulte Jha & Slutzki (1992) , Imrich & Klavžar (1998) y Hagauer, Imrich & Klavžar (1999) . Para los algoritmos de detección de triángulos, véanse Itai y Rodeh (1978) , Chiba y Nishizeki (1985) y Alon, Yuster y Zwick (1995) .
- ^ Alon, Yuster & Zwick (1995) , basado en la multiplicación rápida de matrices . Aquí m es el número de aristas en el gráfico, y la notación O grande oculta un factor constante grande; los mejores algoritmos prácticos para la detección de triángulos requieren un tiempo O ( m 3/2 ). Para el reconocimiento de gráficos medianos, el límite de tiempo se puede expresar en términos de m o n (el número de vértices), como m = O ( n log n ).
- ↑ Mulder y Schrijver (1979) describieron una versión de este método para sistemas de características que no requieren vértices latentes, y Barthélémy (1989) da la construcción completa. El nombre del gráfico de Buneman se da en Dress et al. (1997) y Dress, Huber y Moulton (1997) .
- ^ Mulder y Schrijver (1979) .
- ^ Škrekovski (2001) .
- ^ Mulder (1980) .
- ^ Gráficos modulares , sistema de información sobre clases de gráficos y sus inclusiones, consultado el 30 de septiembre de 2016.
Referencias
- Alon, Noga ; Yuster, Rafael; Zwick, Uri (1995), "Codificación de colores", Journal of the ACM , 42 (4): 844–856, doi : 10.1145 / 210332.210337 , MR 1411787 , S2CID 208936467 CS1 maint: parámetro desalentado ( enlace ).
- Avann, SP (1961), "Semi-retículos distributivos ternarios métricos", Proceedings of the American Mathematical Society , 12 (3): 407–414, doi : 10.2307 / 2034206 , JSTOR 2034206 , MR 0125807.
- Bandelt, Hans-Jürgen (1984), "Retracts of hypercubes", Journal of Graph Theory , 8 (4): 501–510, doi : 10.1002 / jgt.3190080407 , MR 0766499.
- Bandelt, Hans-Jürgen; Barthélémy, Jean-Pierre (1984), "Medianas en gráficas de medianas", Matemáticas aplicadas discretas , 8 (2): 131–142, doi : 10.1016 / 0166-218X (84) 90096-9 , MR 0743019.
- Bandelt, Hans-Jürgen; Chepoi, Victor (2008), "Teoría y geometría de grafos métricos: una encuesta" (PDF) , Surveys on Discrete and Computational Geometry , Contemporary Mathematics, 453 , Providence, RI: American Mathematical Society, pp. 49-86, doi : 10.1090 / conm / 453/08795 , ISBN 9780821842393, MR 2405677.
- Bandelt, Hans-Jürgen; Forster, P .; Sykes, BC; Richards, Martin B. (1 de octubre de 1995), "Retratos mitocondriales de poblaciones humanas utilizando redes medianas" , Genética , 141 (2): 743–753, PMC 1206770 , PMID 8647407.
- Bandelt, Hans-Jürgen; Forster, P .; Rohl, Arne (1 de enero de 1999), "Redes de unión media para inferir filogenias intraespecíficas" , Molecular Biology and Evolution , 16 (1): 37-48, doi : 10.1093 / oxfordjournals.molbev.a026036 , PMID 10331250 , archivado de el original el 27 de diciembre de 2005.
- Bandelt, Hans-Jürgen; Macaulay, Vincent; Richards, Martin B. (2000), "Redes medianas: construcción rápida y reducción codiciosa, una simulación y dos estudios de caso de ADNmt humano", Molecular Phylogenetics and Evolution , 16 (1): 8-28, CiteSeerX 10.1.1.128. 3232 , doi : 10.1006 / mpev.2000.0792 , PMID 10877936.
- Barthélémy, Jean-Pierre (1989), "De hipergráficos de copair a gráficos medianos con vértices latentes", Matemáticas discretas , 76 (1): 9-28, doi : 10.1016 / 0012-365X (89) 90283-5 , MR 1002234.
- Barthélemy, J.-P .; Leclerc, B .; Monjardet, B. (1986), "Sobre el uso de conjuntos ordenados en problemas de comparación y consenso de clasificaciones", Journal of Classification , 3 (2): 187-224, doi : 10.1007 / BF01894188 , S2CID 6092438.
- Birkhoff, Garrett ; Kiss, SA (1947), "Una operación ternaria en celosías distributivas" , Boletín de la American Mathematical Society , 53 (1): 749–752, doi : 10.1090 / S0002-9904-1947-08864-9 , MR 0021540 CS1 maint: parámetro desalentado ( enlace ).
- Buneman, P. (1971), "La recuperación de árboles a partir de medidas de disimilitud", en Hodson, FR; Kendall, DG; Tautu, PT (eds.), Matemáticas en las ciencias arqueológicas e históricas , Edinburgh University Press, págs. 387–395.
- Chepoi, V .; Dragan, F .; Vaxès, Y. (2002), "Problemas de centro y diámetro en cuadrangulaciones planas y triangulaciones", Proc. 13º Simposio ACM-SIAM sobre algoritmos discretos , Soda '02, págs. 346–355 , ISBN 9780898715132.
- Chepoi, V .; Fanciullini, C .; Vaxès, Y. (2004), "Problema de la mediana en algunas triangulaciones y cuadrangulaciones planas", Geometría computacional: teoría y aplicaciones , 27 (3): 193–210, doi : 10.1016 / j.comgeo.2003.11.002.
- Chiba, N .; Nishizeki, T. (1985), "Arboricity and subgraph Listing algoritmos", SIAM Journal on Computing , 14 : 210-223, doi : 10.1137 / 0214017 , MR 0774940.
- Chung, FRK ; Graham, RL ; Saks, ME (1987), "Dynamic search in graphs", en Wilf, H. (ed.), Discrete Algorithms and Complexity (Kyoto, 1986) (PDF) , Perspectives in Computing, 15 , Nueva York: Academic Press, págs. 351–387, MR 0910939 CS1 maint: parámetro desalentado ( enlace ).
- Chung, FRK ; Graham, RL ; Saks, ME (1989), "Un problema de ubicación dinámica para gráficos" (PDF) , Combinatorica , 9 (2): 111-132, doi : 10.1007 / BF02124674 , S2CID 5419897 CS1 maint: parámetro desalentado ( enlace ).
- Día, William HE; McMorris, FR (2003), Teoría del consenso axiomático en la elección de grupo y bioinformática , Sociedad de Matemáticas Industriales y Aplicadas, págs. 91–94, ISBN 978-0-89871-551-4.
- Vestido, A .; Hendy, M .; Huber, K .; Moulton, V. (1997), "Sobre el número de vértices y aristas del gráfico de Buneman", Annals of Combinatorics , 1 (1): 329–337, doi : 10.1007 / BF02558484 , MR 1630739 , S2CID 120716928.
- Vestido, A .; Huber, K .; Moulton, V. (1997), "Algunas variaciones sobre un tema de Buneman", Annals of Combinatorics , 1 (1): 339–352, doi : 10.1007 / BF02558485 , MR 1630743 , S2CID 122966547.
- Duffus, Dwight ; Rival, Ivan (1983), "Gráficos orientables como celosías distributivas", Proceedings of the American Mathematical Society , 88 (2): 197–200, doi : 10.2307 / 2044697 , JSTOR 2044697.
- Feder, T. (1995), Redes estables y gráficos de productos , Memorias de la Sociedad Matemática Estadounidense, 555.
- Hagauer, Johann; Imrich, Wilfried; Klavžar, Sandi (1999), "Recognizing median graph in subcuadratic time", Theoretical Computer Science , 215 (1-2): 123-136, doi : 10.1016 / S0304-3975 (97) 00136-9 , MR 1678773.
- Hell, Pavol (1976), "Graph retractions", Colloquio Internazionale sulle Teorie Combinatorie (Roma, 1973), Tomo II , Atti dei Convegni Lincei, 17 , Roma: Accad. Naz. Lincei, págs. 263–268, MR 0543779 CS1 maint: parámetro desalentado ( enlace ).
- Imrich, Wilfried; Klavžar, Sandi (1998), "Un lema de convexidad y procedimientos de expansión para gráficos bipartitos", European Journal of Combinatorics , 19 (6): 677–686, doi : 10.1006 / eujc.1998.0229 , MR 1642702.
- Imrich, Wilfried; Klavžar, Sandi (2000), Gráficos de productos: estructura y reconocimiento , Wiley, ISBN 978-0-471-37039-0, MR 0788124.
- Imrich, Wilfried; Klavžar, Sandi; Mulder, Henry Martyn (1999), "Gráficas medianas y gráficas sin triángulos", SIAM Journal on Discrete Mathematics , 12 (1): 111-118, CiteSeerX 10.1.1.28.5906 , doi : 10.1137 / S0895480197323494 , MR 1666073.
- Itai, A .; Rodeh, M. (1978), "Encontrar un circuito mínimo en un gráfico", SIAM Journal on Computing , 7 (4): 413–423, doi : 10.1137 / 0207033 , MR 0508603.
- Jha, Pranava K .; Slutzki, Giora (1992), "Algoritmos de expansión convexa para el reconocimiento y la incrustación isométrica de gráficos medianos", Ars Combinatoria , 34 : 75–92, MR 1206551.
- Klavžar, Sandi; Mulder, Henry Martyn (1999), "Gráficos medianos: caracterizaciones, teoría de la ubicación y estructuras relacionadas", Journal of Combinatorial Mathematics and Combinatorial Computing , 30 : 103-127, MR 1705337.
- Klavžar, Sandi; Mulder, Henry Martyn; Škrekovski, Riste (1998), "Una fórmula tipo Euler para gráficas medianas", Matemáticas discretas , 187 (1): 255–258, doi : 10.1016 / S0012-365X (98) 00019-3 , MR 1630736.
- Klavžar, Sandi; Škrekovski, Riste (2000), "En gráficos de mediana y gráficos de cuadrícula de mediana", Matemáticas discretas , 219 (1–3): 287–293, doi : 10.1016 / S0012-365X (00) 00085-6 , MR 1761732.
- Knuth, Donald E. (2008), "Álgebras medianas y gráficas medianas", El arte de la programación informática , IV, Fascículo 0: Introducción a los algoritmos combinatorios y las funciones booleanas, Addison-Wesley, págs. 64-74, ISBN 978-0-321-53496-5 CS1 maint: parámetro desalentado ( enlace ).
- Mulder, Henry Martyn (1980), " n- cubos y gráficas medianas", Journal of Graph Theory , 4 (1): 107–110, doi : 10.1002 / jgt.3190040112 , MR 0558458.
- Mulder, Henry Martyn; Schrijver, Alexander (1979), "Gráficos medianos e hipergráficos Helly" , Matemáticas discretas , 25 (1): 41–50, doi : 10.1016 / 0012-365X (79) 90151-1 , MR 0522746.
- Nebeský, Ladislav (1971), "Gráficos medianos", Commentationes Mathematicae Universitatis Carolinae , 12 : 317–325, MR 0286705.
- Škrekovski, Riste (2001), "Dos relaciones para gráficas medianas", Matemáticas discretas , 226 (1): 351–353, doi : 10.1016 / S0012-365X (00) 00120-5 , MR 1802603.
- Soltan, P .; Zambitskii, D .; Prisăcaru, C. (1973), Problemas extremos sobre gráficos y algoritmos de su solución (en ruso), Chişinău: Ştiinţa.
enlaces externos
- Gráficos de mediana , sistema de información para inclusiones de clases de gráficos.
- Red , software de red filogenético gratuito. La red genera árboles y redes evolutivos a partir de datos genéticos, lingüísticos y de otro tipo.
- PhyloMurka , software de código abierto para cálculos de redes medianas a partir de datos biológicos.