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

(Ｗ−グラフに関する研究：未確定な木状接続構造を有するグラフモデルの性質）

【概要】：グラフ（通常のグラフ）G(V,E)は点の有限集合Vと、Vに属する２点間を結ぶ辺の集合Ｅから構成される。本論文では、Ｗ−グラフなるグラフモデルを提案し、その性質について議論している。Ｗ−グラフは通常のグラフG(V,E)と幾つかのwild-components w_１,w_２,･･･,w_ｋ(k>0)の和と定義され、Ω_ｗ(V,E,W)＝G(V,E)∪w_１∪w_２∪･･･∪w_ｋと表わされる。ここで、各wｉはVの部分集合とその生成木の対として定義され、w_ｉ＝{V(w_ｉ),t^（ｉ）｜t^（ｉ）∈T(w_ｉ)}と表わされる。但し、V(w_ｉ) は w_ｉの点集合であり、T(w_ｉ)はV(w_ｉ)上の全ての生成木の集合である。従って、w_ｉは V(w_ｉ)上の任意の一つの生成木を表わしているとも考えられる。Ｗ−グラフに関連した概念にhyper-graphがある。Hyper-graphは点集合とhyper-edgeと呼ばれる点の部分集合の族とからなるが、hyper-edgeとwild-componentとの違いは後者が点の部分集合であると同時にV(w_ｉ)の点を全て含む｜V(w_ｉ)｜−１本の未確定な辺からなる木状接続構造である点にある。従って、Ｗ−グラフは連結性は満たすが，その接続構造には自由度を有するような点部分集合を扱えるという点では通常のグラフの拡張である。しかもhyper-edgeに比べてより具体的特性化が可能である。この意味でＷ−グラフは通常のグラフとhyper-graph との間を埋める新しいモデルであると考えられる。Ｗ−グラフ、hyper-graph に共通する「不確定な接続構造」を扱うことは VLSI-CADやネットワーク設計等にしばしば必要とされることである。Hyper-edgeが持つ抽象度の高さのためにhyper-graphに関する特性化は具体性に乏しい傾向にあるが、Ｗ−グラフはその欠点を補うことができる。

　通常のグラフのcircuit、cutsetに対応して、W-circuitとW-cutsetを定義し、更にW-ring sumなる演算を導入している。二つの W-circuits の W-ring sum が一つのW-circuitになること、同様に、二つのW-cutsetsのW-ring sumが一つのW-cutsetになること、が証明されている。またその性質の重要性にも言及している。更に、Ｗ−グラフの行列表現としてW-incidence行列、W-cutset行列及びW-circuit行列を定義し、各行列の性質を明らかにしている。

　Ｗ−グラフΩ_ｗ(V,E,W)の各wildｰcomponentの木構造を具体的に与えれば、派生グラフと呼ばれる通常のグラフGｄ(V,E')が生成される。その木構造の与え方に応じて種々の派生グラフが生成できる。Ｗ−グラフと派生グラフとの関係について重要な２つの定理を証明している。

最後にＷ−グラフの応用として、二層topological配線において、ビア(Via)数最小化問題がＷ−グラフΩ_ｗ(V,E,W)によりモデル化できることを示している。本モデル化による解法の有用性に言及している。

Abstract　

   In this dissertation, a graph model called a W-graph is presented.　The graph model Ow consists of an ordinary graph G(V,E) and k(>0) wild-components w₁, w₂,..., w_k, and is represented by Ω_ｗ(V,E,W)＝G(V,E)∪w_１∪w_２∪･･･∪w_ｋ. Each wild-component w_{1} is a pair of a vertex set V(w_i) having p_i vertices and a tree containing V(w_i) and p_i-1 edges, and is formally defined as w_ｉ＝{V(w_ｉ),t^（ｉ）｜t^（ｉ）∈T(w_ｉ)} where V(w_i)={v_i1, v_i2, ..., v_ipi}, T(w_i) is a set of all trees containing all vertices in V(w_i) and t⁽ⁱ⁾ is any tree in T(w_i). Hence, a wild-component w_i can represent any tree containing all vertices of V(w_i), where no specific tree is given. Hypergraphs and hyper-edges are related to W-graphs 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 $A_{w}$, we define a W-tree corresponding to the columns of a non-singular major submatrix of A_w. 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 Ω_ｗ(V,E,W) becomes an ordinary graph G_ｄ(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 Chpter 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 a W-graph Ω_ｗ(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.