再帰的条件による成分因子の存在性に関する研究

利用递归条件研究分量因素的存在性

• 批准号: 07740170
• 负责人: 西村 強
• 金额: $ 0.77万
• 依托单位: Shibaura Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1995
• 资助国家: 日本
• 起止时间: 1995 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-07740170/
• 关键词: 成分因子; P_<3->因子; 連結グラフ; 再帰的条件; 誘導部分グラフ

グラフ理論における再帰的条件におけるある種の構造の存在性定理は、これまでに次の2つのTypeのものが最も基本的なものとして研究されてきている。Gを連結グラフ、HをGの任意の連結誘導部分グラフで位数を固定したものとする。さらにPをグラフのもつ性質とするとき、TypeI:Hが性質Pをもつ⇒Gも性質PをもつTypeII:G＼Hが性質Pをもつ⇒Gも性質PをもつKを連結グラフとし、Pが「K-成分因子をもつ」ということに対して、1986年にEnomoto, Egawa, SaitoによってTypeIが成立することが示されている。ここでの研究実績としては、「K-成分因子をもつ」ということに対するTypeIIの定理が完成させることができた。この結果は、JOurnal of Graph Theory誌において掲載受理を受けた。さらに、新しいTypeの再帰的条件としてTypeIII:H及びG＼Hがともに連結となる任意のHに対し、H(又はG＼H)が性質Pをもつ⇒Gも性質Pをもつということに対し、「K-成分因子をもつ」という結果については解決をみていないが、Gが2連結で、Pが「P_<3->因子をもつ」ということに対しては、TypeIIIが成立することが、この研究において証明することができた。グラフが成分因子をもつための必要十分条件を得ることはNP-完全問題であり、十分条件を得る研究ですらあまり進んでいない状態であったが、この研究において、2つの十分条件を得るに至ることができた。

The existence theorem of the structure of the species is the most basic condition for the re-development of the theory. G link, H link, G link, G Type II:G\H Nature P Nature K Nature P Nature P The results of this research are as follows: "K-component factor" and "TypeII theorem" are completed. The result is JOURNAL OF Graph Theory. The conditions for re-entry of new Type are: Type III:H and G\H are linked to each other, H(G\H) is a property P is linked to G is a property P is linked to each other,"K-component factor is linked to each other," P is linked to each other, <3->Type III is linked to each other, and P is linked to each other. The NP-complete problem is solved by the necessary ten conditions for the component factors, and the necessary ten conditions are obtained.