En matemáticas , especialmente en los campos del álgebra universal y la teoría de grafos , el álgebra de grafos es una forma de dar a un grafo dirigido una estructura algebraica . Fue introducido en (McNulty y Shallon, 1983) , y ha tenido muchos usos en el campo del álgebra universal desde entonces.
Sea
un grafo dirigido, y
un elemento que no está en
. el álgebra de grafos asociado con
es el conjunto
con la multiplicación definida por las siguientes reglas:
si ![{\displaystyle x,y\in V,(x,y)\in E}](//wikimedia.org/api/rest_v1/media/math/render/svg/6d1ddaea054377fadb0f049acbdd087af6a29ba2)
si
.
Esta noción ha hecho posible utilizar los métodos de la teoría de grafos en el álgebra universal y varias otras orientaciones de las matemáticas discretas y ciencias de la computación. El álgebra de grafos se ha utilizado, por ejemplo, en construcciones relativas a dualidades (Davey et al., 2000) , teorías de ecuaciones (Pöschel, 1989), topologías (Lee, 1988) , variedades (Oates-Williams, 1984) , autómatas de estados finitos (Kelarev, Miller y Sokratova, 2005) , máquinas de estados finitos (Kelarev & Sokratova, 2003) , lenguajes de árboles y autómatas de árboles (Kelarev y Sokratova, 2001) etc.
- Davey, Brian A.; Idziak, Pawel M.; Lampe, William A.; McNulty, George F. (2000), «Dualizability and graph algebras», Discrete Mathematics 214 (1): 145-172, ISSN 0012-365X, doi:10.1016/S0012-365X(99)00225-3.
- Delić, Dejan (2001), «Finite bases for flat graph algebras», Journal of Algebra 246 (1): 453-469, ISSN 0021-8693, doi:10.1006/jabr.2001.8947.
- McNulty, George F.; Shallon, Caroline R. (1983), «Inherently nonfinitely based finite algebras», Universal algebra and lattice theory (Puebla, 1982), Lecture Notes in Math. 1004, Berlín, New York: Springer-Verlag, pp. 206-231, doi:10.1007/BFb0063439.
- Kelarev, A.V. (2003), Graph Algebras and Automata, New York: Marcel Dekker, ISBN 0-8247-4708-9.
- Kelarev, A.V.; Sokratova, O.V. (2003), «On congruences of automata defined by directed graphs», Theoretical Computer Science 301 (1–3): 31-43, ISSN 0304-3975, doi:10.1016/S0304-3975(02)00544-3.
- Kelarev, A.V.; Miller, M.; Sokratova, O.V. (2005), «Languages recognized by two-sided automata of graphs», Proc. Estonian Akademy of Science 54 (1): 46-54, ISSN 1736-6046.
- Kelarev, A.V.; Sokratova, O.V. (2001), «Directed graphs and syntactic algebras of tree languages», J. Automata, Languages & Combinatorics 6 (3): 305-311, ISSN 1430-189X.
- Kiss, E.W.; Pöschel, R.; Pröhle, P. (1990), «Subvarieties of varieties generated by graph algebras», Acta Sci. Math. (Szeged) 54 (1–2): 57-75.
- Lee, S.-M. (1988), «Graph algebras which admit only discrete topologies», Congr. Numer. 64: 147-156, ISSN 1736-6046.
- Lee, S.-M. (1991), «Simple graph algebras and simple rings», Southeast Asian Bull. Math. 15 (2): 117-121, ISSN 0129-2021.
- Oates-Williams, Sheila (1984), «On the variety generated by Murskiĭ's algebra», Algebra Universalis 18 (2): 175-177, ISSN 0002-5240, doi:10.1007/BF01198526.
- Pöschel, R (1989), «The equational logic for graph algebras», Z. Math. Logik Grundlag. Math. 35 (3): 273-282, doi:10.1002/malq.19890350311.