平面グラフ上の可変符号付グラフとその双対グラフ
書誌事項
- タイトル別名
-
- Variable-Signed Graph on a Planar Graph and its Dual Graph
この論文をさがす
説明
ここでは,先に提案した可変符号付グラフ(VSG)が1つの平面グラフ上で与えられる場合,その双対グラフにおける符号関係及び諸性質,特に2極グラフ化への負の弧又は辺の最少個数について述べている.VSGの一般化定義の要点は、頂点に輪を持つ1-グラフGにおいて,すべての頂点及び存在する弧にそれぞれ符号(1,又は-1)を付けた±Gを考える.±G上で,頂点iからjヘ向かう弧の符号をk回符号反転してa_<ji>(k)とし,その弧の両端点の符号をp_i(k)及びp_j(k)とするとき、これら3つの符号の積ρ_<ij>=p_i(k)p_j(k)a_<ji>(k)(1)が,初期設定時k=0の値を保ったまま,各符号を変えうるグラフ±G(k)を可変符号付グラフ(VSG)と呼ぶ.無向グラフ上のVSGの場合はG上における特別な場合のVSGとする.またVSGにおける2極グラフとは,頂点が正頂点と負頂点からなり,負の弧が存在しないVSGのことである.2極グラフ化とは,±G(0)に対し,2極グラフにできるだけ近づくようにカットセットの符号反転操作を加えることであるが,一般には2極グラフにならない.そこで2極グラフ化の目標を次の2つに分けて考えることにする.(1)負の弧又は負の辺をできるだけ少なくする.(2)負の弧を始点とする頂点をできるだけ少なくする.ここでVSGが無向グラフ上で与えられる場合は(1)が目標となる.すべて負の辺からなる無向グラフ上のVSGの2極グラフ化は,既存のグラフ理論における2部グラフ化に対応する.(2)は2極グラフ化の応用面で有効となる.特に,アナログ演算回路におけるインバータの最少構成化やソシオメトリの分野が考えられる.一般に2極グラフ化への解法の手数はNP困難であり,その解決策も試行錯誤の域を出ていない.しかしVSGが平面グラフで与えられる場合は,上記(1)における最少個数を特定できる.本稿では,このことに着目し,平面グラフ上のVSGとその双対グラフを定義し,関連する2,3の性質について述べる.
収録刊行物
-
- 電子情報通信学会総合大会講演論文集
-
電子情報通信学会総合大会講演論文集 1996 5-, 1996-03-11
一般社団法人電子情報通信学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1571980077357548544
-
- NII論文ID
- 110003242414
-
- NII書誌ID
- AN10471452
-
- 本文言語コード
- ja
-
- データソース種別
-
- CiNii Articles
