权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

グラフの点素な閉路に関する極値問題

关于图中点不相交循环的极值问题

基本信息

批准号：
03J53061
负责人：
松村初
金额：
$ 1.66万
依托单位：
Keio University
依托单位国家：
日本
项目类别：
Grant-in-Aid for JSPS Fellows
财政年份：
2003
资助国家：
日本
起止时间：
2003 至 2005
项目状态：
已结题

项目摘要

今年度は1.2部グラフにおける指定した頂点数3のパスを含む閉路による分割2.指定した線形林を含む閉路によるグラフの分割3.いくつかの頂点の次数が制限された全域木の存在について取り組んだ。これまでの研究では、指定された頂点や辺を含む閉路によるグラフの分割を考えてきたが、その一般化として、線形林を指定して、それらを含む閉路による分割が考えられる。一般的には頂点と辺を指定した場合の結果を用いることにより、容易に最良の次数条件が求められるが、それには当てはまらないケースもいくつかある。2.の研究ではそのような状況を特定し、その場合における最良の次数条件を求めた。2部グラフにおいては線形林を考える際の元となる頂点と辺を含んだ場合の問題も未解決である。線形林の部分的な問題として、頂点数が3のパスを指定した場合を1.で考え、こちらも最良の次数条件が求まった。2部グラフにおいては頂点数が奇数のパスは辺の場合と大きく状況が異なるため、一般的な問題の解決への1歩になったのではないかと考えている。3.は昨年度より取り組んでいる全域木の研究である。今年度は(1)指定された頂点を含み、全体の次数が制限された部分木(2)指定された頂点については次数が制限された全域木、が存在するための次数条件を考え、最良の条件を求めることが出来た。この研究はこれまで閉路に関する研究で考えられてきた考え方を木の問題に適用したものであり、これまであまりなされていなかったものである。この結果については7月にイギリスで行なわれた「British Combinatorial Conference」および9月にフランスで行なわれた「International Colloquium on Graph Theory」において研究発表を行なった。

This year, 1.2 parts of the tree are divided into 3 parts, including closed circuit. 2 parts of the tree are divided into 3 parts, including closed circuit. This study is based on the analysis of the vertex, closed circuit and linear forest. The result of the general situation is that it is easy to find the best number of times. 2. The optimal number of times for the study is determined by the specific situation and the specific occasion. 2. Unsolved problems in linear forest The problem of linear forest is that the number of vertices is 3 and the number of times specified is 1. The optimal number of times is 1. 2. The number of vertices is odd, the situation is large, the problem is solved, and the problem is solved. 3. Yesteryear This year (1) specify the number of vertices, all the times to limit the number of partial trees (2) specify the number of vertices, all the times to limit the number of global trees, all the times to exist, the best conditions to find out. This research is about the application of the software to the problem. The results were published in July and September under the title "British Combinatorial Conference" and "International Colloquium on Graph Theory."