Graph algebra
{{about|the mathematical concept of Graph Algebras|"Graph Algebra" as used in the social sciences|Graph algebra (social sciences)}}
{{Use shortened footnotes|date=May 2021}}
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 by McNulty and Shallon,{{sfn|McNulty|Shallon|1983|loc=[https://archive.org/details/universalalgebra0000unse/page/206 pp. 206–231]}} and has seen many uses in the field of universal algebra since then.
Definition
Let {{math|1=D = (V, E)}} be a directed graph, and {{math|0}} an element not in {{mvar|V}}. The graph algebra associated with {{mvar|D}} has underlying set , and is equipped with a multiplication defined by the rules
- {{math|1=xy = x}} if and ,
- {{math|1=xy = 0}} if and .
Applications
This notion has made it possible to use the methods of graph theory in universal algebra and several other areas of discrete mathematics and computer science. Graph algebras have been used, for example, in constructions concerning dualities,{{sfn|Davey|Idziak|Lampe|McNulty|2000|pp=145–172}} equational theories,{{sfn|Pöschel|1989|pp=273–282}} flatness,{{sfn|Delić|2001|pp=453–469}} groupoid rings,{{sfn|Lee|1991|pp=117–121}} topologies,{{sfn|Lee|1988|pp=147–156}} varieties,{{sfn|Oates-Williams|1984|pp=175–177}} finite-state machines,{{sfn|Kelarev|Miller|Sokratova|2005|pp=46–54}}{{sfn|Kelarev|Sokratova|2003|pp=31–43}}
tree languages and tree automata,{{sfn|Kelarev|Sokratova|2001|pp=305–311}} etc.
See also
Citations
{{Reflist|20em}}
Works cited
{{refbegin|35em}}
- {{Cite journal | title = Dualizability and graph algebras
| last1 = Davey | first1 = Brian A.
| last2 = Idziak | first2 = Pawel M.
| last3 = Lampe | first3 = William A.
| last4 = McNulty | first4 = George F.
| journal = Discrete Mathematics
| year = 2000 | volume = 214 | issue = 1 | pages = 145–172
| doi = 10.1016/S0012-365X(99)00225-3 | issn = 0012-365X | mr = 1743633
| doi-access = free }}
- {{Cite journal | title = Finite bases for flat graph algebras
| last = Delić | first = Dejan
| journal = Journal of Algebra
| year = 2001 | volume = 246 | issue = 1 | pages = 453–469
| doi = 10.1006/jabr.2001.8947 | issn = 0021-8693 | mr = 1872631
| doi-access = free
}}
- {{Cite journal | title = Languages recognized by two-sided automata of graphs
| last1 = Kelarev | first1 = A.V.
| last2 = Miller | first2 = M.
| last3 = Sokratova | first3 = O.V.
| journal = Proc. Estonian Akademy of Science
| year = 2005 | volume = 54 | issue = 1 | pages = 46–54
| issn = 1736-6046 | mr = 2126358
}}
- {{Cite journal | title = Directed graphs and syntactic algebras of tree languages
| last1 = Kelarev | first1 = A.V.
| last2 = Sokratova | first2 = O.V.
| journal = J. Automata, Languages & Combinatorics
| year = 2001 | volume = 6 | issue = 3 | pages = 305–311
| issn = 1430-189X | mr = 1879773
}}
- {{Cite journal | title = On congruences of automata defined by directed graphs
| last1 = Kelarev | first1 = A.V.
| last2 = Sokratova | first2 = O.V.
| journal = Theoretical Computer Science
| year = 2003 | volume = 301 | issue = 1–3 | pages = 31–43
| url = https://eprints.utas.edu.au/157/1/congruences.pdf
| doi = 10.1016/S0304-3975(02)00544-3 | issn = 0304-3975 | mr = 1975219
}}
- {{Cite journal | title = Graph algebras which admit only discrete topologies
| last = Lee | first = S.-M.
| journal = Congr. Numer
| year = 1988 | volume = 64 | pages = 147–156
| issn = 1736-6046 | mr = 0988675
}}
- {{Cite journal | title = Simple graph algebras and simple rings
| last = Lee | first = S.-M.
| journal = Southeast Asian Bull. Math
| year = 1991 | volume = 15 | issue = 2 | pages = 117–121
| issn = 0129-2021 | mr = 1145431
}}
- {{Cite book| chapter = Inherently nonfinitely based finite algebras
| last1 = McNulty | first1 = George F.
| last2 = Shallon | first2 = Caroline R.
| year = 1983
| title = Universal algebra and lattice theory (Puebla, 1982)
| editor1-last = Freese | editor1-first = Ralph S.
| editor2-last = Garcia | editor2-first = Octavio C.
| publisher = Springer-Verlag | location = Berlin, New York City
| volume = 1004 | series = Lecture Notes in Math.
| at = [https://archive.org/details/universalalgebra0000unse/page/206 pp. 206–231]
| url = https://archive.org/details/universalalgebra0000unse | via = Internet Archive
| doi = 10.1007/BFb0063439 | hdl = 10338.dmlcz/102157 | isbn = 978-354012329-3 | mr = 716184
| hdl-access = free
}}
- {{Cite journal | title = On the variety generated by Murskiĭ's algebra
| last = Oates-Williams | first = Sheila
| author-link = Sheila Oates Williams
| journal = Algebra Universalis
| year = 1984 | volume = 18 | issue = 2 | pages = 175–177
| doi = 10.1007/BF01198526 | issn = 0002-5240 | mr = 743465 | s2cid = 121598599
}}
- {{Cite journal | title = The equational logic for graph algebras
| last = Pöschel | first = R.
| journal = Z. Math. Logik Grundlag. Math.
| year = 1989 | volume = 35 | issue = 3 | pages = 273–282
| doi = 10.1002/malq.19890350311 | mr = 1000970
}}
{{refend}}
Further reading
{{refbegin}}
- {{Cite book| title = Graph Algebras and Automata
| last = Kelarev | first = A.V. | year = 2003
| publisher = Marcel Dekker | place = New York City
| url = https://archive.org/details/graphalgebrasaut0000kela | url-access = registration | via = Internet Archive
| isbn = 0-8247-4708-9 | mr = 2064147
| ref = none
}}
- {{cite journal | title = Subvarieties of varieties generated by graph algebras
| last1 = Kiss | first1 = E.W.
| last2 = Pöschel | first2 = R.
| last3 = Pröhle | first3 = P.
| journal = Acta Sci. Math.
| year = 1990 | volume = 54 | issue = 1–2 | pages = 57–75
| mr = 1073419
| ref = none
}}
- {{Cite book| title = Graph algebras
| last = Raeburn | first = Iain | year = 2005
| publisher = American Mathematical Society
| isbn = 978-082183660-6
| ref = none
}}
{{refend}}