平面グラフ上の可変符号付グラフとその双対グラフ
スポンサーリンク
概要
- 論文の詳細を見る
ここでは,先に提案した可変符号付グラフ(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-03-11
著者
関連論文
- 公認認定機関から特別栽培農産物として認証された果実の微生物学的評価
- 神経心理学検査法による痴呆症診断システムの試作
- A-16-3 ひらがなの客観的評価に関する基礎研究
- A-16-2 可変符号付グラフを利用したひらがなの客観的表現法
- 右側頭葉を重点的に活性化するソフトの試作
- 14-1 色刺激による脳波の変化について
- A-16-1 可変符号付グラフを利用したひらがなの一分類法
- 相互抑制回路の周期的パルス電流刺激に対する応答特性
- 刺激パルス幅が興奮性膜の電子回路モデルの刺激-応答特性に及ぼす影響
- 興奮性膜の電子回路モデルの位相遷移曲線による解析
- 独立成分分析と正値時間周波数分布に基づく脳波解析
- 9-5 可変符号付グラフ理論を用いた顔画像の分類
- 可変符号付グラフの2極グラフ化とその応用
- 平面グラフ上の可変符号付グラフにおけ接続変更と符号
- 相互抑制回路の刺激 : 応答特性
- 可変符号付グラフにおける負の弧の最少化と応用への検討
- 可変符号付グラフとその諸性質
- 平面グラフ上の可変符号付グラフとその双対グラフ
- 可変符号付グラフと応用への検討
- ハードウェアニューロンモデルの周期パルス入力に対する応答特性
- 可変符号付グラフ : 一般化定義
- A-19-18 聴覚BCIにおける刺激音の周波数と正答率に関する検討(A-19.福祉情報工学)