あらまし

閉曲面上のグラフのハミルトン閉路

小関　健太 

Vol.101 No.3pp.258-261

発行日:2018/03/01

Online ISSN:2188-2355

Print ISSN:0913-5693

種別:小特集　グラフアルゴリズムの最先端

専門分野:

キーワード:
ハミルトン閉路, 四色定理, 平面グラフ, 閉曲面上のグラフ, 

本文:PDF(631.1KB)>>

記事を購入

あらまし:
与えられたグラフにおいて，その全ての頂点をちょうど一度ずつ通る閉路をハミルトン閉路という．平面グラフのハミルトン閉路問題は四色定理への挑戦の過程で提案され，また工学的な応用もあり多くの研究が続けられてきた．特に肯定的な命題として，Tutte(1)は「4連結な平面グラフはハミルトン閉路を持つ」ことを示しており，この証明をベースに以降も多くの研究がなされている．
　本稿では4連結平面グラフにおいてハミルトン閉路を見つけるアルゴリズムのアイデアを述べ，当該分野の研究課題と彩色問題との関係について解説する．

ログイン

 > 

パスワードを忘れた場合は

メニュー

Online ISSN:2188-2355

…ジュニア会員・学生員に
　お勧めの記事