PROPERTIES OF CLASSES OF PATHS.
Wataru Mayeda · Illinois Digital Environment for Access to Learning and Scholarship (University of Illinois at Urbana-Champaign) · 1964
C o n tra c t D A -2 8 -0 4 3 -A M C -0 0 0 7 3 (E ) The r e s e a r c h rep o rted in th is docum ent w as made p o s s ib le by support e x ten d ed to the U n iv e rsity of I ll i n o i s , C o o rd in ated S c ie n c e L a b o ra to ry , jo in tly by th e D epartm ent of the Army, D epartm ent of the N avy (O ffice of N aval R e s e a r c h ) , and the D ep art m ent of the Air F o rce (O ffice of S c ie n tif ic R esearch ) under D epartm ent of Army C o n tra c t D A -2 8 -0 4 3 -A M C -0 0 0 7 3 ( E ) .1 The properties of paths between a pair of vertices in a nonoriented linear graph have been discussed by several papers[1,2,3].This paper gives the properties of a class of paths where each class con sists of all possible paths between a pair of vertices in a nonoriented, non-separable linear graph.It is clear that such prop erties should be known when one synthesizes a s.c.switching network which satisfies a set of given switching functions.An interesting application of classes of paths is to obtain all possible trees in a linear graph which will be shown at the end of the paper.Definitions ' For convenience, G represents a non-oriented,non-separable linear graph which contains no self-loops in this paper.Definition 1 ; Let R be a class of sets r.Then Min.R is defined as a subclass of R which satisfies the following: (1) If 0 (empty set) is in R, 0 is in Min.R;(2) For any r ^ 0 in jR-Min.Rj-1 , there exists rg 4 0 in Min.R such that r c r : and s q'(3) For any r ¿ 0 , and r ¿ 0 in Min.R, r <£ r .