Álgebra gráfica

En matemáticas , especialmente en los campos del álgebra universal y la teoría de grafos , un álgebra de grafos es una forma de dar a un grafo dirigido una estructura algebraica . Fue introducida por McNulty y Shallon, ^[1] y ha tenido muchos usos en el campo del álgebra universal desde entonces.

Definición

Sea $D = (V, E)$ un grafo dirigido y $0$ un elemento que no está en $V$ . El álgebra de grafos asociada con $D$ tiene un conjunto subyacente y está equipada con una multiplicación definida por las reglas $V\cup \{0\}$

$xy = x$ siy, $x,y\en V$ $(x,y)\en E$
$xy = 0$ siy. $x,y\en V\cup \{0\}$ $(x,y)\no en E$

Aplicaciones

Esta noción ha hecho posible el uso de los métodos de la teoría de grafos en el álgebra universal y en varias otras áreas de las matemáticas discretas y la informática . Las álgebras de grafos se han utilizado, por ejemplo, en construcciones relativas a dualidades , ^[2] teorías ecuacionales , ^[3] planicidad , ^[4] anillos grupoides , ^[5]topologías , ^[6]variedades , ^[7]máquinas de estados finitos , ^[8]^[9] lenguajes arbóreos y autómatas arbóreos , ^[10] etc.

Véase también

Citas

^ McNulty y Shallon 1983, págs. 206-231.
^ Davey y otros. 2000, págs. 145-172.
^ Pöschel 1989, págs. 273–282.
^ Delić 2001, págs. 453–469.
^ Lee 1991, págs. 117–121.
^ Lee 1988, págs. 147–156.
^ Oates-Williams 1984, págs. 175-177.
^ Kelarev, Miller y Sokratova 2005, págs. 46–54.
^ Kelarev y Sokratova 2003, págs. 31–43.
^ Kelarev y Sokratova 2001, págs. 305–311.

Obras citadas

Davey, Brian A.; Idziak, Pawel M.; Lampe, William A.; McNulty, George F. (2000). "Dualizabilidad y álgebras de grafos". Matemáticas discretas . 214 (1): 145–172. doi : 10.1016/S0012-365X(99)00225-3 . ISSN 0012-365X. MR 1743633.
Delić, Dejan (2001). "Bases finitas para álgebras de grafos planos". Journal of Algebra . 246 (1): 453–469. doi : 10.1006/jabr.2001.8947 . ISSN 0021-8693. MR 1872631.
Kelarev, AV; Miller, M.; Sokratova, OV (2005). "Lenguajes reconocidos por autómatas bilaterales de grafos". Proc. Academia de Ciencias de Estonia . 54 (1): 46–54. ISSN 1736-6046. MR 2126358.
Kelarev, AV; Sokratova, OV (2001). "Grafos dirigidos y álgebras sintácticas de lenguajes arbóreos". J. Automata, Languages & Combinatorics . 6 (3): 305–311. ISSN 1430-189X. MR 1879773.
Kelarev, AV; Sokratova, OV (2003). "Sobre congruencias de autómatas definidos por grafos dirigidos" (PDF) . Theoretical Computer Science . 301 (1–3): 31–43. doi :10.1016/S0304-3975(02)00544-3. ISSN 0304-3975. MR 1975219.
Lee, S.-M. (1988). "Álgebras de grafos que admiten sólo topologías discretas". Congr. Numer . 64 : 147–156. ISSN 1736-6046. MR 0988675.
Lee, S.-M. (1991). "Álgebras de grafos simples y anillos simples". Revista de Matemáticas del Sudeste Asiático . 15 (2): 117–121. ISSN 0129-2021. MR 1145431.
McNulty, George F.; Shallon, Caroline R. (1983). "Álgebras finitas de base no finita inherentemente". En Freese, Ralph S.; García, Octavio C. (eds.). Álgebra universal y teoría de retículos (Puebla, 1982). Lecture Notes in Math. Vol. 1004. Berlín, Nueva York: Springer-Verlag . págs. 206–231. doi :10.1007/BFb0063439. hdl : 10338.dmlcz/102157 . ISBN. 978-354012329-3.MR 0716184 – vía Internet Archive .
Oates-Williams, Sheila (1984). "Sobre la variedad generada por el álgebra de Murskiĭ". Algebra Universalis . 18 (2): 175–177. doi :10.1007/BF01198526. ISSN 0002-5240. MR 0743465. S2CID 121598599.
Pöschel, R. (1989). "La lógica ecuacional para álgebras de grafos". Z. Math. Logik Grundlag. Math . 35 (3): 273–282. doi :10.1002/malq.19890350311. MR 1000970.

Lectura adicional

Kelarev, AV (2003). Álgebras gráficas y autómatas . Ciudad de Nueva York: Marcel Dekker . ISBN 0-8247-4708-9.MR 2064147 – vía Internet Archive .
Kiss, EW; Pöschel, R.; Pröhle, P. (1990). "Subvariedades de variedades generadas por álgebras de grafos". Acta Sci. Math . 54 (1–2): 57–75. MR 1073419.
Raeburn, Iain (2005). Álgebras de grafos . Sociedad Americana de Matemáticas . ISBN 978-082183660-6.