Álgebra de grafos

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.

Definición

Sea ${\displaystyle D=(V,E)}$ un grafo dirigido, y ${\displaystyle 0}$ un elemento que no está en ${\displaystyle V}$. el álgebra de grafos asociado con ${\displaystyle D}$ es el conjunto ${\displaystyle V\cup \{0\}}$ con la multiplicación definida por las siguientes reglas:

• ${\displaystyle xy=x}$ si ${\displaystyle x,y\in V,(x,y)\in E}$
• ${\displaystyle xy=0}$ si ${\displaystyle x,y\in V\cup \{0\},(x,y)\notin E}$.

Aplicaciones

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.

Véase también

• Álgebra de grupo
• Álgebra de incidencia
• Álgebra de caminos

Referencias

• 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 .

Bibliografía

• Raeburn, Iain (2005), Graph algebras, American Mathematical Society, ISBN 978-0-8218-3660-6 .

• Datos: Q5597072