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

高度连通图及其应用

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

今年研究的目的是阐明高度连通图的循环分布，并将图论的成果应用到其他领域。具体目标是解决美国G. Fan教授1984年关于高连通图中存在汉密尔顿环的猜想，并将图论应用于秘密共享方法。范教授的猜想是，如果每个k点独立集中都存在一个度为图内顶点数1/2以上的顶点满足k连通图的某个性质（k[大于或等于] 2),则该图是哈密顿环，即存在经过所有顶点的环。当k=2时，这个猜想被范教授本人肯定地解决了，但当k[大于或等于]3时，仍然没有解决。通过这项研究，主要研究者与东京理科大学江川教授、庆应义塾大学太田教授、美国G. Chen教授合作解决了这一问题。结果，我们证明了该猜想对于所有 k [大于或等于]3 都成立。它还表明预测无法进一步改善。因此，在上述研究中，有必要考虑不在图的最长循环上的顶点的度数，但本研究的主要研究者在这种考虑的推动下，独立地从图中删除了最长循环我们获得了关于之后剩余的组件上的路径的新知识。我们还发现，这可能会导致一个定理，该定理整合了许多先前已知的有关循环分布的结果。这将是未来研究的一个主题。关于秘密共享方法，我们获得了图论特别是超图论可以有效应用的知识。具体来说，通过将可以恢复分布式秘密的成员集表示为超图的边缘，我们成功地使用超图的某个不变量来评估分布式管理所需的信息量的下限。

项目成果

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)。