グラフ書き換え系のネットワーク不変量計算への応用に関する研究

图重写系统在网络不变性计算中的应用研究

• 批准号: 05780257
• 负责人: 溝口 佳寛
• 金额: $ 0.58万
• 依托单位: Kyushu Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1993
• 资助国家: 日本
• 起止时间: 1993 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-05780257/
• 关键词: ネットワーク; グラフ変換; カテゴリー論; グラフアルゴリズム

ネットワークの信頼性計算をグラフ変更を用いて行なう手法は,近年広く知られているがその計算についての理論的解析は十分に行なわれていない.また,信頼性以外のネットワーク不変量計算へのグラフ変換の応用についても未だ知られていないことが多い.本研究の目的は,種々のネットワーク変量のグラフ変換による計算手法を開発し,実現及び理論的解析を行うことである.本年度は,以下の通りの研究実績を挙げた.1.グラフ変換の定式化の容易なグラフの圏の発見グラフ変換の理論的基盤となるグラフの圏においてプッシュアウトの存在条件を調べた.種々のグラフの定式化のうちプッシュアウトが常に存在する,すなわちグラフ変換が自由に定式化出来るグラフの圏を発見した.この成果は,圏論とその応用に関する雑誌(cahiers de topologie et geometrie differentielle categoriques)へ公表した.2.グラフ変換における危険対の補題の証明変換規則の適用順序を変えても計算結果が変化しないことを保証する危険対の補題を,項を表現する制限されたグラフ変換の定式化の下で証明した.この成果の一部は,情報基礎理論ワークショップにおいて公表した.3.グラフ書き換え処理系の実現グラフ変換を利用したアルゴリズム開発に不可欠なグラフ変換を計算機上で自由に実行出来るためのグラフィカル・ユーザ・インターフェース処理系を実現した.任意のグラフ変換規則を自動,または手動で適用していくことが出来る.また,危険対の探索およびその合流性の判定も行なうことが出来る.この成果の一部は,電気関係学会九州支部連合大会論文集において公表した.4.信頼性以外のネットワーク不変量の計算手法の開発直列並列ネットワークに対して,最短経路問題を頂点数に比例した計算時間で計算出来るグラフ変換を用いたアルゴリズムを発見した.この成果の一部は,応用数学合同研究集会報告集に公表した.

In recent years, we know that the calculation of reliability is very difficult to solve. In addition to the reliability of the system, the system does not change the amount of calculation, and the system does not know whether it is in the middle or in the middle. The purpose of this study is to develop computational methods, implement and analyze the theory. This year, the following general research results are summarized: 1. The ease of formulation of the transformation and the theoretical basis for the development of the transformation and the adjustment of the conditions for the existence of the transformation. There is always a pattern of the species, and the pattern of the species is always present, and the pattern of the species is freely formed. The results of this study are as follows: cahiers de topologie et geometrie differentielle categories. 2. The order of application of the rules of transformation is as follows: the calculation results are transformed into the guarantee of the complement of the problem, and the expression of the term is restricted. Part of the results of this research is that the information-based theory is used to realize the processing system. Any change in rules is automatic, but manual. To explore the danger, to determine the convergence, to determine the behavior. A part of the results of this research is published in the Proceedings of the Kyushu Branch Joint Conference of the Institute of Electrical Relations. 4. The calculation method of the variation in the output of the information is developed in parallel with the calculation method of the maximum number of vertices in the shortest path problem. The results of this research are presented in a report on the use of mathematical contracts.

项目成果

溝口佳寛,矢島健一: "グラフ変換による最短経路問題の解法" 応用数学合同研究集会報告集. 43-46 (1993)

Yoshihiro Mizoguchi、Kenichi Yajima：“使用图变换解决最短路径问题”应用数学联合研究会议报告43-46（1993）。

溝口佳寛,河原康雄: "グラフ変換による項書き換え系の危険対の補題について" 情報基礎理論ワークショップ論文集. 52-57 (1993)

Yoshihiro Mizoguchi、Yasuo Kawahara：“关于使用图变换的危险术语重写系统的引理”基本信息理论研讨会论文集 52-57 (1993)。

Yoshihiro Mizoguchi: "A graph structures overthe categories of sets and partial functions" cahiers de topologie et geometrie differentielle categoriques. 34. 2-12 (1993)

Yoshihiro Mizoguchi：“集合和偏函数类别上的图结构”拓扑和几何分类手册。

矢島健一,溝口佳寛: "グラフ変換によるネットワーク量計算システムの開発" 電気関係学会九州支部連合大会講演論文集. 817-817 (1993)

Kenichi Yajima、Yoshihiro Mizoguchi：“使用图形变换开发网络量计算系统”日本电气工程师九州分会会议记录 817-817 (1993)。