Graph algebra

From HandWiki

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,[1] and has seen many uses in the field of universal algebra since then.

Definition

Let D = (V, E) be a directed graph, and 0 an element not in V. The graph algebra associated with D has underlying set [math]\displaystyle{ V \cup \{0\} }[/math], and is equipped with a multiplication defined by the rules

  • xy = x if [math]\displaystyle{ x,y \in V }[/math] and [math]\displaystyle{ (x,y) \in E }[/math],
  • xy = 0 if [math]\displaystyle{ x,y \in V \cup \{0\} }[/math] and [math]\displaystyle{ (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 areas of discrete mathematics and computer science. Graph algebras have been used, for example, in constructions concerning dualities,[2] equational theories,[3] flatness,[4] groupoid rings,[5] topologies,[6] varieties,[7] finite-state machines,[8][9] tree languages and tree automata,[10] etc.

See also

Citations

  1. McNulty & Shallon 1983, pp. 206–231.
  2. Davey et al. 2000, pp. 145–172.
  3. Pöschel 1989, pp. 273–282.
  4. Delić 2001, pp. 453–469.
  5. Lee 1991, pp. 117–121.
  6. Lee 1988, pp. 147–156.
  7. Oates-Williams 1984, pp. 175–177.
  8. Kelarev, Miller & Sokratova 2005, pp. 46–54.
  9. Kelarev & Sokratova 2003, pp. 31–43.
  10. Kelarev & Sokratova 2001, pp. 305–311.

Works cited

Further reading