|
|
TO FIND ALL THE 1-FACTORS AND 1-FACTORIAL CONNECTIONS OF A FLOW GRAPH |
Lu Sheng-xun Zhang Li-he |
Hangzhou University |
|
|
Abstract This note gives a method to find all the 1-factors and 1-factorial connections of a flow graph. Let (D) be the set of all subgraphs of a given diagraph G(V, E) and (H) be the set of all subsets of (D). For h1, h2 ∈(H), a multiplication operation being called "star" is denoted by the symbol * and is defined in the following: h1,*h2 ={x∪y/x∈h1, y∈h2, and deg+x∪y(i)<2, deg-x∪y(i)<2}. Theorem Let G(V, E) be a diagraph with vertex set V={1, 2, …,μ}, and let Sk={(k, t)/(k, t)∈ E, t ∈V}. Then all the 1-factors of G(V,E) can be determined by the product of Sk as follows:C=S1*S2*…*Sμ Obviously, if G(V,E) is replaced by G(V, E) is replaced by G(V, E)U(j, i), (j, i) ∉E, then the product gives all the 1-factorial connections from em to j of the diagraph G(V, E).
|
Received: 08 September 1981
|
|
|
|
|
|
|