# Graph algebra > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Graph_algebra > Markdown URL: https://mediated.wiki/source/Graph_algebra.md > Source: https://en.wikipedia.org/wiki/Graph_algebra > Source revision: 1248410215 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) {{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](/source/mathematics), especially in the fields of [universal algebra](/source/universal_algebra) and [graph theory](/source/graph_theory), a '''graph algebra''' is a way of giving a [directed graph](/source/directed_graph) an [algebraic structure](/source/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](/source/graph_(data_structure)), and {{math|0}} an element not in {{mvar|V}}. The graph algebra associated with {{mvar|D}} has underlying set V \cup \{0\}, and is equipped with a multiplication defined by the rules * {{math|1=''xy'' = ''x''}} if x,y \in V and (x,y) \in E, * {{math|1=''xy'' = 0}} if x,y \in V \cup \{0\} and (x,y)\notin E. == Applications == This notion has made it possible to use the methods of graph theory in universal algebra and several other areas of [discrete mathematics](/source/discrete_mathematics) and [computer science](/source/computer_science). Graph algebras have been used, for example, in constructions concerning [dualities](/source/Dual_(category_theory)),{{sfn|Davey|Idziak|Lampe|McNulty|2000|pp=145–172}} [equational theories](/source/equational_theory),{{sfn|Pöschel|1989|pp=273–282}} [flatness](/source/flatness_(systems_theory)),{{sfn|Delić|2001|pp=453–469}} [groupoid](/source/groupoid_(algebra)) [rings](/source/ring_(mathematics)),{{sfn|Lee|1991|pp=117–121}} [topologies](/source/topology),{{sfn|Lee|1988|pp=147–156}} [varieties](/source/variety_(universal_algebra)),{{sfn|Oates-Williams|1984|pp=175–177}} [finite-state machine](/source/finite-state_machine)s,{{sfn|Kelarev|Miller|Sokratova|2005|pp=46–54}}{{sfn|Kelarev|Sokratova|2003|pp=31–43}} tree languages and [tree automata](/source/tree_automata),{{sfn|Kelarev|Sokratova|2001|pp=305–311}} etc. == See also == * [Group algebra (disambiguation)](/source/Group_algebra_(disambiguation)) * [Incidence algebra](/source/Incidence_algebra) * [Path algebra](/source/Path_algebra) ==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](/source/Discrete_Mathematics_(journal)) | 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](/source/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](/source/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](/source/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](/source/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](/source/Marcel_Dekker) | place = New York City | url = https://archive.org/details/graphalgebrasaut0000kela | url-access = registration | via = [Internet Archive](/source/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](/source/American_Mathematical_Society) | isbn = 978-082183660-6 | ref = none }} {{refend}} Category:Graph theory Category:Universal algebra --- Adapted from the Wikipedia article [Graph algebra](https://en.wikipedia.org/wiki/Graph_algebra) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Graph_algebra?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.