分野別セミナー

安藤 映 (崇城大)
Ei Ando (Sojo University)
Title：木幅の小さなグラフ上の確率的最適化問題の効率的な解法
　　(An approach for solving the stochastic optimization problems on graphs with small treewidth)
Abstract：
頂点集合Vと枝集合Eを持つような離散グラフG=(V,E)について、各枝eに互いに独立な確率変数の枝重みX_eが付けられている場合を考える。このとき、二頂点間の最短路の長さや、グラフの最大全域木の重みを求めるような問題のことを確率的最適化問題と呼ぶことにする。確定的な枝重みの場合には効率的に解けような問題でも、確率変数の枝重みを考えた場合は一般に#P困難と呼ばれる難問のクラスに属する。本発表では、二頂点間の最短路長さや、最大全域木重みの確率分布を求める問題は木幅を制限すればグラフ規模の多項式時間で完了するアルゴリズムを示す。




井口 修一 (九大数理)
Shuichi Inokuchi (Kyushu University)
Title：合成が可換となるCAの組とその合成CAの周期長について
Abstract：
遷移関数の合成により定義されたセルオートマトン（CA)を対象にする。一般にCAの遷移関数の合成は可換とはならないが、与えられたCAと可換となるCAを計算する方法は報告されている。ここでは、合成が可換となるCAの組みを求め、合成が可換となる為の条件について報告する。また、合成が可換となるCAの周期と、それらの合成により構成されたCAの 周期の関係について報告する。




手老 篤史 (九大IMI)
Atsushi Terou (Kyushu University)
Title：生物の適応ネットワークに学ぶフローネットワーク理論
Abstract：
血管や葉脈など生物は様々な輸送ネットワークを作る。これらは生物の形態形成や生命現象の維持には欠かせない 重要な機構であり、状況に応じて様々な形状をとる。ここでは真正粘菌という単細胞生物が迷路を解くという 現象を基にフローネットワークにおける最適化問題について解説する。




高橋 規一(九大システム情報)
Norikazu Takahashi (Kyushu University)
Title：与えられた頂点数と辺数の下で代数的連結度を最大にする グラフについて
　　(On graphs with given number of vertices and edges that maximize the algebraic connectivity)
Abstract：
相互に作用しながら自律的に行動する複数の主体 （エージェント）からなるネットワークをマルチエージェントネットワークという． マルチエージェントネットワークにおいて，合意形成は，センサフュージョン， 自律移動ロボット群のフォーメーション形成，結合振動子の同期等に関連する 重要な技術である．Olfati-Saberらは，各エージェントが近傍のエージェントと 通信を行いながら自身の状態値を変化させる合意形成アルゴリズムを提案し， エージェント間の通信の可否を表す単純無向グラフの連結性が保たれれば必ず 平均合意に達することや，平均合意への収束の速さがそのグラフのラプラシアン 行列の2番目に小さい固有値，すなわち，代数的連結度によって決まることを 示した．そこで講演者の研究グループでは，高速な合意形成を実現するマルチ エージェントネットワークの接続構造を明らかにすることを目標とし，与えられた 頂点数と辺数をもつ単純無向連結グラフの中から代数的連結度を最大または極大に するものを求める問題に取り組んでいる．本講演では，この問題に関してこれまで に得られたいくつかの結果を紹介する．




※ このセミナーは，グローバルCOEプログラム「マス・フォア・インダストリ 研究教育拠点」の支援を受けて開催されます。



リンク
　組合せ数学セミナーWebsite
　リファレンス駅東ビル