閉曲面上のグラフのハミルトン閉路
Vol.101 No.3pp.258-261
発行日:2018/03/01
Online ISSN:2188-2355
Print ISSN:0913-5693
種別:小特集 グラフアルゴリズムの最先端
専門分野:
キーワード:
ハミルトン閉路, 四色定理, 平面グラフ, 閉曲面上のグラフ,
本文:PDF(631.1KB)>>
あらまし:
与えられたグラフにおいて,その全ての頂点をちょうど一度ずつ通る閉路をハミルトン閉路という.平面グラフのハミルトン閉路問題は四色定理への挑戦の過程で提案され,また工学的な応用もあり多くの研究が続けられてきた.特に肯定的な命題として,Tutte(1)は「4連結な平面グラフはハミルトン閉路を持つ」ことを示しており,この証明をベースに以降も多くの研究がなされている.
本稿では4連結平面グラフにおいてハミルトン閉路を見つけるアルゴリズムのアイデアを述べ,当該分野の研究課題と彩色問題との関係について解説する.