Conventionally, small problems in graphs can be solved using graph networks and
large ones by the adjacency matrix method [1]. In the latter method, one starts with
an adjacency matrix A of the digraph of a network. From it one obtains
matrices A^2, A^3,... where the values of the matrix elements give the number of
paths of specific lengths. The adjacency matrix method is suitable for directed
graphs but how does one find paths in undirected graphs? It turns out that this is
best handled via sequence algebra using a symbolic package. This paper describes
the algorithm and procedure using a simple textbook example. The method is only suitable for
undirected graphs including loops. Computations are made using Macsyma 2.2.1.[3].
2.
Sequence Algebra - A Tutorial Paper
- Huen Y.K. (Date Released 2/2/98, 46 Kbytes)
========================================================
11. Evaluations Of Normc( ) Function
In Macsyma 2.2
- Huen Y.K. (Date Released 17/12/97, 14 Kbytes)
================================================
12.
List Processing In Sequence Algebra
- Huen Y.K. (Date Released 23/12/97, 20 Kbytes)
================================================
========================================================
========================================================
========================================================
========================================================
========================================================
========================================================
========================================================
========================================================
21. The Throwing Power Of
Oddcomp(z).
- by Huen Y.K. (date released : 24.9.97 ) (15 Kbytes).
========================================================
========================================================
========================================================
========================================================
========================================================
========================================================
========================================================
========================================================
1. Introduction
Currently small problems in graph can be solved visually using graph networks
and large ones by adjacency matrix [1]. This paper presents a sequence algebraic
method of solving such problems.
A set of k independent but unordered vertices
v1:sum(1/v(i),i,1,k);
An algebraic representations of independent vertices such as shown in equation (1)
is not useful in graphs since one must start with a representation of the interconnections
of an actual graph network. The next equation represents interconnections by edges
by pairs of symbols for vertices or nodes as shown in equation (2) where 1/(v(i)*v(j))
represents an undirected edge joining the two vertices. This means that if v(i) = v(j), the
term represents a loop. Therefore in sequence algebra, networks are represented
by an edge sequence rather than a node sequence.
....k
====
\............1
. )......------ ..............(1).
/...........v(i)
====....
i = 1
v1:sum(sum(1/(v(i)*v(j),i,1,k),j,1,k);
2. Finding Paths Between Two Nodes
....k........k
==== ====
\..........\..................1
. )..........)......-------------- ..............(2).
/........../..............v(i)*v(j)
==== ====....
i = 1....j = 1
To demonstrate how to count paths of various lengths from a graph we use a simple
textbook example drawn from reference [1]. Figure 1 shows
the digraph with five nodes as v(1), v(2), v(3), v(4), and v(5). Its adjacency matrix is
given by equation (3).
v1--------------------v2
Fig.1 - Digraph Network.
0.................................0
^..\.........................^...^^
|........\................/.........|.......\
|.............\....../..............|............\
|...............X.................|...............0 v3
|............./.....\...............|............^
|......../................\.........|........./
|../...........................v...|..../
0<--------------------0
v5-------------------v4
A naive representation where v1,v2,... represent nodes and 0 represents node-point. X represents cross-over and symbols like / and \ represent edges, and ^, <, >, V are directed arrowheads. ----> represents a directed edge.
The adjacency matrix A of the above network is represented by equation (4) each array element
of 1 represents an edge connecting the vertex i (from row i) to vertex j (column j).
A =
[ 0 0 0 1 0 ]
In the adjacency method, to work out elements in A^2, A^3,.... we use the relation aij^2=
sum(aik*akj,k=1,n). Unfortunately this is quite tedious since this is not a standard
matrix operation as a digraph has directed edges. Equation (5) shows the actual
adjacency matrix for A, i.e. for paths containing single edges whereas
equation (6) is the adjacency matrix for A^2 i.e. for paths containing two edges.
[ 0 0 1 0 0 ]
[ 0 1 0 0 0 ].................................(4).
[ 0 1 1 0 1 ]
[ 1 1 0 0 0 ]
A =
[ 0 0 0 1 0 ]
[ 0 0 1 0 0 ]
[ 0 1 0 0 0 ].................................(5).
[ 0 1 0 0 1 ]
[ 1 1 0 0 0 ]
In equation (2), the element of 2 represents the number of paths of length 2
from vertex i = 4 to vertex j = 2 which are of course v4-v3-v2 and v4-v5-v2.
Similarly the element of 1 represents a single path of length 2 such as
given by v1-v2.
A^2 =
[ 0 1 1 0 1 ]
[ 0 1 0 0 0 ]
[ 0 0 1 0 0 ]..................................(6).
[ 1 2 1 0 0 ]
[ 0 0 1 1 0 ]
The above adjacency matrices assume a directed graph network and is thus
not useful for finding paths of undirected graph network. In section (3) we will
show how to count paths of an undirected graph using figure 1.
3. Finding Undirected Paths Using A Symbolic Package
From figure 1, the sequence representation for undirected edges are given by
equation (7):
Graph_network:1/(v(1)*v(4))+1/(v(2)*v(3))+1/(v(3)*v(2))+1/(v(4)*v(2))+1/(v(4)*v(3))
+1/(v(4)*v(5))+1/(v(5)*v(1))+1/(v(5)*v(2));
Graph_network =
Any of the term in the equation (7) above represents an undirected edge linking
two vertices. For undirect edges, the path is counted twice, i.e., forward and
backward. The member_terms function below will search an undirected graph
network represented by x2 for a given subpattern given by x1. If it exists, this
predicate will return true, otherwise false. We convert this predicate into an MMF
which will suppress terms which do not match any pattern [2].
.....1...............1..............1...............1...............1..............1...............2
--------- + -------- + -------- + -------- + -------- + -------- + --------....(7).
v(4) v(5)...v(2) v(5)...v(1) v(5)...v(3) v(4)...v(2) v(4)...v(1) v(4)...v(2) v(3)
member_terms(x1,x2):=(if op(x1) # "+" then x1:[x1],if op(x2) # "+" then x2:[x2],block
([args_x1:args(x1), args_x2:args(x2), ans:true],for args:args_x1 next rest(args) unless
args=[] do (if not member(first(args),args_x2) then return(ans:false)),return(ans)))$
x1:1/(v(1)*v(4))+1/(v(2)*v(3))+1/(v(3)*v(2))+1/(v(4)*v(2))+1/(v(4)*v(3))
+1/(v(4)*v(5))+1/(v(5)*v(1))+1/(v(5)*v(2));
(1/(v(4) * v(5))) + (1/(v(2) * v(5))) + (1/(v(1) * v(5)))
+ (1/(v(3) * v(4))) + (1/(v(2) * v(4))) + (1/(v(1) * v(4)))
+ (2/(v(2) * v(3))).........................................(8).
x3:makelist(makelist(makelist(1/(v(i)*v(k))+1/(v(k)*v(j)),k,1,5),i,1,5),j,1,5);
The output sequence in equation (9) contains a compound list nested three levels deep in the form:
(list1(list2(list3))) where each list contains 5 items.
[[[(2/(v^2(1))), (2/(v(1) * v(2))), (2/(v(1) * v(3))), (2/(v(1) * v(4))), (2/(v(1) * v(5)))],
[(1/(v(1) * v(2))) + (1/(v^2(1))), (1/(v(1) * v(2))) + (1/(v^2(2))), (1/(v(2) * v(3))) + (1/(v(1) * v(3))),
(1/(v(2) * v(4))) + (1/(v(1) * v(4))), (1/(v(2) * v(5))) + (1/(v(1) * v(5)))],
[(1/(v(1) * v(3))) + (1/(v^2(1))), (1/(v(2) * v(3))) + (1/(v(1) * v(2))), (1/(v(1) * v(3))) + (1/(v^2(3))),
(1/(v(3) * v(4))) + (1/(v(1) * v(4))), (1/(v(3) * v(5))) + (1/(v(1) * v(5)))],
[(1/(v(1) * v(4))) + (1/(v^2(1))), (1/(v(2) * v(4))) + (1/(v(1) * v(2))),
(1/(v(3) * v(4))) + (1/(v(1) * v(3))), (1/(v(1) * v(4))) + (1/(v^2(4))),
(1/(v(4) * v(5))) + (1/(v(1) * v(5)))], [(1/(v(1) * v(5))) + (1/(v^2(1))),
(1/(v(2) * v(5))) + (1/(v(1) * v(2))), (1/(v(3) * v(5))) + (1/(v(1) * v(3))),
(1/(v(4) * v(5))) + (1/(v(1) * v(4))), (1/(v(1) * v(5))) + (1/(v^2(5)))]],
[[(1/(v(1) * v(2))) + (1/(v^2(1))), (1/(v(1) * v(2))) + (1/(v^2(2))),
(1/(v(2) * v(3))) + (1/(v(1) * v(3))), (1/(v(2) * v(4))) + (1/(v(1) * v(4))),
(1/(v(2) * v(5))) + (1/(v(1) * v(5)))], [(2/(v(1) * v(2))), (2/(v^2(2))), (2/(v(2) * v(3))),
(2/(v(2) * v(4))), (2/(v(2) * v(5)))], [(1/(v(1) * v(3))) + (1/(v(1) * v(2))),
(1/(v(2) * v(3))) + (1/(v^2(2))), (1/(v(2) * v(3))) + (1/(v^2(3))), (1/(v(3) * v(4))) + (1/(v(2) * v(4))),
(1/(v(3) * v(5))) + (1/(v(2) * v(5)))], [(1/(v(1) * v(4))) + (1/(v(1) * v(2))),
(1/(v(2) * v(4))) + (1/(v^2(2))), (1/(v(3) * v(4))) + (1/(v(2) * v(3))), (1/(v(2) * v(4))) + (1/(v^2(4))),
(1/(v(4) * v(5))) + (1/(v(2) * v(5)))], [(1/(v(1) * v(5))) + (1/(v(1) * v(2))),
(1/(v(2) * v(5))) + (1/(v^2(2))), (1/(v(3) * v(5))) + (1/(v(2) * v(3))),
(1/(v(4) * v(5))) + (1/(v(2) * v(4))), (1/(v(2) * v(5))) + (1/(v^2(5)))]],
[[(1/(v(1) * v(3))) + (1/(v^2(1))), (1/(v(2) * v(3))) + (1/(v(1) * v(2))),
(1/(v(1) * v(3))) + (1/(v^2(3))), (1/(v(3) * v(4))) + (1/(v(1) * v(4))),
(1/(v(3) * v(5))) + (1/(v(1) * v(5)))], [(1/(v(1) * v(3))) + (1/(v(1) * v(2))),
(1/(v(2) * v(3))) + (1/(v^2(2))), (1/(v(2) * v(3))) + (1/(v^2(3))), (1/(v(3) * v(4))) + (1/(v(2) * v(4))),
(1/(v(3) * v(5))) + (1/(v(2) * v(5)))], [(2/(v(1) * v(3))), (2/(v(2) * v(3))), (2/(v^2(3))),
(2/(v(3) * v(4))), (2/(v(3) * v(5)))], [(1/(v(1) * v(4))) + (1/(v(1) * v(3))),
(1/(v(2) * v(4))) + (1/(v(2) * v(3))), (1/(v(3) * v(4))) + (1/(v^2(3))), (1/(v(3) * v(4))) + (1/(v^2(4))),
(1/(v(4) * v(5))) + (1/(v(3) * v(5)))], [(1/(v(1) * v(5))) + (1/(v(1) * v(3))),
(1/(v(2) * v(5))) + (1/(v(2) * v(3))), (1/(v(3) * v(5))) + (1/(v^2(3))),
(1/(v(4) * v(5))) + (1/(v(3) * v(4))), (1/(v(3) * v(5))) + (1/(v^2(5)))]],
[[(1/(v(1) * v(4))) + (1/(v^2(1))), (1/(v(2) * v(4))) + (1/(v(1) * v(2))),
(1/(v(3) * v(4))) + (1/(v(1) * v(3))), (1/(v(1) * v(4))) + (1/(v^2(4))),
(1/(v(4) * v(5))) + (1/(v(1) * v(5)))], [(1/(v(1) * v(4))) + (1/(v(1) * v(2))),
(1/(v(2) * v(4))) + (1/(v^2(2))), (1/(v(3) * v(4))) + (1/(v(2) * v(3))), (1/(v(2) * v(4))) + (1/(v^2(4))),
(1/(v(4) * v(5))) + (1/(v(2) * v(5)))], [(1/(v(1) * v(4))) + (1/(v(1) * v(3))),
(1/(v(2) * v(4))) + (1/(v(2) * v(3))), (1/(v(3) * v(4))) + (1/(v^2(3))), (1/(v(3) * v(4))) + (1/(v^2(4))),
(1/(v(4) * v(5))) + (1/(v(3) * v(5)))], [(2/(v(1) * v(4))), (2/(v(2) * v(4))), (2/(v(3) * v(4))),
(2/(v^2(4))), (2/(v(4) * v(5)))], [(1/(v(1) * v(5))) + (1/(v(1) * v(4))),
(1/(v(2) * v(5))) + (1/(v(2) * v(4))), (1/(v(3) * v(5))) + (1/(v(3) * v(4))),
(1/(v(4) * v(5))) + (1/(v^2(4))), (1/(v(4) * v(5))) + (1/(v^2(5)))]], [[(1/(v(1) * v(5))) + (1/(v^2(1))),
(1/(v(2) * v(5))) + (1/(v(1) * v(2))), (1/(v(3) * v(5))) + (1/(v(1) * v(3))),
(1/(v(4) * v(5))) + (1/(v(1) * v(4))), (1/(v(1) * v(5))) + (1/(v^2(5)))],
[(1/(v(1) * v(5))) + (1/(v(1) * v(2))), (1/(v(2) * v(5))) + (1/(v^2(2))),
(1/(v(3) * v(5))) + (1/(v(2) * v(3))), (1/(v(4) * v(5))) + (1/(v(2) * v(4))),
(1/(v(2) * v(5))) + (1/(v^2(5)))], [(1/(v(1) * v(5))) + (1/(v(1) * v(3))),
(1/(v(2) * v(5))) + (1/(v(2) * v(3))), (1/(v(3) * v(5))) + (1/(v^2(3))),
(1/(v(4) * v(5))) + (1/(v(3) * v(4))), (1/(v(3) * v(5))) + (1/(v^2(5)))],
[(1/(v(1) * v(5))) + (1/(v(1) * v(4))), (1/(v(2) * v(5))) + (1/(v(2) * v(4))),
(1/(v(3) * v(5))) + (1/(v(3) * v(4))), (1/(v(4) * v(5))) + (1/(v^2(4))), (1/(v(4) * v(5))) + (1/(v^2(5)))],
[(2/(v(1) * v(5))), (2/(v(2) * v(5))), (2/(v(3) * v(5))), (2/(v(4) * v(5))), (2/(v^2(5)))]]]..........(9).
sum(sum(sum(part(part(part(x3,k),i),j)*(member_terms(part(part(part(x3,k),i),j),x1
)-false)/(true-false),k,1,5),i,1,5),j,1,5);
The above program line will count all paths with lengths of 2 in the figure 1 as given in
equation (10).
....10..............6.................6................6................8...............8..............4
--------- + --------- + --------- + --------- + ---------+ --------- + ---------...........(10).
v(4) v(5)....v(2) v(5)....v(1) v(5)....v(3) v(4)....v(2) v(4)....v(1) v(4)....v(2) v(3)
The above output does not display the intermediate node along each path. So
the program line is modified by including f(k,i,j) to display of path information. Since
the matching
is for undirected edges, the orders of i,j, and k are not important. Note that in the
program line below, the MMF = member_terms(part(part(part(x3,k),i),j),x1
)-false)/(true-false) which will return the integer value of 1 if there is a match and
0 otherwise. This means that terms which do not match will be suppressed.
sum(sum(sum(part(f(k,i,j)*part(part(x3,k),i),j)*(member_terms(part(part(part(x3,k),i),j),x1
)-false)/(true-false),k,1,5),i,1,5),j,1,5);
f(5, 4, 2)*((1/(v(2) * v(5))) + (1/(v(2) * v(4))))
+ f(5, 4, 1) *((1/(v(1) * v(5))) + (1/(v(1) * v(4))))
+ f(5, 3, 4)*((1/(v(4) * v(5))) + (1/(v(3) * v(4))))
+ f(5, 2, 4)*((1/(v(4) * v(5))) + (1/(v(2) * v(4))))
+ f(5, 1, 4)*((1/(v(4) * v(5))) + (1/(v(1) * v(4))))
+ f(4, 2, 5)* ((1/(v(4) * v(5))) + (1/(v(2) * v(5))))
+ f(2, 4, 5) * ((1/(v(4) * v(5))) + (1/(v(2) * v(5))))
+ f(4, 1, 5) * ((1/(v(4) * v(5))) + (1/(v(1) * v(5))))
+ f(1, 4, 5)* ((1/(v(4) * v(5))) + (1/(v(1) * v(5))))
+ f(3, 5, 4) * ((1/(v(4) * v(5))) + (1/(v(3) * v(4))))
+ f(2, 5, 4) * ((1/(v(4) * v(5))) + (1/(v(2) * v(4))))
+ f(1, 5, 4)* ((1/(v(4) * v(5))) + (1/(v(1) * v(4))))
+ f(2, 1, 5) * ((1/(v(2) * v(5))) + (1/(v(1) * v(5))))
+ f(1, 2, 5) * ((1/(v(2) * v(5))) + (1/(v(1) * v(5))))
+ f(4, 5, 2)* ((1/(v(2) * v(5))) + (1/(v(2) * v(4))))
+ f(4, 5, 1) * ((1/(v(1) * v(5))) + (1/(v(1) * v(4))))
+ f(3, 2, 4) * ((1/(v(3) * v(4))) + (1/(v(2) * v(4))))
+ f(2, 3, 4)* ((1/(v(3) * v(4))) + (1/(v(2) * v(4))))
+ f(3, 1, 4) * ((1/(v(3) * v(4))) + (1/(v(1) * v(4))))
+ f(1, 3, 4) * ((1/(v(3) * v(4))) + (1/(v(1) * v(4))))
+ f(2, 1, 4)* ((1/(v(2) * v(4))) + (1/(v(1) * v(4))))
+ f(1, 2, 4) * ((1/(v(2) * v(4))) + (1/(v(1) * v(4))))
+ ((2 * f(3, 3, 2))/(v(2) * v(3)))
+ ((2 * f(2, 2, 3))/(v(2) * v(3)))................................(11).
The paths reported by equation (10) and equation (11) are checked by physical
counting using the graph network in figure 1 and are found to be correct. We give only
one check example involving vertices v(4) and v(5) where 5 lines in equation (11)
are highlighted. Each line represent 2 undirected paths and so there are 10 paths
as for this pair of vertices as reported in equation (10).
One can use the same method to find paths with higher number of nodes but
one must be aware that the nested levels will increase correspondingly. The
problem of limitations in memory resources for large graph network will have to be
addressed just like in the matrix method.
4. Conclusions
This paper describes briefly an algebraic method for finding the number of
undirected paths of a graph network given by figure 1. Once
the graph is known, finding these paths can be automated. The results are
presented in a sequence which is easier to read than that from an adjacency
matrix. It is especially difficult to read high order adjacency matrix because
only the row and column numbers of the matrix are accessible unless one
is willing to work backward. In the case of the present method, the whole
path can be printed out together with the path counts. The present paper
has not addressed the search for paths of digraphs. This will be treated in
a separate short communication.
5 References
Since no standard textbooks have been published on the topic of sequence algebra,
we include more references than is deemed necessary in a research paper. Readers
who have no previous background in this topic will find some of these papers helpful.
1. Grassman W.K. and Tremblay J.P.( ): Logic And Discrete Mathematics -
A Computer Science Perspective, Prentice-Hall, chapter 7, graphs and tree, pp 353 to
421.
3. Macsyma: Symbolic/numeric/graphical mathematics software, Mathematics and
System Reference Manual, 16th edition, relevant sections.
Published Papers:
4. Huen Y.K.: A Matrix Map for Prime and Non-prime Numbers, INT. J. Math. Educ. Sci.
Technol., 1994, VOL. 25, NO.6, pp 913-920.
5. Huen Y.K.: Some Interesing Properties Of The Natural Number System, Int. J. Math. Educ.
Sci. Technol., 1996, VOL.27, NO. 5, 685-691.
6. Huen Y.K.: Visual algebra and its applications, INT. J. Math. Educ. Sci. Technol.,
1997, VOL.28, NO.3, pp 333-344.
7. Huen Y.K.: The twin prime problem revisited, INT. J. Math. Educ. Sci. Technol.,1997, VOL.28,
NO. 6, pp 825-834.
8. Huen Y.K.: Is Pie Periodic?, INT. J. Math. Educ. Sci. Technol.,199?,VOL.??,NO.?,???-???. (in the press).
9. Huen Y.K.: Final value theorem in number sequences., INT. J. Math. Educ. Sci. Technol.,199?,VOL.-??,NO.?,???-???. (accepted).
Papers posted in this website.