組合せ数学セミナー
発表内容の概要
周期グラフは結晶など様々なもののモデルに使われており、
周期グラフの対称性に関して多くの研究が行われている。
周期グラフ描画の回転対称性に関しては、L1-rigidな周期グラフ描画
について必要条件が知られている[Deza,Shtogrin 2002]。
本講演では、L1-rigidよりもより広いクラスであるコヒーレントな
周期グラフ描画が回転対称性を持つための必要条件を示す。
本研究は、国立情報学研究所の夫紀恵氏との共同研究である。
In the late 1970's, Fiedler proved some remarkable properties
of the eigenvector associated with the smallest positive
Laplacian eigenvalue of a tree. We describe these results and
then consider some other values associated with the vertices
of a tree, related to the Laplacian, which exhibit similar monotonicity
properties. We also state some open problems. The talk is partly
based on joint work with Chai Wah Wu.
本講演では，マトロイドの向き付け可能性と表現可能性という二つの代表的な性質における，禁
止マイナーによる特徴づけを扱う.
極小禁止マイナー（以下、禁止マイナー）はグラフの性質に対して，簡潔な特徴づけを与えうる
ことが知られている．例えば，KuratowskiとWagnerによって示された，グラフが平面的であるこ
とが，完全グラフK_{5}と二部完全グラフK_{3,3}という二つのグラフをマイナーとして含まない
ことと同値であるという定理は，グラフ理論において最もよく知られた古典的な結果の一つであ
る．RobertsonとSeymourは，このような有限個の禁止マイナーによる特徴づけが常に可能である
ことを示した．つまり，マイナー操作に関して閉じたグラフの性質に関しては，有限個の禁止マ
イナーを列挙することで，常に同値な特徴づけが可能であることを示した．これはGraph Minor
Theoremと呼ばれ，この定理の証明の過程で，グラフの分解などの多くの深遠な理論体系や手法
が構築・整備されたことで，アルゴリズム開発における現在の多様な展開を引き起こすことに繋
がっている．
マトロイドは，グラフの全域木や閉路の持つ性質や，ベクトルの一次独立性を公理化した組合せ
構造である．マトロイドにおいても，マイナー操作は，グラフからの拡張として自然に定義され
る一方で，マトロイドの性質に関しては，グラフのように常に有限個の極小禁止マイナーで特徴
付けられるとは限らない．例えば，マトロイドの表現可能性，つまり，所与のマトロイド構造が
ベクトル空間上の点集合の一次独立関係として，（あるいは同じことだが射影空間上の点と超平
面の接続関係として，）具体的に表現できるかどうか，という性質がある．これは空間の係数体
が有限体であるときには，有限個の禁止マイナーで特徴づけられることが予想され（Rotaの予想）
，当分野の一大未解決問題として，多くの研究がなされた結果，近年その解決が報告された．一
方で，無限体の場合は，常に無限個の禁止マイナーが存在してしまうことが知られている．この
ようにマトロイドにおいては基礎的な性質でも禁止マイナーが無限個存在してしまうことが知ら
れており，禁止マイナーによる特徴づけがグラフの場合と比べ困難であると言えるが，一方で，
無限個ある場合においても，何からの自然な制限などを課すことで，禁止マイナーによる有限個
の特徴づけが可能になる可能性がある．
今回は，禁止マイナーが無限個あることがあることが知られている二つの基礎的な性質，向き付
け可能性と，（無限体上）表現可能性に関して，このような視点から行った我々の研究を紹介す
る．本研究は森山園子氏（日本大学）との共同研究である．
閉曲面上の三角形分割グラフとは，
各面が三本の辺からなるグラフであり，
四角形分割グラフとは各面が四本の辺からなるグラフである．
グラフ理論で最も有名な問題のひとつの「四色問題」は，
平面上の三角形分割グラフの頂点4-彩色性を問う問題である．
これを発端として，
閉曲面上の三（四）角形分割グラフの彩色について数多くの研究がなされてきた．
本講演では三（四）角形分割グラフの頂点・辺着色に関する既存の結果，
及び得られている研究成果を一通り紹介し議論する．
本研究の一部は，
中本敦浩氏（横浜国立大学），
鈴木有祐氏（新潟大学），
小関健太氏（国立情報学研究所），
松本直己氏（成蹊大学）との共同研究である．
巡査が k 人おり各巡査 i は速さ v_i で動ける。これを使って塀（線分）を警邏し、どの点も
任意の単位時間に一度は誰かが訪れるようにしたい。明らかな方法としては各巡査 i が長さ v_
i/2 の区間を受け持って往復するというものがあり、合せて長さ (v_1 + ... + v_k)/2 を警邏
できる。これよりも長い塀が警邏できることはないとCzyzowiczらは予想した。この予想に反例
を与えるとともに、関連する問題について論ずる。小林佑輔氏、副島真氏との共同研究に基づく。
コミュニティ抽出における評価関数として，Newman & Girvan による modularity が
よく知られている．しかし modularity には解像度限界と呼ばれる問題点があること
が，Fortunato & Barthelemy によって指摘されている．これに対して，Li et al.
は，modularity density という評価関数を提案した．Modularity density の最大化
問題は，分数関数の和を目的関数に持つ最適化問題に定式化される．
本研究では，この問題が 0-1SDP と呼ばれる問題に等価変換できることを示し，その
錐計画緩和問題を解くことにより上界値を求める．
本研究は，松井知己先生（東京工業大学），山本芳嗣先生（筑波大学）との共同研究
である．
マトロイド交わり問題は最も基本的な組合せ最適化問題のひとつであり，二部グラフの最大マッ
チングや有向グラフの有向木詰め込みなどを特殊な場合として含む．本発表では，重み付きマト
ロイド交わり問題に対する新しいアルゴリズムを提案する．計算量は擬多項式時間であるが，最
大重みが小さな場合は既存アルゴリズムより高速である．アルゴリズムの主なアイデアは，重み
を分解することで重み無しマトロイド交わり問題に帰着することである．提案アルゴリズムの枠
組みは近似アルゴリズムの設計にも利用できる．
本研究は，神山 直之 氏(九州大学)，Chien-Chung Huang氏(チャルマース工科大学)との共同
研究である．
トップに戻る