Графовая алгебра

В математике , особенно в области универсальной алгебры и теории графов , алгебра графов — это способ придания ориентированному графу алгебраической структуры . Его представили МакНалти и Шаллон. ^[1] и с тех пор нашел множество применений в области универсальной алгебры.

Определение [ править ]

Пусть $D = (V, E)$ — ориентированный граф , а $0 —$ элемент, не $V.$ принадлежащий Алгебра графов, связанная с $D,$ имеет базовый набор $V\cup \{0\}$ , и снабжен умножением, определяемым правилами

$ху = х$ , если $x,y\in V$ и $(x,y)\in E$ ,
$ху = 0$ , если $x,y\in V\cup \{0\}$ и $(x,y)\notin E$ .

Приложения [ править ]

Это понятие позволило использовать методы теории графов в универсальной алгебре и ряде других областей дискретной математики и информатики . Алгебры графов использовались, например, в конструкциях, касающихся двойственности . ^[2] эквациональные теории , ^[3] плоскостность , ^[4] группоидные кольца , ^[5] топологии , ^[6] сорта , ^[7] конечные автоматы , ^[8]^[9] древовидные языки и древовидные автоматы , ^[10] и т. д.

См. также [ править ]

Цитаты [ править ]

^ МакНалти и Шаллон 1983 , стр. 206–231 .
^ Дэйви и др. 2000 , стр. 145–172.
^ Пёшель 1989 , стр. 273–282.
^ Делич 2001 , стр. 453–469.
^ Ли 1991 , стр. 117–121.
^ Ли 1988 , стр. 147–156.
^ Оутс-Уильямс 1984 , стр. 175–177.
^ Kelarev, Miller & Sokratova 2005 , pp. 46–54.
^ Kelarev & Sokratova 2003 , pp. 31–43.
^ Kelarev & Sokratova 2001 , pp. 305–311.

Цитируемые работы [ править ]

Дэйви, Брайан А.; Идзяк, Павел М.; Лампе, Уильям А.; МакНалти, Джордж Ф. (2000). «Дуализуемость и граф-алгебры» . Дискретная математика . 214 (1): 145–172. дои : 10.1016/S0012-365X(99)00225-3 . ISSN 0012-365X . МР 1743633 .
Делич, Деян (2001). «Конечные базисы плоских графовых алгебр» . Журнал алгебры . 246 (1): 453–469. дои : 10.1006/jabr.2001.8947 . ISSN 0021-8693 . МР 1872631 .
Келарев А.В.; Миллер, М.; Сократова, ОВ (2005). «Языки, распознаваемые двусторонними автоматами графов». Учеб. Эстонская академия наук . 54 (1): 46–54. ISSN 1736-6046 . МР 2126358 .
Келарев А.В.; Сократова, ОВ (2001). «Ориентированные графы и синтаксические алгебры древовидных языков». Дж. Автоматы, Языки и комбинаторика . 6 (3): 305–311. ISSN 1430-189X . МР 1879773 .
Келарев А.В.; Сократова, ОВ (2003). «О сравнениях автоматов, заданных ориентированными графами» (PDF) . Теоретическая информатика . 301 (1–3): 31–43. дои : 10.1016/S0304-3975(02)00544-3 . ISSN 0304-3975 . МР 1975219 .
Ли, С.-М. (1988). «Графовые алгебры, допускающие только дискретные топологии». Конгресс Число . 64 : 147–156. ISSN 1736-6046 . МР 0988675 .
Ли, С.-М. (1991). «Простые алгебры-графики и простые кольца». Юго-Восточно-Азиатский Бык. Математика . 15 (2): 117–121. ISSN 0129-2021 . МР 1145431 .
МакНалти, Джордж Ф.; Шаллон, Кэролайн Р. (1983). «По своей сути неограниченно базируемые конечные алгебры». Во Фризе, Ральф С.; Гарсия, Октавио К. (ред.). Универсальная алгебра и теория решеток (Пуэбла, 1982) . Конспект лекций по математике. Том. 1004. Берлин, Нью-Йорк: Springer-Verlag . стр. 206–231 . дои : 10.1007/BFb0063439 . hdl : 10338.dmlcz/102157 . ISBN 978-354012329-3 . MR 0716184 – через Интернет-архив .
Оутс-Уильямс, Шейла (1984). «О многообразии, порожденном алгеброй Мурского». Алгебра Универсалис . 18 (2): 175–177. дои : 10.1007/BF01198526 . ISSN 0002-5240 . МР 0743465 . S2CID 121598599 .
Пёшель, Р. (1989). «Экциональная логика для графовых алгебр». З. Математика. Логик Грундлаг. Математика . 35 (3): 273–282. дои : 10.1002/malq.19890350311 . МР 1000970 .

Дальнейшее чтение [ править ]

Келарев, А.В. (2003). Алгебры графов и автоматы . Нью-Йорк: Марсель Деккер . ISBN 0-8247-4708-9 . MR 2064147 – через Интернет-архив .
Поцелуй, EW; Пёшель, Р.; Прёле, П. (1990). «Подмногообразия многообразий, порожденных графовыми алгебрами». Акта Наука. Математика . 54 (1–2): 57–75. МР 1073419 .
Реберн, Иэн (2005). Графовые алгебры . Американское математическое общество . ISBN 978-082183660-6 .

[FOOTNOTEMcNultyShallon1983[httpsarchiveorgdetailsuniversalalgebra0000unsepage206_pp._206–231]-1] МакНалти и Шаллон 1983 , стр. 206–231 .

[FOOTNOTEDaveyIdziakLampeMcNulty2000145–172-2] Дэйви и др. 2000 , стр. 145–172.

[FOOTNOTEPöschel1989273–282-3] Пёшель 1989 , стр. 273–282.

[FOOTNOTEDelić2001453–469-4] Делич 2001 , стр. 453–469.

[FOOTNOTELee1991117–121-5] Ли 1991 , стр. 117–121.

[FOOTNOTELee1988147–156-6] Ли 1988 , стр. 147–156.

[FOOTNOTEOates-Williams1984175–177-7] Оутс-Уильямс 1984 , стр. 175–177.

[FOOTNOTEKelarevMillerSokratova200546–54-8] Kelarev, Miller & Sokratova 2005 , pp. 46–54.

[FOOTNOTEKelarevSokratova200331–43-9] Kelarev & Sokratova 2003 , pp. 31–43.

[FOOTNOTEKelarevSokratova2001305–311-10] Kelarev & Sokratova 2001 , pp. 305–311.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]