講演抄録/キーワード |
講演名 |
2013-12-21 13:20
k-Edge-Rigid Body-Hinge Graphs Yuya Higashikawa・Naoki Katoh・○Yuki Kobayashi(Kyoto Univ.)・Adnan Sljoka(York Univ.) COMP2013-53 |
抄録 |
(和) |
本論文では, body-hingeグラフ $G$ が $k$-辺連結 ($k ge 3$) であることは, $G$ が $(k-1)$-edge-rigid であるための必要十分条件であることを示す. ここで, 任意の $(k-1)$ 本の辺をbody-hinge グラフ $G$ から取り除いてできるグラフが剛であるとき, $G$ は $k$-edge-rigid であるとする. さらに, body-hingeグラフ $G$ が $k$-vertex-rigid であるとき, $G$ は $k$-連結であり, $G$ が $(k+2)$-連結であるとき, $h$ を $0le h le k-1$ として, $G$ が $(k-h, h+2)$-rigid であることを示す ($k ge 1$). ここで,任意の$(k-1)$個の頂点をbody-hingeグラフ$G$から取り除いてできるグラフが剛であるとき, $G$ は $k$-vertex-rigid であるとし, 任意の $(i-1)$ 個の頂点を $G$ から取り除いてできるグラフが $j$-edge-rigid であるとき, $G$ は $(i,j)$-rigid であるとする. |
(英) |
In this paper, we prove that a body-hinge graph $G$ is $(k-1)$-edge-rigid if and only if $G$ is $k$-edge-connected ($k ge 3$). A body-hinge graph $G$ is $k$-edge-rigid if removing any $(k-1)$ edges from $G$ results in a graph which is rigid. Furthermore, we prove that a body-hinge graph $G$ is $k$-vertex-connected if $G$ is $k$-vertex-rigid and that a body-hinge graph $G$ is $(k-h, h+2)$-rigid with $h (0le h le k-1)$ if $G$ is $(k+2)$-vertex-connected ($k ge 1$). A body-hinge graph $G$ is $k$-vertex-rigid if removing any $(k-1)$ vertices from $G$ results in a graph which is rigid. A body-hinge graph $G$ is $(i,j)$-rigid if removing any $(i-1)$ vertices from $G$ results in a graph which is $j$-edge-rigid. |
キーワード |
(和) |
Body-hinge フレームワーク / 組合せ剛性理論 / 剛な実現 / 辺連結度 / 冗長な剛性 / / / |
(英) |
Body-hinge frameworks / Combinatorial rigidity / Rigid realization / Edge connectivity / Redundant rigidity / / / |
文献情報 |
信学技報, vol. 113, no. 371, COMP2013-53, pp. 87-91, 2013年12月. |
資料番号 |
COMP2013-53 |
発行日 |
2013-12-13 (COMP) |
ISSN |
Print edition: ISSN 0913-5685 Online edition: ISSN 2432-6380 |
著作権に ついて |
技術研究報告に掲載された論文の著作権は電子情報通信学会に帰属します.(許諾番号:10GA0019/12GB0052/13GB0056/17GB0034/18GB0034) |
PDFダウンロード |
COMP2013-53 |
|