小特集 2. マッチングからマトロイドパリティへ

電子情報通信学会 - IEICE会誌 試し読みサイト
Vol.101 No.3 (2018/3) 目次へ

前の記事へ次の記事へ


グラフアルゴリズムの最先端

小特集 2.

マッチングからマトロイドパリティへ

From Matching to Matroid Parity

小林佑輔

小林佑輔 筑波大学システム情報系社会工学域

Yusuke KOBAYASHI, Nonmember (Division of Policy and Planning Sciences, University of Tsukuba, Tsukuba-shi, 305-8573 Japan).

電子情報通信学会誌 Vol.101 No.3 pp.248-252 2018年3月

©電子情報通信学会2018

abstract

 グラフのマッチングは,研修医の病院への割当て,学生の学校への割当て,仕事の労働者への割当てなどのモデル化を動機として,様々な分野において盛んに研究されている.本稿では,アルゴリズムに興味を持つ読者を対象とし,所望のマッチングを効率良く求めるアルゴリズムの理論について,計算機科学の視点から紹介する.まず,マッチングの概念を説明し,マッチングアルゴリズムに関する古典的な結果について述べる.そして,マトロイドパリティと呼ばれるマッチングを一般化した概念について筆者らの最新の結果とともに紹介する.

キーワード:マッチング,グラフアルゴリズム,多項式時間アルゴリズム,マトロイドパリティ

1.は じ め に

 4人の男性mathmathmathmathと4人の女性mathmathmathmathがいるときに,この8人を四つの男女ペアに分けることを考える.ただし,ペアになることのできる男女の組には制限があり,例えばmathmathはペアになることができるが,mathmathはペアになることができない,といった具合である.それぞれの人を点で表し,互いにペアになることができる人を線分で結ぶことで,ペアになることのできる組合せを図1のように表現することにする.この場合は,8人を例えばmathmathmathmathというペアに分けられることが分かる.なお,図1のように点とそのつながり方を表現する構造はグラフと呼ばれる.

fig_1.png

 本稿ではグラフを頂点集合mathと辺集合mathとの組mathで表す.特に,今回の場合には各頂点に対応する人は男性と女性の2種類に分けられており,男女をペアにする状況を考えていた.そのため,扱うグラフは頂点集合がmathが2種類の集合mathmathに分割されており,各辺はmathの頂点とmathの頂点をつないでいる.このようなグラフを2部グラフと呼び,mathと表す.ペア分けはグラフにおいてはマッチングと呼ばれる概念に相当する.辺の集合mathがマッチングであるとは,どの頂点に対してもその点に接続するmathの辺が高々1本であることを言う.また,特にどの頂点に対してもその点に接続するmathの辺がちょうど1本であるときに,mathは完全マッチングであると言う.すると,男女ペアに分ける問題は,2部グラフmathが与えられたときに,完全マッチングmathを求める問題として記述することができる.


続きを読みたい方は、以下のリンクより電子情報通信学会の学会誌の購読もしくは学会に入会登録することで読めるようになります。 また、会員になると豊富な豪華特典が付いてきます。


続きを読む(PDF)   バックナンバーを購入する    入会登録


  

電信情報通信学会 - IEICE会誌はモバイルでお読みいただけます。

電子情報通信学会誌 会誌アプリのお知らせ

電信情報通信学会 - IEICE会誌アプリをダウンロード

  Google Play で手に入れよう

本サイトでは会誌記事の一部を試し読み用として提供しています。