組合せ数学セミナー
発表内容の概要
Travel groupoidは木や測地グラフ(任意の二頂点間の最短パスが一意に存在するグラフ)の
代数的特徴付けの研究を通じて2006年に定義された代数系である．多重辺とループを持た
ない無向グラフに対してtravel groupoidが構成できて，歩道の代数的記述が得られる．
特にnon-confusing travel groupoidと呼ばれるクラスでは，グラフ上のパスが代数的に
記述される．
本講演では，travel groupoidについての基本的な事柄を解説し，non-confusing travel
groupidの一般化となる代数系(navigation groupoid)を提案する．また，この代数系の応
用としてカーナビ等のナビゲーションシステムとの関係についても述べる．
送信者の選択した相手のみに対してメッセージを効率的かつ安全に送信するための暗号として，
ブロードキャスト暗号が知られているが，その暗号化において暗号鍵をどのように管理するかが
問題となる．その際に組合せ論における木構造を考え鍵を管理する方法が知られている．
さらにその鍵管理木とグラフ理論に出てくる完全マッチングの間には様々な全単射が存在するが
そのことについても紹介する。
A kernel is an independent and dominating subset of vertices of a digraph.
Kernels have a strong game-theoretic flavour; in particular, stable matchings can be
considered as kernels of a specially oriented digraph. In this talk, I will talk
about their connections with game theory, and some algorithmic results for a
restricted class of graph families.
単一割当ハブネットワーク設計問題とは, 航空ネットワークや通信ネットワーク等に
おいて, 総輸送費用を最小にするように, 各非ハブノードからハブノードへの接続を
決定する問題である.
本講演では, サイクルスター型ハブネットワーク設計問題の定式化を解説し, この問
題に対する, 線形緩和問題と従属ラウンディングを用いた2(1-1/h)-近似アルゴリズム
について述べる. (h:ハブの数)
3次元空間内の面積1の凸曲面(閉，連結である必要はない）上から一様ランダムに選んだ3点を通
る平面でその曲面を2分割する。その片方の面積 A を確率変数としたとき，A の確率密度分布関
数は f(x) = 6x(1-x) であり，曲面の形状に依存しない。この「A の確率密度が曲面の形状に依
存しない」という命題が成立するのは，3次元以下の空間の特質であり，4次元以上では成り立た
ない。
トップに戻る