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

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

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