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