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

高度连通图及其应用

• 批准号: 06780286
• 负责人: 斎藤 明
• 金额: $ 0.64万
• 依托单位: Nihon University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1994
• 资助国家: 日本
• 起止时间: 1994 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-06780286/
• 关键词: グラフ; 連結度; ハミルトンサイクル; サイクル分布; 秘密共有法

本年度の研究目的は、高連結度グラフのサイクル分布の解明、及びグラフ理論上の成果の他分野への応用であった。具体的には高連結度グラフのハミルトンサイクルの存在に関して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について予想が成り立つことを証明した。また、予想がこれ以上改善できないことも併せて示した。この結果上記研究において、グラフの最長サイクル上にない頂点の次数を考察が必要になったが、本研究代表者はこの考察を推し進め、上記予想の解決とは独立に、グラフから最長サイクルを除去した後に残る成分上のパスに関して新たな知見を得た。またこれがサイクル分布に関しては従来知られている多くの結果を統合する定理に結び付く可能性があることを見いだした。これは今後の研究課題となる。秘密共有法については、グラフ理論、特にハイパーグラフの理論が有効に応用できるという知見を得た。具体的には、分散管理された秘密を復元できるメンバーの集合をハイパーグラフの辺として表すことにより、分散管理に必要な情報の量の下限をハイパーグラフのある不変量で評価することに成功した。

今年研究的目的是阐明高连接图的周期分布，并将图理论结果应用于其他领域。具体而言，目的是解决1984年美国教授G.Fan对高连接图的存在的预测，并将图理论应用于秘密共享方法。 FAN教授的预测是，如果每个K点独立集满足k连接图的某些特性（k [大于或相等] 2）的顶点为1/2或更多程度的顶点，则该图将具有汉密尔顿循环，也就是说，这是一个通过所有角度传递的循环。当K = 2时，Fan教授本人对该预测进行了积极的解决，但在K [大于或相等] 3中未解决。这位研究人员与东京科学大学的Egawa教授，Keio大学的OTA教授和美国的G. Chen教授一起工作，并通过这项研究解决了问题。结果，我们证明了预测对所有k [大于或相等] 3都是有效的。他还表明，期望无法进一步提高。结果，在上述研究中，有必要考虑到图表最长周期的顶点的顺序，但是本研究者促进了这一考虑，并获得了有关在从图中删除最长循环后保留的组件的路径的新知识，独立于以上预测的解决方案。我们还发现，这可能导致定理，从而整合了许多在周期分布方面已知的结果。这将是未来的研究主题。我们已经获得了一个知识，即图理论，尤其是HyperGraph理论，可以有效地应用于秘密共享方法。具体而言，通过代表可以将分布式托管秘密作为超图的边缘恢复的成员集，我们成功地评估了分布式管理所需的信息的下限，并使用HyperGraph的某些不变式进行了评估。

项目成果

Yoshimi Egawa: "Non-contractible edges in a 3-connected graph" Combinatorica. 15. 1-8 (1995)

Yoshimi Ekawa：“3 连通图中的不可收缩边” Combinatorica。

Guantao Chen: "Graphs with a cycle of length divisible by three" J.Combinatorial Theory(B). 60. 277-292 (1994)

陈观涛：“长度可被三整除的环的图”J.组合理论(B)。