Алгебра графов

В этой статье есть встроенные цитаты , но они не отформатированы должным образом . Пожалуйста, улучшите эту статью, исправив их . Ссылки в скобках устарели ; преобразовать в сокращенные сноски . ( Январь 2021 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения )

В математике , особенно в области универсальной алгебры и теории графов , А граф алгебра представляет собой способ придания Ориентированный граф в алгебраической структуры . Он был представлен в ( McNulty & Shallon, 1983 ) и с тех пор нашел много применений в области универсальной алгебры.

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

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

$xy = x,$ еслии, ${\ displaystyle x, y \ in V}$ ${\ displaystyle (x, y) \ in E}$
$xy = 0,$ еслии. ${\ Displaystyle х, у \ в В \ чашка \ {0 \}}$ ${\ Displaystyle (х, у) \ notin E}$

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

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

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

Процитированные работы [ править ]

Дэйви, Брайан А .; Idziak, Pawel M .; Лампе, Уильям А .; Макналтите, Джордж Ф. (2000), "Dualizability и граф алгебра", дискретная математика , 214 (1): 145-172, DOI : 10.1016 / S0012-365X (99) 00225-3 , ISSN 0012-365X , МР 1743633
Делич, Деяна (2001), "Конечные основы для плоских графов алгебр", журнал алгебры , 246 (1): 453-469, DOI : 10,1006 / jabr.2001.8947 , ISSN 0021-8693 , МР 1872631
Келарев, А.В. (2003), Алгебры и автоматы графов, Нью-Йорк: Марсель Деккер , ISBN 0-8247-4708-9, MR 2064147 - через Интернет-архив
Келарев А.В.; Miller, M .; Сократова О.В. (2005), "Языки, распознаваемые двусторонними автоматами графов", Тр. Эстонская академия наук , 54 (1): 46–54, ISSN 1736-6046 , MR 2126358
Келарев А.В.; Сократова, О.В. (2001), "Направленные графы и синтаксические алгебры языков деревьев", J. Автоматы, языки и комбинаторика , 6 (3): 305–311, ISSN 1430-189X , MR 1879773
Келарев А.В.; Сократова, О.В. (2003), «О конгруэнциях автоматов, определяемых ориентированными графами» (PDF) , Теоретическая информатика , 301 (1–3): 31–43, DOI : 10.1016 / S0304-3975 (02) 00544-3 , ISSN 0304-3975 , MR 1975219
Поцелуй, EW; Pöschel, R .; Прёле, П. (1990), "Подмногообразия многообразий, порожденные алгебрами графов", Acta Sci. Математика. (Сегед) , 54 (1-2): 57–75, MR 1073419
Ли, С.-М. (1988), "Алгебры графов, допускающие только дискретные топологии", Congr. Нумер. , 64 : 147–156, ISSN 1736-6046 , MR 0988675
Ли, С.-М. (1991), "Простые алгебры графов и простые кольца", Southeast Asian Bull. Математика. , 15 (2): 117–121, ISSN 0129-2021 , MR 1145431
Макналти, Джордж Ф .; Шаллон, Кэролайн Р. (1983), «Конечные алгебры с неограниченной базой », Универсальная алгебра и теория решеток (Puebla, 1982) , Lecture Notes in Math., 1004 , Берлин, Нью-Йорк: Springer-Verlag , стр. 206–231 , DOI : 10.1007 / BFb0063439 , ЛВП : 10338.dmlcz / 102157 , ISBN 978-3-540-12329-3, MR 0716184 - через Интернет-архив
Оутс-Williams, Шейла (1984), "О многообразии , порожденной алгебры Мурский в", Алгебра Universalis , 18 (2): 175-177, DOI : 10.1007 / BF01198526 , ISSN 0002-5240 , МР 0743465 , S2CID 121598599
Pöschel, R (1989), "Эквациональная логика для алгебр графов", Z. Math. Logik Grundlag. Математика. , 35 (3): 273-282, DOI : 10.1002 / malq.19890350311 , МР 1000970

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

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