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