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

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

本研究の目的は、特に連結度の高いグラフに重点を置いてその数学的性質を解明し、また、得られた数学上の結果を情報科学の諸分野に応用することであった。この目的に対して今年度の研究実績は以下のようにまとめられる。1.縮約法で用いられる可縮辺の分布については昔から良く調べられてきたが、今回非可縮辺の分布について多くの知見が得られた。それらは基本的には、グラフの辺の増加に伴い可縮でない辺はある一定数以上には増加しない、という事実を述べている。これは縮約法の応用性について可能性を広げるものであり、しかも従来の可縮辺に着目した研究からは得られないものである。2.米国G. Fan教授によるハミルトンサイクルの存在に関する定理を拡張し、より広いサイクル分布に関して知見を得た。これは本研究申請時の研究目的に挙げられたものである。本研究によりFan教授の条件を満たす高連決度グラフのサイクル分布はほぼ完全に解明された。3.グラフ理論の応用に関しては、秘密共有法との関係について知見が得られた。その成果は、秘密共有法への幅広い応用を考えるには、単純なグラフの構造は貧弱であることを示唆しており、今後の研究はハイパーグラフ、あるいはより広い集合族の上での理論の構築に進むこととなった。以上のように、当初の研究目的に対して、それを上回るような成果が得られた。