離散幾何における組合せ論的手法
【研究分野】数学一般(含確率論・統計数学)
【研究キーワード】
離散幾何 / 組合せ論 / 三角形分割 / 四角形分割 / グラフ理論 / 木 / 直線描画 / ネットワークフロー / サイクル / グラフ / ハミルトン性 / Johnsonスキーム / 閉包 / 因子 / 分割問題 / 組み合せ論 / 照明問題 / 刑務所問題 / ハミルトングラフ / 単位距離グラフ
【研究成果の概要】
本研究は、3年という研究期間において離散幾何の諸問題の持つ組合せ論的な側面を抽出、分類し、そこから離散幾何における一般的な方法論を構築することを目的としていた。その研究成果のうち、主要なものをいくつか挙げる。
・平面内の有限個の頂点を線分で結び、できるだけ交差する線分が少ないハミルトンサイクルを描画する問題は、見かけ上幾何学的な問題であるが、実はこれが本質的に組合せ論的特性として記述できることを明らかにし、こうした問題を解決する方法論を構築した。
・幾何学的独立木の問題をグラフの独立木の問題の発展形として捉えることで、その組合せ論的特性を明らかにし、幾何学的独立木の問題を扱う方法論を構築した。
・ユークリッド空間内に置かれた有限個の幾何的対象に対し、その両側にほぼ同数が分布するような超平面の存在を問う問題は多数存在するが、これらの問題の組合せ論的特性を明らかにし、それを用いて、特に対象が球面である場合に問題を解決した。
・濃淡画像を白黒2値画像として表現する問題を、グラフ理論におけるネットワークフロー問題に還元する方法論を構築し、それを用いて従来のものとは全く異なるアルゴリズムを得た。
・離散幾何の問題にはグラフの分割問題に帰着させられるものが多数存在することを明らかにし、特に完全グラフ、完全2部グラフの場合における様々な分割問題を解決した。これらは本研究成果のごく一部であり、その全容は研究成果報告書に詳しい。得られた成果の多さと深さを考えれば、本研究は大きな成功を収めたと考えられる。
【研究代表者】