マッチング問題]]とは?

Weblio 辞書 > 学問 > OR事典 > マッチング問題]]の意味・解説 

マッチング問題

読み方まっちんぐもんだい
【英】:matching problem

概要

無向グラフ与えられたときに, ある目的にしたがってマッチングを選ぶ問題をマッチング問題と呼ぶ. 例えば, 最大要素マッチング問題, 最大重みマッチング問題(割当問題), 安定マッチング求め安定結婚問題などが挙げられる. 2部グラフでのマッチング問題はネットワークフロー問題の特殊ケースとして解くことができるのに対し, 一般グラフ場合問題構造がより複雑になり多少工夫要するが, いずれの問題多項式時間で解くことができる.

詳説

 G = (V, A)\, 無向グラフとする. G\, マッチング (matching) とは, 端点共有しない集合 M \subseteq A\, のことである. k\, 本のからなるマッチングk\, -マッチング呼び, 特に k = |V|/2\, のときは完全マッチングと呼ぶ. 与えられた目的に従ってマッチングを選ぶ問題のことを, マッチング問題という. 以下, 幾つかのマッチング問題について簡単に説明する.

(a) 最大マッチング問題 数が最大マッチング求め問題を, 最大マッチング問題という. マッチング M\, に対し, 長さ奇数の道 P =(a_1, a_2, \cdots, a_{2k+1})\, が, 条件 a_i \in A\setminus M\, (\forall i:\, 奇数), a_i \in M\,  (\forall i:\, 偶数)\, を満たし、道P\, 始点終点M\, 端点でないとき, P\, M\, に関する増加道と呼ばれる. 増加に関して, 以下の性質成り立つ:



 従って, 数 0 のマッチングからはじめ, 各反復では, 増加道を求めてマッチング数を増やしていくことで, 最大マッチング求められる. G\, 2部グラフ場合には, 増加道の存在判定及び検出が容易に実行できるのに対し, 一般グラフ場合には多少工夫要するいずれの場合多項式時間最大マッチング求めることができる.

 点集合 U \subseteq V\, に対して, 任意の a \in A\, 端点のうち少なくとも一方U\, 含まれるとき, U\, G\, 被覆呼ばれる. 任意のマッチング M \subseteq A\, 任意の被覆 U \subseteq V\, に対して, 不等式 |M| \leq |U|\, 成り立つ. 特に, G\, 2部グラフならば, 最大マッチング数と最小被覆点数等しい:


\max\{|M| \mid M: G\, マッチング\} = \min\{|U| \mid U: G\, 被覆\}.\,   (1)\,


これを, 2部グラフに関する最大マッチング最小被覆定理という.

 一般グラフ場合, 式(1)は成り立つとは限らないが,成り立つようにその右辺修正することができる.奇数個の点からなる集合の族を {\mathcal U} = \{U_1, U_2, \cdots, U_k\}\, とする. 任意の a \in A\, に対して, 以下の条件 (i) または (ii) が成り立つとき, \mathcal U\, G\, の奇被覆と呼ぶ:

\mbox{(i)} \quad |U_i| = 1\, なる U_i\, 存在して, a\, 一方端点U_i\, 含まれる.
\mbox{(ii)} \quad|U_i| > 1\, なる U_i\, 存在して, a\, 両端点が U_i\, 含まれる.

U \in \mathcal U\, に対し, c(U)\, を, |U| = 1\, ならば c(U) = 1, |U| > 1\, ならば c(U) = (|U| - 1)/2\, , と定める. このとき, 次の最大・最小定理成り立つ:

\textstyle \max\{|M| \mid M: G\, マッチング \textstyle \} = \min\{{\sum}_{U \in {\mathcal U}} c(U) \mid {\mathcal U}: G\, の奇被覆\}.\,

 2部グラフ G = (V^+, V^-; A)\, において, |M| = |V^+|\, であるマッチング M\, を, 左側端点集合 V^+\, に関する完全マッチングという. 左側端点集合 V^+\, に関する完全マッチング存在するための必要十分条件次のように書ける:


|U^+| \leq |\{v \in V^- \mid \ u \in U^+, (u, v) \in A\}| \qquad
(\forall U^+ \subseteq V^+).
\,


これを, ホールの定理 (Hall's theorem) と呼ぶ.

 最小被覆族の構造に基づいた2部グラフ分解としてダルメジ・メンデルゾーン分解 (Dulmage-Mendelsohn decomposition) が知られている. 略してDM分解呼ばれる. この分解は, 与えられた2部グラフを, 半順序構造有する部分グラフの族へと一意的分解する. DM 分解は, 連立一次方程式を解く際にも有用である. 係数行列関連する2部グラフDM分解用いて係数行列ブロック三角化が出来, これにより計算時間削減することができる.

(b) 最大重みマッチング問題 無向グラフ G = (V, A)\, 及び各 a \in A\, 重み w(a) \in \mathbf{R}\, 与えられたとき, 重みの和 \textstyle {\sum}_{a \in M}w(a)\, 最大にするマッチング M \subseteq A\, 求め問題最大重みマッチング問題と呼ぶ. 最大重みk\, -マッチング問題, 最大重み完全マッチング問題も同様に定義される. 2部グラフにおける最大重み完全マッチング問題は割当問題 (assignment problem) とも呼ばれる.

 最大重みマッチング求めるときも, 最大マッチング同様に 増加道を用いて繰り返しマッチング数を増やしていき, 最終的所望マッチング求めることができる. その際, 各反復でのマッチングある種最適性満たすように, 増加道をうまく選ぶ必要がある.

 一般グラフ場合には, まず最大重みマッチング問題を線形計画問題として定式化し, そこから現れる相補性条件考え,その条件満たされるように増加道を選ぶ. 特に, G\, 2部グラフ場合は, マッチング重み増加量が最大となるように, 各反復において増加道を選べば良い. いずれの場合も, 多項式時間最大重みマッチング求めることが出来る. 以上のような主双対算法の他に多く解法提案されている.

(c) 安定結婚問題 2部グラフでのマッチング問題の一種として, 安定結婚問題が挙げられる. 同じ人数男性女性存在して, 各々異性に対して結婚相手としての選好順序をもつと仮定する. ここで, 男女全て結婚させること, すなわち男女間の完全マッチングについて考える. 男女間の完全マッチング与えられたとき, それが安定であるとは, 結婚ていない男性女性任意の(m, f)\, に対して, m\, f\, より現在の結婚相手を好むか, または f\, m\, より現在の結婚相手を好むことである. 男女間の安定な完全マッチング求め問題安定結婚問題と呼ぶ.

 安定な完全マッチングは常に存在し, ゲイル・シャプレー(Gale-Shapley) の解法により多項式時間求められる. この解法では, 各々男性は1番目に好きな女性から, 2番目に好きな女性, ...と順に, 拒否されたら順位1つ下げて, 求婚する. 一方, 各々女性求婚してきた男性のうち, 最も好きな人との結婚を仮受託し, それ以外の求婚してきた男性拒否する. この手順を繰り返し, すべての女性が仮受託したら終了であり, 安定な完全マッチング求められる.



参考文献

[1] R. K. Ahuja, T. L. Magnanti and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall, 1993.

[2] W. J. Cook, W. H. Cunningham, W. R. Pulleyblank and A. Schrijver, Combinatorial Optimization, John Wiley & Sons, 1998.

[3] 重悟,『離散数学』, 岩波講座応用数学基礎12, 岩波書店, 1993.

[4] 重悟,『グラフ・ネットワーク・組合せ論』, 工系数学講座18, 共立出版, 2002.

[5] D. Gusfield and R. W. Irving, The Stable Marriage Problem: Structure and Algorithms, MIT Press, 1989.

[6] 伊理正夫, 重悟, 大山達雄,『グラフ・ネットワーク・マトロイド』, 産業図書, 1986.

[7] B. Korte and J. Vygen, Combinatorial Optimization, 4th ed., Springer, 2007. 浅野孝夫,平田富夫小野孝男,浅野泰仁訳,『組合せ最適化理論アルゴリズム (第2版) 』、シュプリンガー・フェアラーク東京,2005.

[8] E. L. Lawler, Combinatorial Optimization, Networks and Matroids, Holt, Rinehart and Winston, 1976.

[9] L. Lovász and M. D. Plummer, Matching Theory, North-Holland, 1986.

[10] C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization, Algorithms and Complexity, Prentice-Hall, 1982.

[11] W. R. Pullyblank, "Matchings and Extensions," in Handbook of Combinatorics, Vol. I, R. L. Graham, M. Grötschel and L. Lovász, eds., North-Holland, 1995.

[12] A.Schrijver, Combinatorial Optimization, Polyhedra and Efficiency, Springer, 2003.




英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「マッチング問題]]」の関連用語

マッチング問題]]のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



マッチング問題]]のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

  
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会
Copyright (C) 2021 (社)日本オペレーションズ・リサーチ学会 All rights reserved.

©2021 GRAS Group, Inc.RSS