平面グラフの線形システムへの応用

平面图在线性系统中的应用

• 批准号: 08640301
• 负责人: 高橋 浩光
• 金额: $ 1.15万
• 依托单位: Okayama Prefectural University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 1996
• 资助国家: 日本
• 起止时间: 1996 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-08640301/
• 关键词: Δ-Y変換; 平面グラフの縮約; 連立1次方程式

実対称行列W=(w_<fj>)に対して,無向グラフG=(V,E)がE={(v_f,v_j)|w_<fj>≠0}を満たすとき,グラフGはWに付随したグラフと言う。Gが2連結平面グラフである場合に連立1次方程式Wx=cを効率よく解く問題を考える。2連結平面グラフに(1)直列辺の除去,(2)並列辺の除去,(3)YをΔに置き換える,(4)ΔをYで置き換える,という4つの変換(以後総称してΔ-Y変換という)をうまく繰り返すことにより一辺のみからなるグラフに縮約できることはすでに解っている。我々はこの事実を利用して上記の連立方程式を解くことを考えた。Wに付随するグラフGにおいてΔ-Y変換をおこなったときG'になったとすると,Wx=cの解とW'x'=c'の解が同じになるようにW',c'を決めかつG'がW 'に付随するグラフであるようにできる。従ってこの方法で解く場合,有効性は2連結平面グラフを1辺に縮約するΔ-Y変換列の長さに依存する。我々は次のような短い縮約Δ-Y変換列を求めるアルゴリズムを提案した。(1)GがG'のマイナ-でありかつG'はすべての頂点の次数が4以下になるようなグラフG'を求める。(2)G'をシリンダー上の格子グラフに埋め込む。(3)シリンダー上の格子グラフを1辺に縮約するΔ-Y変換列を求める。(4)(3)で求めたΔ-Y変換列の中からGの辺のみからなる変換列を求める。これが求める変換列である。各ステップの時間計算量は,頂点数nに対して,1)がO(n),3)が格子グラフの寸法k×mに対してO(k^2m)である。従ってこのアルゴリズムはステップ2)に依存する。多くのグラフでO(n)の大きさの格子グラフに埋め込むことができその場合全体の時間計算量はO(n√<n>)である。

For example, if W=(w_<fj>), G=(V,E), E={(v_f,v_j)}| W_<fj>≠0} G 2-link plane 2. Link plane: (1) removal of in-line edge;(2) removal of parallel edge;(3)Y Δ change;(4)Δ Y change;(4) change (hereinafter referred to as Δ-Y change);(5) change (hereinafter referred to as Δ-Y change);(6) change (hereinafter referred to as Δ-Y change);(7) change (hereinafter referred to as Δ-Y change);(8) change (hereinafter referred to as Δ-Y change);(9) change (hereinafter referred to as Δ-Y change);(10) change (hereinafter referred to as Δ-Y change);(11) change (hereinafter referred to as Δ-Y change (hereinafter referred to as Δ-Y change);(12) change (hereinafter referred to as Δ-Y change (hereinafter referred to as Δ-Y change);(13) change (hereinafter referred to as Δ-Y change (hereinafter referred to as Δ-Y change);(14) change (hereinafter referred to as Δ-Y change I'm going to use this to solve the equation. Wx=c and W'x = c. In this case, the length of the column depends on the length of the column. I'm going to have to go to the next level to reduce the delta-Y transition. (1)G The number of times of the peak of G ' (2)G' (3)The lattice on the top of the column is reduced to Δ-Y. (4)(3) Δ-Yこれが求める変换列である。The calculation quantity of time for each vertex is O(n),1) O(n),3) O(k^2m).従ってこのアルゴリズムはステップ2)に依存する。O (n)= 0 (n)= 0 (n<n>)= 0

项目成果

A.Kanagawa,H.Kawabata and H.Takahashi: "Classification Method by Using the Associatire Memories in Cellular Networks" Proceeding of IFCS-96 : Data Science, Classifiation and Related Method.(to appear)

A.Kanakawa、H.Kawabata 和 H.Takahashi：“使用蜂窝网络中关联存储器的分类方法”IFCS-96 论文集：数据科学、分类和相关方法。（待发表）

Y.Shigehiro,H.Takahashi他: "Automatic Layout Recycling Based on Layait Description and Linear Programming" IEEE TRANS.COMPUTER-AIDED DESIGN. 15,8. 959-967 (1996)

Y. Shigehiro、H. Takahashi 等人：“基于 Layait 描述和线性编程的自动布局回收”IEEE TRANS.计算机辅助设计 15,8 (1996)。

H.Nakahara & H.Takahashi: "An Algorithm for the Solution of a Linear System by Δ-Y Transformations" IEICE TRANS.FUNDAMENTALS. E79-A,7. 1079-1088 (1996)

H.Nakahara 和 H.Takahashi：“通过 Δ-Y 变换求解线性系统的算法”IEICE TRANS.FUNDAMENTALS。E79-A,7 (1996)。

A.Kanagawa,H.Kawabata & H.Takahashi: "Cellular Neural Networks with Multiple-Valued Output and its Application" IEICE TRANS.FUNDAMENTALS. E79-A,10. 1658-1663 (1996)

A.神奈川,H.川端

Y.Takahashi and M.Kato: "On random Clarkson inequalities" Hiroshima Math.J.26. 295-300 (1996)

Y.Takahashi 和 M.Kato：“论随机克拉克森不等式”Hiroshima Math.J.26。