Feedback | Hist | India | Other Sites | Math | Theol | Th Phys | Time | Translit

Catend Study pointer

Algebras of Digraphs and Posets

by Anthony P. Stone


1. Introduction
2. Digraph Algebras
2.1 Digraph algebras of type C(S)
2.2 Abstract algebras of type C(S)
3. Representation of Posets

1. Introduction_______ (Contents)

In the early 1970s, while teaching mathematics at St Stephen's College, Delhi, I had the idea of representing a directed graph as an algebraic expression in its vertices. When the university closed for some weeks because of a student agitation, I developed some (much too complicated) algebras along the lines I had been thinking about. I failed to get the idea published, partly (perhaps) because mathematical journals thought my aim was to advance the theory of algebras.

My aim was really very simple. Instead of referring to the digraph, ao--->---ob, for instance, by some artificial name, it can be referred to as ab, which also tells us all there is to know about it. This is analogous to the situation in analytical geometry, where a particular circle is represented by the equation x^2 + y^2 = r^2, which also contains all there is to know about that circle.

The algebras developed here clearly enable a finite digraph to be held in a computer as a string.

2. Digraph Algebras

2.1 Digraph algebras of type C(S)_______(Contents)

A labelled digraph is completely defined by an ordered pair of sets [V,E], where V is the set of vertices of the digraph and E is the set of its edges. If we have some ordered pair [V,E], the necessary and sufficient conditions for it to be interpretable as a digraph will be taken to be, intuitively,

(1) V x V incls E,
(2) V, E have null intersection,
(3) The elements of V are irreducible (in the sense that even if these elements have some internal structure, this never interacts with any digraph operations).

Edges have the form (a,b), where a,b are vertices. An edge (a,a) is a loop and a sequence of two or more edges of the form (a,b), (b,c), ... , (k,a) is a circuit.

The digraph [V,E] may be interpreted as a set V on which there is a binary relation R, given by

(D) aRb iff (a,b) blng E.

Conversely, a set V with a binary relation R is equivalent to the digraph [V,E], where

E = {(a,b)| a,b blng V, and aRb}.

In a digraph algebra of type C (so named because abc, for instance, represents a chain), we define

(4) [V,E] = [W,F] iff V=W, E=F,
(5) [V,E] + [W,F] = [V union W, E union F],
(6) [V,E][W,F] = [V union W, E union F union (V x W)].

It is easier to work with a simplified notation for digraphs. An isolated vertex will simply be called by its name:

(7) [{a},0] <--> a.

The empty digraph [0,0] will be denoted by 1 (this makes some formulae counterintuitive, but the alternative symbol, 0, is equally counterintuitive in other formulae):

(8) [0,0] <--> 1.

An arbitrary digraph will be denoted by a capital letter, as in

(9) [V(A),E(A)] <--> A.

It is now not difficult to derive the following axioms for an algebra of type C called C(S), say (the significance of the S is explained later):

C1. If A, B blng C(S) then A + B, AB blng C(S),
C2. A + B = B + A,
C3. (A + B) + C = A + (B + C),
C4. (AB)C = A(BC),
C5. A(B + C) = AB + AC, (A + C)B = AB + CB,
C6. A + 1 = 1 + A,
C7. A1 = 1A = A,
C8. ABC = AB + BC + AC.

(Axioms C1-C5 make C(S) a semiring.) Putting C=1 in C5, and later B=1 gives the important absorption rules:

AB + A = AB = AB + B, A + A = A.

We also have A^3 = A^2, 1^2 =1.

Any particular digraph algebra C(S) is generated by 1 and certain vertices which are the elements of the set S. By repeated use of the axioms we obtain a canonical form for any element of C(S):

(10) A = Sum ab + Sum c, (a,b,c blng S, and c =/= a,b),

the summations being over the terms relevant to a, assuming that maximum absorption of terms has taken place. Eq.(10) has an intuitive meaning: any digraph is the sum of its edges between pairs of vertices, together with any isolated vertices. Canonical forms are unique up to the order of terms.

Putting (10) into the ordered pair notation using (5)-(7), (9) gives two important definitions in C(S):

C9. V(A) = {a | a blng S, and a occurs in a canonical form of A},
C10. E(A) = {(a,b) | a,b blng S, and ab is a term in a canonical form of A}.

Inclusion of digraphs will be defined by

(11) [V,E] incls [W,F] iff V incls W, E incls F.

Now suppose A, B are digraphs of C(S) and A incls B. Absorption when A, B are expressed in canonical form gives A + B = A. Conversely, this equation can only hold by absorption. Hence

C11. A incls B iff A + B = A.

An important element of C(S) is the digraph G(S) defined by

(12) G(S) = Sum Sum ab = (Sum a)^2,

the summation being over all the elements of S. G(S) is the complete looped digraph with vertices S, so

[S, S x S] <--> G(S).

Hence any digraph A belongs to C(S) iff G(S) incls A.

The following useful result is easily derived using canonical forms:

AB = A + B + (Sum a)(Sum b), (a blng V(A), b blng V(B)).

2.2 Abstract algebras of type C(S)_______(Contents)

Now suppose we have an algebra built out of 1 and the elements of S, obeying the axioms C1-C8. We also suppose that the definitions C9-C11 are used. Can this abstract algebra C(S) be interpreted as the digraph algebra C(S) derived in 2.1?

THEOREM 1. Necessary and sufficient conditions for an abstract algebra C(S) to be interpretable as a digraph algebra of that type are (i) 1 not blng S, (ii) the sets S and S x S have null intersection, (iii) the elements of S are treated as irreducible.

Proof. Necessity: (i) As a matter of notation, 1 is distinguished from any element of S. (ii) is (2) applied to G(S). (iii) is just (3).
Sufficiency: Given C1-C11 and (i)-(iii), we have to derive (1)-(8) under the correspondence (9). (1) follows from C9, C10. (2) follows from C9, C10, (ii). (3) is (iii). (4)-(8) are easy to obtain.

Theorem 1 is the result we were looking for. Two simple examples are: ab is the digraph ao---->------ob, and a + b is the digraph ao ob.

3. Representation of Posets_______ (Contents)

A poset is an ordered set whose order relation R is irreflexive and transitive. Posets therefore correspond to certain digraphs. A poset in which every pair of elements is relatively ordered is a chain (or linearly ordered set). By repeated application of C8 we have that the product ab...k is always a chain.

An abstract algebra whose elements must be posets has to have a more complicated structure than C(S).

Up to Mathematics page.

Copyright (C) Anthony P. Stone 1996. This material may be freely used, provided the author is acknowledged.

Last updated: 04 January 2005