WikiDer > Медианная алгебра - Википедия

В математика, а медианная алгебра это набор с тернарная операция ${ Displaystyle langle х, у, г 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) клин (y vee z) клин (z vee x)}$ удовлетворяет этим аксиомам, так что каждая булева алгебра и каждая дистрибутивная решетка образует медианную алгебру.

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

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

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

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

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

• Биркофф, Гарретт; Поцелуй, С.А. (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.

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

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