A Study on W-graphs : Properties of Graph Models Containing Unspecified Tree Structures

W-グラフに関する研究 : 未確定な木状接続構造を有するグラフモデルの性質

Zhao Hua-an

In this dissertation, a graph model called a W-graph is presented. The graph model Ωw, consists of an ordinary graph G(V, E) and k(> 0) wild-components w1, w2, • • •, wk, and is represented by Ωw(V, E, W ) = G(V, E) ∪ w1 ∪ w2 ∪ • • • ∪ wk. Each wild-component w, is a pair of a vertex set V (wi) having pi vertices and a. tree containing V (wi) and pi - 1 edges, and is formally defined as wi = {V(wi), t(i) | t(i) ∈ T(wi)}, where V(wi) = {vi1, vi2, • • •, vipi}, T(wi) is a set of all trees containing all vertices in V(wi) and t(i) is any tree in T(wi). Hence, a wild-component wi can represent any tree containing all vertices of V(wi), where no specific tree is given. Hypergraphs and hyper-edges are related to W-gra.phs and wild-components. The definition of the former is more general than that, of the latter, which restricting wild-components to trees leads us to more sophisticated discussion, as will be given in this dissertation.

Introduction is given in Chapter 1 and basic definitions are explained in Chapter 2.

In Chapter 3, we introduce the concept. of W-circuits and W-cutsets of a W-graph as an extension of circuits and cutsets of an ordinary graph. Also defined is an operation of W-ring sum in a W-graph. It is proved that. the W-ring sum of two W-circuits is a W-circuit and that the W-ring sum of two W-cutsets is also a W-cutset. Furthermore, W-incidence, W-cutset and W-circuit matrices are introduced. In a W-incidence matrix Aw, we define a W-tree corresponding to the columns of a non-singular major submatrix of Aw. By the W-tree, a fundamental W-cutset matrix and a fundamental W-circuit matrix can be constructed where their rows corresponds to a set of linearly independent W-cutsets and a set of linearly independent W-circuits, respectively.

In Chapter 4, the relation between a W-graphs and its derived graphs is discussed. When structure of each wild-component is specified, a W-graph Ωw(V, E, W) becomes an ordinary graph Gd(V, E') which is called a derived graph. We prove (i) and (ii) as follows: (i) A W-circuit, a W-cutset and a W-tree of a W-graph can be transformed to a circuit (or edge disjoint union of circuits), a cutset (or edge disjoint union of cutsets) and a tree of any derived graph, respectively; (ii) if all elements in a set of W-circuits (W-cutsets, respectively) are linearly independent. under W-ring sum, then all elements in a set of edge disjoint circuits (edge disjoint cutsets) obtained in (i) are also linearly independent. under ring sum.

In Chapter 5, some applications of W-graphs are mentioned. Consider the via-minimization problem in two-layered topological routing that is often used in design of VLSI or printed wiring boards. The problem can be modeled by W-graph #w(V, E, W), where V represents a set of all terminals, E does a set of two-terminal nets and W does a set of multi-terminal nets. With this modeling, the problem is reduced to two problems of W-graphs: the one is detection of planarity of W-graphs and the other is plane drawing of planar W-graphs. At present, the two problems still remain unsolved, we are unable to evaluate our approach by W-graphs explicitly. However, if we can solve the two problems in W-graphs, the advantages of this approach will be shown. In this dissertation, some theorems are provided for testing planar W-graphs for some particular W-graphs.

Finally, unsolved problems on W-graphs left. for future research are stated.

Mathematics [ 410 ]

eng

Copyright(c) by Author

広島大学