Álgebra mediana
En matemática, un álgebra mediana es un conjunto con un operador ternario < x,y,z > que satisface los siguientes axiomas, los cuales generalizan la noción de mediana o función mayorante, como una función booleana:
- absorción por la derecha:
- simetría por la derecha:
- simetría por la izquierda:
- transitividad:
El segundo y tercer axioma implican conmutatividad. Es posible (pero no sencillo) demostrar que en presencia de los otros tres, el tercer axioma es redundante. El cuarto axioma implica asociatividad.[1]
Existen otros posibles sistemas axiomáticos, como por ejemplo los siguientes dos axiomas, que también son suficientes:
En un álgebra de Boole, o más general en un retículo distributivo, la función mediana satisface estos axiomas. Por lo tanto, cada álgebra de Boole y cada retículo distributivo forman un álgebra mediana.[2]
Birkhoff y Kiss demostraron que un álgebra mediana con elementos y que satisfacen es un retículo distributivo.[3]
Relación con grafos medianos
Un grafo mediano es un grafo no dirigido en que para cualesquiera tres vértices x, y, z existe un único vértice < x,y,z > que pertenece a los caminos más cortos entre todos los pares conformados por ellos. Cuando un grafo es mediano, la operación < x,y,z > define un álgebra mediana cuyos elementos son los vértices del grafo.
Al revés, en cualquier álgebra mediana, uno puede definir un intervalo [x, z] como el conjunto de elementos y tales que < x,y,z > = y. Se puede definir así un grafo desde un álgebra mediana creando un vértice por cada elemento del álgebra y una arista por cada par (x, z) tal que el intervalo [x, z] no contenga elementos adicionales. Si el álgebra posee la propiedad de que cada intervalo sea finito, entonces este grafo es un grafo mediano, que es exactamente representado por el álgebra, y en que la operación mediana definida por los caminos más cortos en el grafo coinciden con la operación mediana del álgebra original.[4]
Referencias
- Isbell, John R. (Agosto de 1980). «Median Algebra». Trans. Amer. Math. Soc. (en inglés) 260 (2): 319-362. doi:10.2307/1998007.
- Knuth, Donald E. (2008). «Introduction to combinatorial algorithms and Boolean functions». The Art of Computer Programming (en inglés) (Upper Saddle River, NJ: Addison-Wesley). 4.0: 64-74. ISBN 0-321-53496-4.
- Birkhoff, Garret; Kiss (1947). «A ternary operation in distributive lattices». Bull. Amer. Math. Soc. (en inglés) 53: 749-752. doi:10.1090/S0002-9904-1947-08864-9.
- Bandelt, Hand-Jürgen; V. Chepoi (2008). «Metric graph theory and geometry: a survey». Contemporary Mathematics (en inglés). Archivado desde el original el 25 de noviembre de 2006.