凸幾何上のマトロイドおよびグラフに関する離散構造・最適化問題の研究

凸几何拟阵和图的离散结构及优化问题研究

• 批准号: 08J05732
• 负责人: 佐野 良夫
• 金额: $ 0.77万
• 依托单位: Kyoto University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for JSPS Fellows
• 财政年份: 2008
• 资助国家: 日本
• 起止时间: 2008 至 2009
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-08J05732/
• 关键词: 離散最適化; マトロイド; 凸幾何; グラフ理論; 競争グラフ; 競争数

凸幾何上のマトロイドとは、マトロイドの一般化である。私はこの凸幾何マトロイドについての研究を行った。凸幾何マトロイドの独立集合族、全域集合族の公理系をそれぞれ強めることによって得られる部分クラスとして、ストリクト凸幾何マトロイド、コストリクト凸幾何マトロイドがある。私は、これらの部分クラスに対しても公理系による特徴づけを与えた。それから、制限や縮約などといった凸幾何マトロイドに対する作用について考察した。これらの作用は、上記の凸幾何マトロイドの部分クラスと非常に深い関係がある。一般に、凸幾何マトロイドの制限や縮約が凸幾何マトロイドになるとは限らないのであるが、ストリクト凸幾何マトロイドの制限は常にストリクト凸幾何マトロイドであり、コストリクト凸幾何マトロイドの縮約は常にコストリクト凸幾何マトロイドであることが明らかになった。また、凸幾何マトロイドに関連する最適化問題として、最大独立集合問題(最大基問題)についても考察し、その結果、ストリクト凸幾何マトロイドの貪欲アルゴリズムによる特徴づけを与えた。また、グラフの離散構造に関する研究として、競争グラフおよびグラフの競争数に関して取り組んだ。グラフの競争数の計算は、NP困難問題であることが示されており、一般のグラフに対してその正確な値を求めることは簡単ではない。私は対称性の高いグラフの競争数について研究を行った。その結果、完全多部グラフについて、競争数と非常に深い関係をもつ辺クリーク被覆がラテン方陣と関係があることがわかった。このラテン方陣との関係を用いることで、完全多部グラフの競争数の上界および下界に既存の結果よりもよりよい評価を与えることができた。また、ジョンソン・グラフ、ハミング・グラフについて、その競争数についての上界・下界を与え、さらにグラフの直径が3以下であるものについては、その競争数の値を正確に与えた。

Convex geometry is generalized. A study of convex geometry is carried out. The axiom system of the independent set family and the global set family of convex geometry is divided into two parts: the first part and the second part. The first part of the article is about the characteristics of the axiom system. The role of the convex geometry in the control system is investigated. The effect of this is to record the convex geometry of the part with the very deep relationship. General, convex geometry limit, reduce convex geometry limit The maximum independent set problem (maximum basis problem) is investigated and the results are presented. The study of discrete structures in the field of transportation, competition, and competition is of great importance to the organization. The calculation of the number of competitors is the NP difficulty problem. The research on privacy and competition is carried out in a highly competitive manner. The result is complete multi-division, the number of competitions is very deep, the relationship is very deep. The upper bound of the competition number of the complete multipart matrix is the lower bound of the existing result.また、ジョンソン·グラフ、ハミング·グラフについて、その竞争数についての上界·下界を与え、さらにグラフの直径が3以下であるものについては、その竞争数の値を正确に与えた。

项目成果

The niche graphs of doubly partial orders

双偏序的利基图

• 发表时间: 2009
• 期刊: Congressus Numerantium 195
• 作者: Suh-Ryung KIM;Jung Yeun LEE;Boram PARK;Won Jin PARK;Yoshio SANO
• 通讯作者: Yoshio SANO

Subclasses of cg-matroids

cg-拟阵的子类

• 发表时间: 2009
• 期刊: Proceedings of the 6th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications
• 作者: Suh-Ryung KIM;Boram PARK;Yoshio SANO;Yoshio SANO;Yoshio SANO
• 通讯作者: Yoshio SANO

完全多部グラフの競争数について

关于完整多部分图的竞争数量

• 发表时间: 2008
• 作者: Suh-Ryung KIM;Yoshio SANO;佐野良夫;佐野良夫;佐野良夫;佐野良夫;佐野良夫;佐野良夫;佐野良夫;佐野良夫;佐野良夫;佐野良夫;佐野良夫;佐野良夫;佐野良夫;Yoshio SANO;Yoshio SANO;Yoshio SANO;Yoshio SANO;佐野良夫;Yoshio SANO;Yoshio SANO;佐野良夫;Yoshio SANO;佐野良夫;佐野良夫
• 通讯作者: 佐野良夫

Cycles and p-competition graphs

循环和 p 竞争图

• 发表时间: 2009
• 期刊: Congressus Numerantium 196
• 作者: Suh-Ryung KIM;Boram PARK;Yoshio SANO
• 通讯作者: Yoshio SANO

The competition numbers of regular polyhedra

正多面体的竞赛数

• 发表时间: 2009
• 期刊: Congressus Numerantium 198
• 作者: Suh-Ryung KIM;Boram PARK;Yoshio SANO;Yoshio SANO
• 通讯作者: Yoshio SANO