グラフの生成定理を用いた効率的なグラフ列挙アルゴリズムの構築
【研究キーワード】
三角形分割 / 生成定理 / 局所連結グラフ / facial achromatic number / 偶三角形分割 / 組合せゲーム / グラフ彩色 / 局所変形 / 既約グラフ / グラフ理論 / 列挙アルゴリズム
【研究成果の概要】
本研究課題では,グラフの新しい生成定理のバリエーションの創成とその応用が主題であり,本年度は当初の計画書に記載していた通り,三角形分割と呼ばれるグラフについて,応用面に焦点を当てて研究を遂行した.以下ではその応用研究のうち,局所連結グラフと呼ばれる三角形分割をある種の拡張概念に関する研究の内容について紹介する.
三角形分割は定義から,その各点の近傍が2-連結グラフ(どの1点を取り除いても連結なグラフ)を誘導することが知られている.それより少し弱い条件「各点の近傍が連結グラフ」を満たすグラフのことを局所連結グラフと呼ぶ.定義より,任意の三角形分割は局所連結グラフであるため,三角形分割の定理を局所連結グラフに拡張しようという研究は以前より行われてきた.
そこで私は,平面偶三角形分割におけるfacial achromatic numberと呼ばれる不変量に関する定理に着目した.この定理は,本研究課題を始めてすぐの頃に生成定理を利用して証明した命題の一つである.この定理では,偶三角形分割の生成定理を応用し,facial achromatic numberがある定数と一致するグラフの特徴付けを行っている.
今回,その特徴付けを行ったときに用いた手法を局所連結グラフに応用し,偶三角形分割の定理を局所連結グラフに拡張することに成功した.局所連結グラフにすることで,上述の不変量に影響を与えるより本質的な局所構造に着目することができた.
また,上記に加え,グラフの局所構造に対する変形操作を扱う生成定理の研究の一環として,本年度はグラフが幾何的に埋め込まれている場合における局所構造に関する研究や特定の部分グラフを禁止した場合のグラフの性質に関する研究成果も得ている.
【研究代表者】
【研究種目】若手研究
【研究期間】2019-04-01 - 2023-03-31
【配分額】3,120千円 (直接経費: 2,400千円、間接経費: 720千円)