释义 |
- Definition
- Applications
- See also
- References
- Further reading
{{about|the mathematical concept of Graph Algebras|"Graph Algebra" as used in the social sciences|Graph algebra (social sciences)}}In mathematics, especially in the fields of universal algebra and graph theory, a graph algebra is a way of giving a directed graph an algebraic structure. It was introduced in {{harv|McNulty|Shallon|1983}}, and has seen many uses in the field of universal algebra since then. Definition Let be a directed graph, and an element not in . The graph algebra associated with is the set equipped with multiplication defined by the rules Applications This notion has made it possible to use the methods of graph theory in universal algebra and several other directions of discrete mathematics and computer science. Graph algebras have been used, for example, in constructions concerning dualities {{harv|Davey|Idziak|Lampe|McNulty|2000}}, equational theories {{harv|Pöschel|1989}}, flatness {{harv|Delić|2001}}, groupoid rings {{harv|Lee|1991}}, topologies {{harv|Lee|1988}}, varieties {{harv|Oates-Williams|1984}}, finite state automata {{harv|Kelarev|Miller|Sokratova|2005}}, finite state machines {{harv|Kelarev & Sokratova|2003}}, tree languages and tree automata {{harv|Kelarev|Sokratova|2001}} etc. See also - Group algebra
- Incidence algebra
- Path algebra
References- {{Citation | last1=Davey | first1=Brian A. | last2=Idziak | first2=Pawel M. | last3=Lampe | first3=William A. | last4=McNulty | first4=George F. | title=Dualizability and graph algebras | doi=10.1016/S0012-365X(99)00225-3 |mr=1743633 | year=2000 | journal=Discrete Mathematics | issn=0012-365X | volume=214 | issue=1 | pages=145–172}}
- {{Citation | last1=Delić | first1=Dejan | title=Finite bases for flat graph algebras | doi=10.1006/jabr.2001.8947 |mr=1872631 | year=2001 | journal=Journal of Algebra | issn=0021-8693 | volume=246 | issue=1 | pages=453–469}}
- {{Citation | last1=McNulty | first1=George F. | last2=Shallon | first2=Caroline R. | title=Universal algebra and lattice theory (Puebla, 1982) | publisher=Springer-Verlag | location=Berlin, New York | series=Lecture Notes in Math. | doi=10.1007/BFb0063439 |mr=716184 | year=1983 | volume=1004 | chapter=Inherently nonfinitely based finite algebras | pages=206–231}}
- {{Citation | last1=Kelarev | first1=A.V. | title=Graph Algebras and Automata | publisher = Marcel Dekker |
year=2003 | place=New York | isbn=0-8247-4708-9 |mr=2064147 }} - {{Citation | last1=Kelarev | first1=A.V. | last2=Sokratova | first2=O.V. | year=2003 | title=On congruences of automata defined by directed graphs | journal=Theoretical Computer Science | volume=301 | issue=1–3 |mr=1975219 | pages=31–43 | issn=0304-3975 | doi=10.1016/S0304-3975(02)00544-3 }}
- {{Citation | last1=Kelarev | first1=A.V. | last2=Miller | first2=M. | last3=Sokratova | first3=O.V. | year=2005 | title=Languages recognized by two-sided automata of graphs | journal=Proc. Estonian Akademy of Science | volume=54 | issue =1 | pages=46–54 |mr=2126358 | issn=1736-6046 }}
- {{Citation | last1=Kelarev | first1=A.V. | last2=Sokratova | first2=O.V. | year=2001 | title=Directed graphs and syntactic algebras of tree languages | journal=J. Automata, Languages & Combinatorics | volume=6 | issue=3 | pages=305–311 |mr=1879773 | issn=1430-189X }}
- {{Citation | last1=Kiss | first1=E.W. | last2=Pöschel | first2=R. | last3=Pröhle | first3=P. | year=1990 | title=Subvarieties of varieties generated by graph algebras | journal=Acta Sci. Math. (Szeged) | volume=54 | issue=1–2 | pages=57–75 |mr=1073419 }}
- {{Citation | last1=Lee | first1=S.-M. | year=1988 | title=Graph algebras which admit only discrete topologies | journal=Congr. Numer. | volume=64 | pages=147–156 |mr=0988675 | issn=1736-6046 }}
- {{Citation | last1=Lee | first=S.-M. | year=1991 | title=Simple graph algebras and simple rings | journal=Southeast Asian Bull. Math. | volume=15 | issue=2 | pages=117–121 |mr=1145431 | issn=0129-2021 }}
- {{Citation | last1=Oates-Williams | first1=Sheila | title=On the variety generated by Murskiĭ's algebra | doi=10.1007/BF01198526 |mr=743465 | year=1984 | journal=Algebra Universalis | issn=0002-5240 | volume=18 | issue=2 | pages=175–177}}
- {{Citation | doi=10.1002/malq.19890350311 | last1=Pöschel | first1=R | year=1989 | title=The equational logic for graph algebras | journal=Z. Math. Logik Grundlag. Math. | volume=35 | issue=3 | pages=273–282 |mr=1000970 }}
Further reading- {{Citation | title=Graph algebras | author=Raeburn, Iain | authorlink=Iain Raeburn | year=2005 | publisher=American Mathematical Society | isbn=978-0-8218-3660-6}}
2 : Universal algebra|Graph theory |