Алгебра графов - Graph algebra

В математика, особенно в областях универсальная алгебра и теория графов, а алгебра графов это способ дать ориентированный граф ан алгебраическая структура. Он был введен в (Макналти и Шаллон, 1983 ), и с тех пор он видел много применений в области универсальной алгебры.

Определение

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

${displaystyle xy = x}$ если ${displaystyle x, yin V}$ и ${displaystyle (x, y) в E}$ ,
${displaystyle xy = 0}$ если ${displaystyle x, yin Vcup {0}}$ и ${displaystyle (x, y) otin E}$ .

Приложения

Это понятие позволило использовать методы теории графов в универсальной алгебре и некоторых других направлениях дискретной математики и информатики. Алгебры графов использовались, например, в конструкциях, касающихся двойственности (Davey et al. 2000 г. ), эквациональные теории (Пешель 1989 ), плоскостность (Делич 2001 ), группоид кольца (Ли 1991 ), топологии (Ли 1988 ), разновидности (Оутс-Уильямс 1984 ), конечные автоматы (Келарев, Миллер и Сократова 2005 ), конечные автоматы (Келарев и Сократова 2003 ), древовидных языков и древовидные автоматы (Келарев и Сократова 2001 ) так далее.

Смотрите также

Процитированные работы

Дэйви, Брайан А .; Idziak, Pawel M .; Лампе, Уильям А .; МакНалти, Джордж Ф. (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
Келарев, А. (2003), Алгебры и автоматы графов, Нью-Йорк: Марсель Деккер, ISBN 0-8247-4708-9, Г-Н 2064147 - через Интернет-архив
Келарев, А.В .; Miller, M .; Сократова, О.В. (2005), «Языки, распознаваемые двусторонними автоматами графов», Proc. Эстонская академия наук, 54 (1): 46–54, ISSN 1736-6046, Г-Н 2126358
Келарев, А.В .; Сократова, О.В. (2001), «Направленные графы и синтаксические алгебры языков деревьев», J. Автоматы, языки и комбинаторика, 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
Kiss, E.W .; Pöschel, R .; Pröhle, P. (1990), "Подмногообразия многообразий, порожденные алгебрами графов", Acta Sci. Математика. (Сегед), 54 (1–2): 57–75, Г-Н 1073419
Ли, С.-М. (1988), "Алгебры графов, допускающие только дискретные топологии", Congr. Нумер., 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-3-540-12329-3, Г-Н 0716184 - через Интернет-архив
Оутс-Уильямс, Шейла (1984), "О многообразии, порожденном алгеброй Мурского", Универсальная алгебра, 18 (2): 175–177, Дои:10.1007 / BF01198526, ISSN 0002-5240, Г-Н 0743465, S2CID 121598599
Pöschel, R (1989), "Эквациональная логика для алгебр графов", Z. Math. Logik Grundlag. Математика., 35 (3): 273–282, Дои:10.1002 / malq.19890350311, Г-Н 1000970

дальнейшее чтение

Реберн, Иэн (2005), Алгебры графов, Американское математическое общество, ISBN 978-0-8218-3660-6