Graph algebra: Difference between revisions

Revision as of 09:03, 31 August 2020

Latest revision as of 10:32, 29 September 2024

(13 intermediate revisions by 12 users not shown)

Line 1:

{{Use Harvard referencing|date=August 2020}}

{{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 inby McNulty and Shallon,{{harvsfn|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'')</math>}} be a directed [[graph (data structure)|graph]], and <{{math>|0</math>}} an element not in <math>{{mvar|V</math>}}. The graph algebra associated with <math>{{mvar|D</math>}} has underlying set <math>V \cup \{0\}</math>, and is equipped with a multiplication defined by the rules

* <{{math>|1=''xy'' = ''x</math>''}} if <math>x,y \in V</math> and <math>(x,y) \in E</math>,

* <{{math>|1=''xy'' = 0</math>}} if <math>x,y \in V \cup \{0\}</math> and <math>(x,y)\notin E</math>.

== Applications ==

This notion has made it possible to use the methods of graph theory in universal algebra and several other directionsareas of [[discrete mathematics]] and [[computer science]]. Graph algebras have been used, for example, in constructions concerning dualities[[Dual (category theory)|dualities]],{{harvsfn|Davey|Idziak|Lampe|McNulty|2000|pp=145–172}}, [[equational theory|equational theories]] ,{{harvsfn|Pöschel|1989|pp=273–282}}, [[flatness (systems theory)|flatness]] ,{{harvsfn|Delić|2001|pp=453–469}}, [[groupoid (algebra)|groupoid]] [[ring (mathematics)|rings]] ,{{harvsfn|Lee|1991|pp=117–121}}, [[topology|topologies]] ,{{harvsfn|Lee|1988|pp=147–156}}, [[variety (universal algebra)|varieties]] ,{{harvsfn|Oates-Williams|1984|pp=175–177}}, [[finite -state automatamachine]] s,{{harvsfn|Kelarev|Miller|Sokratova|2005|pp=46–54}}, [[finite state machine]]s {{harvsfn|Kelarev|Sokratova|2003|pp=31–43}},

tree languages and [[tree automata]] ,{{harvsfn|Kelarev|Sokratova|2001|pp=305–311}} etc.

== See also ==

Line 17:

* [[Incidence algebra]]

* [[Path algebra]]

==Citations==

{{Reflist|20em}}

==Works cited==

{{refbegin|35em}}

*{{CitationCite journal | title = Dualizability and graph algebras

| last1 = Davey | first1 = Brian A.

| last2 = Idziak | first2 = Pawel M.

Line 28 ⟶ 31:

| 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 }}

}}

*{{CitationCite journal | title = Finite bases for flat graph algebras

| last = Delić | first = Dejan | year = 2001

| 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

}}

*{{CitationCite journal | title = Languages recognized by two-sided automata of graphs

*{{Citation| title = ''Graph Algebras and Automata''

| last = Kelarev | first = A.V. | year = 2003

| publisher = [[Marcel Dekker]] | place = New York

| url = https://archive.org/details/graphalgebrasaut0000kela | url-access = registration | via = [[Internet Archive]]

| isbn = 0-8247-4708-9 | mr = 2064147

}}

*{{Citation| title = Languages recognized by two-sided automata of graphs

| last1 = Kelarev | first1 = A.V.

| last2 = Miller | first2 = M.

Line 49 ⟶ 47:

| issn = 1736-6046 | mr = 2126358

}}

*{{CitationCite journal | title = Directed graphs and syntactic algebras of tree languages

| last1 = Kelarev | first1 = A.V.

| last2 = Sokratova | first2 = O.V.

Line 56 ⟶ 54:

| issn = 1430-189X | mr = 1879773

}}

*{{CitationCite journal | title = On congruences of automata defined by directed graphs

| last1 = Kelarev | first1 = A.V.

| last2 = Sokratova | first2 = O.V.

Line 64 ⟶ 62:

| doi = 10.1016/S0304-3975(02)00544-3 | issn = 0304-3975 | mr = 1975219

}}

*{{CitationCite journal | title = SubvarietiesGraph ofalgebras varietieswhich generatedadmit byonly graphdiscrete algebrastopologies

| last1last = KissLee | first1first = ES.W-M.

| journal = Congr. Numer.

| last2 = Pöschel | first2 = R.

| last3year = Pröhle1988 | first3volume = P.64 | pages = 147–156

| journal = Acta Sci. Math. (Szeged)

| year = 1990 | volume = 54 | issue = 1–2 | pages = 57–75

| mr = 1073419

}}

*{{Citation| title = Graph algebras which admit only discrete topologies

| last = Lee | first = S.-M. | year = 1988

| journal = Congr. Numer.

| volume = 64 | pages = 147–156

| issn = 1736-6046 | mr = 0988675

}}

*{{CitationCite journal | title = Simple graph algebras and simple rings

| last = Lee | first = S.-M. | year = 1991

| journal = Southeast Asian Bull. Math.

| year = 1991 | volume = 15 | issue = 2 | pages = 117–121

| issn = 0129-2021 | mr = 1145431

}}

*{{CitationCite 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.

| publisher = [[Springer-Verlag]] | ___location = Berlin, New York

| editor2-last = Garcia | editor2-first = Octavio C.

| publisher = [[Springer-Verlag]] | ___location = Berlin, New York City

| volume = 1004 | series = Lecture Notes in Math.

| pagesat = [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-3-540-12329354012329-3 | mr = 716184

| hdl-access = free

}}

*{{CitationCite journal | title = On the variety generated by Murskiĭ's algebra

| last = Oates-Williams | first = Sheila | year = 1984

| author-link = IainSheila RaeburnOates Williams

| journal = [[Algebra Universalis]]

| year = 1984 | volume = 18 | issue = 2 | pages = 175–177

| doi = 10.1007/BF01198526 | issn = 0002-5240 | mr = 743465 | s2cid = 121598599

}}

*{{CitationCite journal | title = The equational logic for graph algebras

| last = Pöschel | first = R | year = 1989.

| journal = Z. Math. Logik Grundlag. Math.

| year = 1989 | volume = 35 | issue = 3 | pages = 273–282

| doi = 10.1002/malq.19890350311 | mr = 1000970

}}

Line 112 ⟶ 105:

==Further reading==

{{refbegin}}

*{{CitationCite book| title = Graph algebrasAlgebras 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. (Szeged)

| 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

| author-link = Iain Raeburn

| publisher = [[American Mathematical Society]]

| isbn = 978-0-8218-3660082183660-6

| ref = none

}}