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:
"Los grafos medianos surgen naturalmente del estudio de los conjuntos ordenados y de los retículos distributivos discretos, y poseen una extensa literatura."
En filogenia, el grafo de Buneman que representa todos los árboles filogenéticos de máxima parsimonia es un grafo mediano. 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.
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
Cualquier árbol es un grafo mediano. 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.
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. 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
En teoría de retículos, el grafo de un retículo finito tiene un vértice por cada elemento de este, 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:
- 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:
- 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}.
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). 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.
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.
Notas
- Alon, Noga; Yuster, Raphael; Zwick, Uri (1995), «Color-coding», Journal of the Association for Computing Machinery 42 (4): 844-856, doi:10.1145/210332.210337, MR 1411787.
- Avann, S. P. (1961), «Metric ternary distributive semi-lattices», Proceedings of the American Mathematical Society 12 (3): 407-414, doi:10.2307/2034206, MR 0125807.
- Bandelt, Hans-Jürgen (1984), «Retracts of hypercubes», Journal of Graph Theory 8: 501-510, doi:10.1002/jgt.3190080407, MR 0766499.
- Bandelt, Hans-Jürgen; Barthélémy, Jean-Pierre (1984), «Medians in median graphs», Discrete Applied Mathematics 8 (2): 131-142, doi:10.1016/0166-218X(84)90096-9, MR 0743019.
- Bandelt, Hans-Jürgen; Chepoi, V. (2008), «Metric graph theory and geometry: a survey» (PDF), Contemporary Mathematics, archivado desde el original el 25 de noviembre de 2006, consultado el 22 de diciembre de 2009.
- Bandelt, Hans-Jürgen; Forster, P.; Sykes, B. C.; Richards, Martin B. (1 de octubre de 1995), «Mitochondrial portraits of human populations using median networks», Genetics 141 (2): 743-753, PMID 8647407.
- Bandelt, Hans-Jürgen; Forster, P.; Rohl, Arne (1 de enero de 1999), «Median-joining networks for inferring intraspecific phylogenies», Molecular Biology and Evolution 16 (1): 37-48, PMID 10331250.
- Bandelt, Hans-Jürgen; Macaulay, Vincent; Richards, Martin B. (2000), «Median networks: speedy construction and greedy reduction, one simulation, and two case studies from human mtDNA», Molecular Phylogenetics and Evolution 16 (1): 8-28, doi:10.1006/mpev.2000.0792.
- Barthélémy, Jean-Pierre (1989), «From copair hypergraphs to median graphs with latent vértices», Discrete Mathematics 76 (1): 9-28, doi:10.1016/0012-365X(89)90283-5, MR 1002234.
- Birkhoff, Garrett; Kiss, S. A. (1947), «A ternary operation in distributive lattices», Bulletin of the American Mathematical Society 52 (1): 749-752, doi:10.1090/S0002-9904-1947-08864-9, MR 0021540.
- Buneman, P. (1971), «The recovery of trees from measures of dissimilarity», en Hodson, F. R.; Kendall, D. G.; Tautu, P. T., eds., Mathematics in the Archaeological and Historical Sciences, Edinburgh University Press, pp. 387-395.
- Chepoi, V.; Dragan, F.; Vaxès, Y. (2002), «Center and diameter problems in planar quadrangulations and triangulations», Proc. 13th ACM-SIAM Symposium on Discrete Algorithms, pp. 346-355.
- Chepoi, V.; Fanciullini, C.; Vaxès, Y. (2004), «Median problem in some plane triangulations and quadrangulations», Computational Geometry: Theory & Applications 27: 193-210.
- Chiba, N.; Nishizeki, T. (1985), «Arboricity and subgraph listing algorithms», SIAM Journal on Computing 14: 210-223, doi:10.1137/0214017, MR 0774940.
- Chung, F. R. K.; Graham, R. L.; Saks, M. E. (1987), «Dynamic search in graphs», en Wilf, H., ed., Discrete Algorithms and Complexity (Kyoto, 1986), Perspectives in Computing 15, New York: Academic Press, pp. 351-387, MR 0910939.
- Chung, F. R. K.; Graham, R. L.; Saks, M. E. (1989), «A dynamic location problem for graphs» (PDF), Combinatorica 9: 111-132, doi:10.1007/BF02124674.
- Day, William H. E.; McMorris, F. R. (2003), Axiomatic Concensus [sic] Theory in Group Choice and Bioinformatics, Society for Industrial and Applied Mathematics, pp. 91-94, ISBN 0898715512.
- Dress, A.; Hendy, M.; Huber, K.; Moulton, V. (1997), «On the number of vértices and edges of the Buneman graph», Annals of Combinatorics 1 (1): 329-337, doi:10.1007/BF02558484, MR 1630739.
- Dress, A.; Huber, K.; Moulton, V. (1997), «Some variations on a theme by Buneman», Annals of Combinatorics 1 (1): 339-352, doi:10.1007/BF02558485, MR 1630743.
- Duffus, Dwight; Rival, Ivan (1983), «Graphs orientable as distributive lattices», Proceedings of the American Mathematical Society 88 (2): 197-200, doi:10.2307/2044697.
- Feder, T. (1995), Stable Networks and Product Graphs, Memoirs of the American Mathematical Society 555.
- Hagauer, Johann; Imrich, Wilfried; Klavžar, Sandi (1999), «Recognizing median graphs in subquadratic 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, Rome: Accad. Naz. Lincei, pp. 263-268, MR 0543779.
- Imrich, Wilfried; Klavžar, Sandi (1998), «A convexity lemma and expansion procedures for bipartite graphs», European Journal on Combinatorics 19: 677-686, doi:10.1006/eujc.1998.0229, MR 1642702.
- Imrich, Wilfried; Klavžar, Sandi (2000), Product Graphs: Structure and Recognition, Wiley, ISBN 0-471-37039-8, MR 788124.
- Imrich, Wilfried; Klavžar, Sandi; Mulder, Henry Martyn (1999), «Median graphs and triangle-free graphs», SIAM Journal on Discrete Mathematics 12 (1): 111-118, doi:10.1137/S0895480197323494, MR 1666073.
- Itai, A.; Rodeh, M. (1978), «Finding a minimum circuit in a graph», SIAM Journal on Computing 7: 413-423, doi:10.1137/0207033, MR 0508603.
- Jha, Pranava K.; Slutzki, Giora (1992), «Convex-expansion algorithms for recognizing and isometric embedding of median graphs», Ars Combinatorica 34: 75-92, MR 1206551.
- Klavžar, Sandi; Mulder, Henry Martyn (1999), «Median graphs: characterizations, location theory and related structures», Journal of Combinatorial Mathematics and Combinatorial Computing 30: 103-127, MR 1705337.
- Klavžar, Sandi; Mulder, Henry Martyn; Škrekovski, Riste (1998), «An Euler-type formula for median graphs», Discrete Mathematics 187 (1): 255-258, doi:10.1016/S0012-365X(98)00019-3, MR 1630736.
- Knuth, Donald E. (2008), «Median algebras and median graphs», The Art of Computer Programming, IV, Fascicle 0: Introduction to Combinatorial Algorithms and Boolean Functions, Addison-Wesley, pp. 64-74, ISBN 978-0-321-53496-5.
- Mulder, Henry Martyn (1980), «n-cubes and median graphs», Journal of Graph Theory 4 (1): 107-110, doi:10.1002/jgt.3190040112, MR 0558458.
- Mulder, Henry Martyn; Schrijver, Alexander (1979), «Median graphs and Helly hypergraphs», Discrete Mathematics 25 (1): 41-50, doi:10.1016/0012-365X(79)90151-1, MR 0522746.
- Nebesk'y, Ladislav (1971), «Median graphs», Commentationes Mathematicae Universitatis Carolinae 12: 317-325, MR 0286705.
- Škrekovski, Riste (2001), «Two relations for median graphs», Discrete Mathematics 226 (1): 351-353, doi:10.1016/S0012-365X(00)00120-5, MR 1802603.
- Soltan, P.; Zambitskii, D.; Prisăcaru, C. (1973), Extremal problems on graphs and algorithms of their solution (en ruso), Chişinău: Ştiinţa.
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)
| Control de autoridades |
|
|---|
-
Datos: Q3115592