Медианная алгебра

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

Аксиомы

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

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

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

тоже хватит.

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

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

с

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

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

Ссылки

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

Внешние ссылки

• Медианное алгебраическое доказательство