高連結度グラフとその応用

点击翻译按钮获取中文摘要

本年度の研究目的は、高連結度グラフのサイクル分布の解明、及びグラフ理論上の成果の他分野への応用であった。具体的には高連結度グラフのハミルトンサイクルの存在に関して1984年に米国G.Fan教授が出した予想の解決と秘密共有法へのグラフ理論の応用を目標としていた。Fan教授の予想は、k-連結グラフ(k【greater than or equal】2)のある性質を満たすk点独立集合それぞれにグラフの頂点数の1/2以上の次数を持つ頂点が存在すれば、そのグラフはハミルトンサイクル、すなわち全ての頂点を通るサイクルが存在する、というものである。この予想はk=2の場合はFan教授自身が肯定的に解決したが、k【greater than or equal】3では未解決であった。本研究代表者は本研究により東京理科大 江川教授、慶応大 太田教授、米国G.Chen教授らと共同で解決に当たった。その結果全てのk【greater than or equal】3について予想が成り立つことを証明した。また、予想がこれ以上改善できないことも併せて示した。この結果上記研究において、グラフの最長サイクル上にない頂点の次数を考察が必要になったが、本研究代表者はこの考察を推し進め、上記予想の解決とは独立に、グラフから最長サイクルを除去した後に残る成分上のパスに関して新たな知見を得た。またこれがサイクル分布に関しては従来知られている多くの結果を統合する定理に結び付く可能性があることを見いだした。これは今後の研究課題となる。秘密共有法については、グラフ理論、特にハイパーグラフの理論が有効に応用できるという知見を得た。具体的には、分散管理された秘密を復元できるメンバーの集合をハイパーグラフの辺として表すことにより、分散管理に必要な情報の量の下限をハイパーグラフのある不変量で評価することに成功した。