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

高度连通图及其应用

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

The purpose of this year's research is to clarify the distribution of high-level links, and to identify other applications of theoretical results. In 1984, Professor G.Fan of the United States proposed a solution to the problem of high degree of connectivity and the application of secret sharing theory. Professor Fan's prediction is that the k-link class (k [greater than or equal] 2) has the property of independent set of k points, and the number of vertices of the class is more than 1/2 of the number of times, and the vertex exists. If k=2, then Fan himself is sure that k [greater than or equal] 3 is not solved. The representatives of this study were Professor Egawa of Tokyo University of Science, Professor Ota of Keizo, and Professor G.Chen of the United States. The result of the test is k [greater than or equal] 3. I want to improve my performance. The results of this study are summarized as follows: 1. The number of vertices in the longest part of the tree is investigated. 2. The representative of this study is to push forward the investigation. 3. The author wants to solve the problem of independence. 4. The longest part of the tree is removed. 3. The number of vertices in the longest part is removed. 4. The new knowledge is obtained. For example, if you want to know more about the distribution, you can use the theorem of integration to find out more about it. Future research topics. The secret sharing method is to use the theory of secret sharing, and the theory of secret sharing is to use the theory of secret sharing. Specific, decentralized management of the collection of information, information.

项目成果

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