Grafo mediano

El mediano de tres vértices en un grafo mediano.

En matemática, y más específicamente en la teoría de grafos, un grafo mediano es un grafo no dirigido en que cualesquiera tres vértices a, b, y c tienen un único mediano. Un mediano es un vértice m(a,b,c) que pertenece a los caminos más cortos entre cualquier par de nodos conformado por a, b, y c.

El concepto de grafo mediano ha sido largamente estudiado, por ejemplo, por Birkhoff y Kiss (1947) o (más explícitamente) por Avann (1961), pero el primer artículo en llamarlos "grafos medianos" aparece en Nebesk'y (1971). Chung, Graham, y Saks escriben:

En filogenia, el grafo de Buneman que representa todos los árboles filogenéticos de máxima parsimonia es un grafo mediano.^[2] Los grafos medianos también aparecen en la teoría de elección social: si un conjunto de alternativas tiene una estructura de un grafo mediano, es posible derivar una elección no ambigua de las mejores preferencias posibles entre ellas.^[3]

En Klavžar y Mulder (1999), Bandelt y Chepoi (2008) y Knuth (2008) se presentan "Surveys" (artículos científicos que presentan estados del arte sobre un tópico determinado) acerca de grafos medianos.

Ejemplos

El mediano m(a,b,c) de tres vértices a, b y c en un árbol, mostrando el subárbol formado por la unión de los caminos más cortos entre dichos vértices.

Cualquier árbol es un grafo mediano.^[4] Para ver esto, note que en un árbol, la unión de los tres caminos más cortos entre cualesquiera tres vértices a, b y c puede ser:

• un camino en sí mismo, en cuyo caso la mediana m(a,b,c) es igual a uno de los nodos a, b o c, dado que alguno de ellos se encontrará entre los otros dos en el camino, o bien
• un subárbol formado por tres caminos conectados en un único nodo central de grado tres, en cuyo caso la mediana m(a,b,c) corresponde a dicho nodo central.

Ejemplos adicionales de grafos medianos son los grafos reticulados (lattice graphs en inglés). En un grafo reticulado, las coordenadas de la mediana m(a,b,c) pueden encontrarse como la mediana de las coordenadas de a, b y c. Por otro lado, en cada grafo mediano uno puede etiquetar los vértices como puntos en un retículo entero de tal manera que las medianas pueden calcularse satisfactoriamente.^[5]

Un grafo cuadrado.

Los grafos cuadrados, que son grafos planares en que todas las superficies interiores son cuadriláteros y todos los vértices interiores tienen cuatro o más aristas incidentes, son otra subclase de grafos medianos.^[6] Un poliominó es un caso especial de un grafo cuadrado, y por lo tanto también forma un grafo mediano.

El grafo simple κ(G) de cualquier grafo no dirigido G tiene un nodo para cada clique (subgrafo completo) de G; dos nodos son enlazados por una arista si el clique correspondiente difiere en un vértice. La mediana de cualesquiera tres cliques puede ser formada utilizando la regla de mayoración para determinar qué vértices de los cliques incluir; el grafo simple es un grafo mediano en que esta regla determina la mediana de cualesquiera tres vértices.

Ningún grafo ciclo de tamaño distinto de cuatro puede ser un grafo mediano, porque cualquiera de esos ciclos tiene tres vértices a, b y c tales que los tres caminos más cortos involucran todas las posibilidades alrededor del ciclo sin lograr una intersección común. Para una ciclo de tamaño tres, no puede haber una mediana.

Definiciones equivalentes

En cualquier grafo, para cualesquiera dos vértices a y b, se define el intervalo de los vértices que se encuentran en los caminos más cortos como:

I(a,b) = {v | d(a,b) = d(a,v) + d(v,b)}.

Un grafo mediano es definido por la propiedad que, para cualesquiera tres vértices a, b y c, estos intervalos se intersecan en un único punto:

Para todo a, b y c, |I(a,b) ∩ I(a,c) ∩ I(b,c)| = 1.

Equivalentemente, para cada tres vértices a, b y c uno puede encontrar un vértice m(a,b,c) tal que las distancias sin peso en el grafo satisfacen las inecuaciones

• d(a,b) = d(a,m(a,b,c)) + d(m(a,b,c),b)
• d(a,c) = d(a,m(a,b,c)) + d(m(a,b,c),c)
• d(b,c) = d(b,m(a,b,c)) + d(m(a,b,c),c)

y m(a,b,c) es el único vértice para el cual esto es verdadero.

También es posible definir grafos medianos como los conjuntos solución de problemas 2-SAT, como los repliegues de hipercubos, como los grafos de álgebras medianas finitas, como los grafos de Buneman de sistemas de corte de Helly, y como los grafos de windex 2.

Retículos distributivos y álgebras medianas

Grafo de un retículo distributivo, dibujado como un diagrama de Hasse.

En teoría de retículos, el grafo de un retículo finito tiene un vértice por cada elemento de éste, y una arista por cada par de elementos en su relación de cobertura. Los retículos son comúnmente visualizados mediante diagramas de Hasse, que son un tipo de grafos, los cuales, especialmente en el caso de los retículos distributivos, tienden a estar estrechamente relacionados con los grafos medianos.

En un retículo distributivo, la siguiente operación mediana autodual de tres parámetros, descrita por Birkhoff:^[7]

m(a,b,c) = (a ∧ b) ∨ (a ∧ c) ∨ (b ∧ c) = (a ∨ b) ∧ (a ∨ c) ∧ (b ∨ c),

satisface ciertos axiomas clave, que son compartidos con la mediana usual de números en el rango desde 0 a 1, y más en general con las álgebras medianas:

• Idempotencia: m(a,a,b) = a para cada a 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 cualquier a, 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.
• Elemento identidad: m(0,a,1) = a para todo a.

La regla distributiva puede ser reemplazada por una regla asociativa:^[8]

• Asociatividad: m(x,w,m(y,w,z)) = m(m(x,w,y),w,z)

La operación mediana puede también utilizarse para definir una noción de intervalos para retículos distributivos:

I(a,b) = {x | m(a,x,b) = x} = {x | a ∧ b ≤ x ≤ a ∨ b}.^[9]

El grafo de un retículo finito distributivo tiene una arista entre cualesquiera dos vértices a y b siempre que I(a,b) = {a,b}. Para cualesquiera dos vértices a y b de este grafo, el intervalo I(a,b) definido en términos de la teoría de retículos de arriba, consiste de los vértices en los caminos más cortos desde a hasta b, y por lo tanto coincide con los intervalos definidos inicialmente como teoría de grafos. Para cualquier a, b, y c, m(a,b,c) es la única intersección de los tres intervalos I(a,b), I(a,c), y I(b,c).^[10] Por lo tanto, el grafo de un retículo distributivo finito es un grafo mediano. Por otro lado, si un grafo mediano G contiene dos vértices 0 y 1 tal que cualquier otro vértice se encuentra en un camino más corto entre los dos (equivalentemente, m(0,a,1) = a para todo a), entonces se puede definir un retículo distributivo en que a ∧ b = m(a,0,b) y a ∨ b = m(a,1,b), de modo que G será el grafo de este retículo.^[11]

Duffus y Rival (1983) caracteriza grafos de retículos distributivos directamente como retracts de hipercubos. En general, cualquier grafo mediano da lugar a una operación ternaria m que satisface idempotencia, conmutatividad y distriutividad, pero posiblemente sin elementos de identidad de un retículo distributivo. Cualquier operación ternaria en un conjunto finito que satisface estas tres propiedades (pero no necesariamente tener elementos 0 y 1) da lugar en el mismo sentido a un grafo mediano.^[12]

Notas

Referencias

Enlaces externos

• Grafos medianos, Sistemas de información para inclusiones de clases de grafos. (en inglés)
• Redes, Software libre de redes filogenéticas. Red que genera árboles filogenéticos y redes a partir de datos genéticos, lingüísticos y de otros tipos. (en inglés)
• PhyloMurka, software open-source para computar redes medianas a partir de datos biológicos.. (en inglés)