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

高度连通图及其应用

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

縮約法は連結度の高いグラフの性質を調べる際に有力な道具となる。本年度はこの縮約法を用いて、グラフのサイクル分布に関する問題の解決を試みた。またグラフに関する数学上の成果を情報科学の他分野に応用することも試みた。その研究実績は以下の通りである。グラフのサイクル分布に関してLesniakは、最小次数が3以上であるグラフには長さが4の倍数になるサイクルが存在するだろうと予想した。本研究代表者はDean、Lesniakらと共にこの予想を解決した。この際、背理法の議論により、まず頂点数最小の反例の性質を調べ、そのグラフの連結度が高いことを導いた。そして縮約法により、矛盾を導いた。すなわちこの証明において縮約法は中心的な役割を果たした。今のところ縮約法を用いない証明は知られていないので、縮約法の有用性がここにおいても示されたことになる。また本研究代表者は、グラフが非自明な誘導木に分解されるための必要十分条件を導いた。この証明においても縮約法は中心的な役割を果たしている。証明は構成的であり、この結果はグラフを効率的に木に分解するアルゴリズムも与えている。さらに本研究代表者は、グラフの性質を秘密共有法とよばれる暗号法の1つに応用することに成功した。秘密共有法とは、1つの秘密情報を断片に分割して管理し、その1部が漏洩しても秘密そのものの機密性が保たれるようにする技術である。本代表者は、以前にもこの分野の研究を行ったが、今回はグラフの性質を使って、その時よりも効率の良い秘密共有法を構築した。

The nature of the contraction of the constitution is highly correlated with the strength of the instrument. This year, we will try to solve the problems related to the use of contractions and the distribution of services. The results of mathematics related to information science are applied to other fields. The research achievements are as follows: The minimum number of times the number of times This study represents Dean and Lesniak's efforts to resolve this problem. In this case, the discussion of the method of back-up, the property of the counterexample with the minimum number of vertices, and the degree of connection between the two vertices are high. The Constitution of the People's Republic of China has been revised and the contradiction has been solved. The proof of this is that the Constitution is the center of the work. The present article is intended to prove the usefulness of the Constitution. This study represents the necessary conditions for the decomposition of non-self-evident trees. The proof of this is that the Constitution is the center of the work. It is proved that the composition of the system can be divided into two parts: one part is composed of two parts, the other part is composed of two parts. The author of this study succeeded in sharing the nature of the secret code. Secret sharing method: 1. Secret information fragmentation management; 1. Secret information leakage; 2. Secret information protection; 3. The representative of this paper is to construct a good secret sharing method for the study of the past and the future.

项目成果

N.Dean: "Cycles of length O modulo 4 in graphs" Discrete Mathematics. 121. 37-49 (1993)

N.Dean：“图中长度为 O 模 4 的循环”离散数学。

M.Ito: "Multiple assignment scheme for sharing secret" Journal of Cryptology. 6. 15-20 (1993)

M.Ito：“共享秘密的多重分配方案”密码学杂志。

A.Saito: "Partitioning graphs into induced stars" Ars Combinatoria. 36. 3-6 (1993)

A.Saito：“将图划分为诱导星”Ars Combinatoria。