Медианная алгебра - Median algebra

В математика, а медианная алгебра это набор с тернарная операция ${\displaystyle \langle x,y,z\rangle }$ удовлетворяющий набору аксиом, обобщающих понятие медианы или функция большинства, как Логическая функция.

Аксиомы

1. ${\displaystyle \langle x,y,y\rangle =y}$
2. ${\displaystyle \langle x,y,z\rangle =\langle z,x,y\rangle }$
3. ${\displaystyle \langle x,y,z\rangle =\langle x,z,y\rangle }$
4. ${\displaystyle \langle \langle x,w,y\rangle ,w,z\rangle =\langle x,w,\langle y,w,z\rangle \rangle }$

Вторая и третья аксиомы подразумевают коммутативность: можно (но не просто) показать, что при наличии трех других аксиома (3) является избыточной. Четвертая аксиома предполагает ассоциативность. Существуют и другие возможные системы аксиом: например, две

• ${\displaystyle \langle x,y,y\rangle =y}$
• ${\displaystyle \langle u,v,\langle u,w,x\rangle \rangle =\langle u,x,\langle w,u,v\rangle \rangle }$

тоже хватит.

В Булева алгебра, или в более общем смысле распределительная решетка, медианная функция ${\displaystyle \langle x,y,z\rangle =(x\vee y)\wedge (y\vee z)\wedge (z\vee x)}$ удовлетворяет этим аксиомам, так что каждая булева алгебра и каждая дистрибутивная решетка образует медианную алгебру.

Биркгоф и Кисс показали, что медианная алгебра с элементами ${\displaystyle 0}$ и ${\displaystyle 1}$ удовлетворение ${\displaystyle \langle 0,x,1\rangle =x}$ это распределительная решетка.

Связь с медианными графиками

А медианный график является неориентированный граф в котором для каждых трех вершин ${\displaystyle x}$, ${\displaystyle y}$, и ${\displaystyle z}$ есть единственная вершина ${\displaystyle \langle x,y,z\rangle }$ это принадлежит кратчайшие пути между любыми двумя из ${\displaystyle x}$, ${\displaystyle y}$, и ${\displaystyle z}$. Если это так, то операция ${\displaystyle \langle x,y,z\rangle }$ определяет медианную алгебру, имеющую вершины графа как ее элементы.

И наоборот, в любой медианной алгебре можно определить интервал ${\displaystyle [x,z]}$ быть набором элементов ${\displaystyle y}$ такой, что ${\displaystyle \langle x,y,z\rangle =y}$. Можно определить граф из медианной алгебры, создав вершину для каждого элемента алгебры и ребро для каждой пары ${\displaystyle (x,z)}$ такой, что интервал ${\displaystyle [x,z]}$ не содержит других элементов. Если алгебра обладает тем свойством, что каждый интервал конечен, то этот граф является медианным графом и точно представляет алгебру в том смысле, что медианная операция, определяемая кратчайшими путями на графе, совпадает с исходной медианной операцией алгебры.

Рекомендации

• Биркофф, Гарретт; Поцелуй, С.А. (1947). «Тернарная операция в распределительных решетках». Бык. Амер. Математика. Soc. 53 (8): 749–752. Дои:10.1090 / S0002-9904-1947-08864-9.
• Исбелл, Джон Р. (Август 1980 г.). «Медианная алгебра». Пер. Амер. Математика. Soc. Американское математическое общество. 260 (2): 319–362. Дои:10.2307/1998007. JSTOR  1998007.
• Кнут, Дональд Э. (2008). Введение в комбинаторные алгоритмы и булевы функции. Искусство программирования. 4.0. Река Аппер Сэдл, Нью-Джерси: Аддисон-Уэсли. С. 64–74. ISBN  0-321-53496-4.

внешняя ссылка

• Доказательство медианной алгебры