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

高度连通图及其应用

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

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

The purpose of this study is to clarify the mathematical properties of information science and to obtain mathematical results. This year's research results are as follows: 1. In the past, we have been able to adjust the distribution of contractible parts, but now we have been able to adjust the distribution of contractible parts. For example, if you want to increase your weight, you can increase your weight by a certain amount. This is the first time I've ever seen a person who's been in a position to do something like this. 2. G. Professor Fan's theorem on the existence of a group of objects is extended and the distribution of objects is known. The purpose of this study is to improve the quality of the product. In this study, Fan's condition was completely explained. 3. The relationship between the theory and the secret sharing method is related to the relationship between the theory and the secret sharing method. The results of this study are as follows: (1) The structure of the system is weak,(2) The structure of the system is weak,(3) The structure of the system is weak,(4) The structure of the system is weak,(5) The structure of the system is weak. The above research objectives are achieved.

项目成果

X. Yu: "Noncontractible edges in 3-connected graphs" Combinatorica. 15. 357-364 (1995)

X. Yu：“3 连通图中的不可收缩边” Combinatorica。

A. Saito: "Relative length of long paehs and cycles in graphs with large degree sums" J. Graph Theory. 20. 213-225 (1995)

A. Saito：“具有大度数和的图中长 paeh 和循环的相对长度”J. 图论。

A. Saito: "Essential independent sets and hamiltonian cycles" J. Graph Theory. 21. 243-250 (1996)

A. Saito：“基本独立集和哈密顿循环”J. 图论。