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

高度连通图及其应用

• 批准号: 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部が漏洩しても秘密そのものの機密性が保たれるようにする技術である。本代表者は、以前にもこの分野の研究を行ったが、今回はグラフの性質を使って、その時よりも効率の良い秘密共有法を構築した。

约简方法是研究高度连通图的属性的强大工具。今年，我们使用这种约简方法来尝试解决与图的循环分布相关的问题。我们还尝试将与图相关的数学结果应用到信息科学的其他领域。研究结果如下。关于图的环分布，Lesniak 预测最小度大于或等于 3 的图将具有长度为 4 倍数的环。首席研究员与 Dean 和 Lesniak 一起解决了这个猜想。这时，通过讨论逆向方法，我们首先考察了顶点数最少的反例的性质，得出图的连通度较高。并且通过还原的方法，他导致了矛盾。换句话说，归约方法在这个证明中发挥了核心作用。由于目前还没有已知的证据表明不使用归约方法，因此这里也证明了归约方法的有用性。主要研究者还推导了图分解为非平凡归纳树的充分必要条件。归约方法在这个证明中也起着核心作用。证明是有建设性的，结果也提供了一种有效地将图分解为树的算法。此外，首席研究员成功地将图的属性应用于一种称为秘密共享的密码学。秘密共享法是一种将一段秘密信息分割成碎片进行管理的技术，这样即使一部分泄露，秘密本身的机密性也能得到维持。该代表此前曾在该领域进行过研究，但这次他利用图的性质构建了一种比当时更高效的秘密共享方法。

项目成果

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。