小特集 7. グラフ剛性理論の展開

電子情報通信学会 - IEICE会誌 試し読みサイト
Vol.101 No.3 (2018/3) 目次へ

前の記事へ次の記事へ


グラフアルゴリズムの最先端

小特集 7.

グラフ剛性理論の展開

Recent Advances in Graph Rigidity

谷川眞一

谷川眞一 東京大学大学院情報理工学系研究科数理情報学専攻

Shin-ichi TANIGAWA, Nonmember (Graduate School of Information Science and Technology, The University of Tokyo, Tokyo, 113-8656 Japan).

電子情報通信学会誌 Vol.101 No.3 pp.272-275 2018年3月

©電子情報通信学会2018

abstract

 リンケージやフレームワークといった離散構造物の剛性解析は,構造力学やセンサネットワーク位置同定,分子挙動解析など幅広い分野に現れる基本的問題である.近年の組合せ剛性理論の成果によって剛性や大域剛性といった幾何的・代数的性質に潜む組合せ的側面が解明され,様々なモデルの剛性判定問題が組合せ的グラフアルゴリズムによって効率的に解けることが分かってきている.本稿では,このような剛性解析に対する組合せ的アプローチに焦点を絞り,その代表的成果を紹介する.

キーワード:グラフの剛性,大域剛性,構造力学,分子挙動解析

1.は じ め に

 図1のように平面上に点と直線で描かれたグラフを考えよう.直線を棒材,点を接合部と考えることでこれらのグラフをフレームワーク(枠組み,リンケージ)として捉えることができる.そのようなフレームワークは,頂点の辺の本数やつなぎ方,頂点配置に応じて異なる力学的性質を有する.本稿では主に,静力学的性質つまりフレームワークの剛性を中心に話を進める.

fig_1.png

 我々は経験的に,棒と点のつながり方,つまりフレームワークのグラフがその力学的性質に重要な役割を果たしていることを理解している.図1(a)のような頂点数に比べ辺の本数が少ない場合,フレームワークは辺長を変えることなく様々な変形が可能である.一方,図1(d)のような完全グラフでは動きに自由度のない安定的な状態と考えられる.しかしながら,図1(b)(c)のように頂点数と辺数が同じ場合であってもその剛性は異なることがあり,剛性とグラフの関係を正確に理解することは容易ではないように思われる.面白いことに,平面においては,ある種の一般性の仮定の下において,剛性とグラフの組合せ的構造の関係が完全に理解されており,ある補助2部グラフ上でのマッチング問題を複数回計算することによって剛性判定という幾何的問題を組合せ的に解くことが可能である.本稿では,このような組合せ的アプローチに焦点を絞り,その代表的成果を紹介する.


続きを読みたい方は、以下のリンクより電子情報通信学会の学会誌の購読もしくは学会に入会登録することで読めるようになります。 また、会員になると豊富な豪華特典が付いてきます。


続きを読む(PDF)   バックナンバーを購入する    入会登録


  

電信情報通信学会 - IEICE会誌はモバイルでお読みいただけます。

電子情報通信学会誌 会誌アプリのお知らせ

電信情報通信学会 - IEICE会誌アプリをダウンロード

  Google Play で手に入れよう

本サイトでは会誌記事の一部を試し読み用として提供しています。