最大マッチングと最大フローのまとめ最大マッチング H27 グラフ理論 ―第13回― 最大フロー問題の応用マッチング (頂点を共有しない辺の集合) 増大道 (両端が飽和されていない交互道) 最大マッチング (完全マッチング) 1 最大マッチングと最大フローのまとめ 22/25 25 8 5 3 30 5/5 s t 最大フロー 2/8 2/3 6 V2 3 t t 5 4 15/15 19/19 V1 2 2 5 s 10 22/30 25 c(e)-f(e)=3 5 Δ(P)=4 この二部グラフを図のような有向グラフと考える f(eR)=f(e)=22 15 25/25 3/5 t 10/15 残余ネットワーク s 3/3 15/19 19 27/27 2/8 20/30 15 20/20 二部グラフの最大マッチングは最大フロー問題の特殊ケースである 25/27 15/20 24 s (1) 二部グラフの最大マッチングと最大フローフローの例ネットワーク N = (G,c,s,t) 20 2 20 15 10 3 4 1 このネットワーク上の最大フローを求めるこのグラフに頂点 s,t を追加して s から V1 の頂点への辺と V2 の頂点から t への辺を追加する V1 1 1 V2 1 s 1 1 1/1 1 1 1 1 初期フロー 1/1 s t 1 1 1 t すべての辺eに対して c(e)=1が省略されていると考える 1/1 1 1 1 1 1 1 1 1/1 残余ネットワークの逆辺 1 1/1 1/1 s ここですべての辺容量が c(e)=1 と仮定すれば得られる有向グラフはあるネットワークを表す s t 1 1 1 1 1/1 1 1 1 1 1/1 5 1/1 s 1/1 1 1 1 1 1 1/1 1/1 1 t s 1 1/1 1/1 1 1 1 1 1 1 s t 1 1/1 1 増加道 V2 1/1 1 1 1 1 t 1/1 1/1 1 1/1 V1 V1 1 1/1 t 6 残余ネットワークに s から t への増加道は存在しないので左図が最大フロー最大フロー (0/1は単に1と書いてある) t 1 1 s 1 1 1 1 1/1 1 V2 得られたフローは最大であるので対応するマッチングも最大となるここでフローが存在する辺のうちはじめの二部グラフの辺を選択するとそれはあるマッチングとなるなぜならば辺容量はすべて１なのでフローは合流しない。すなわち合流しない辺の集合はマッチングとなる。以上により最大マッチングは最大フロー問題の特殊な場合と見なせる 7 8 2 (2) 優勝可能性判定への応用セリーグの勝敗表ある年のセリーグの8月の時点での勝敗表と残り試合の組み合わせが与えられたとき、中日にまだ優勝の可能性があるかどうかを判定したい。 (引き分けは後日対戦するので引き分けはないと見なせる) セリーグの勝敗表チーム勝数チーム勝数負数残数ヤクルト６６３８２６広島６２４０２８巨人５６４７２７横浜５２５１２７阪神３６６６２８中日３３６３３４各組合せの残り試合数負数残数対戦残数ヤクルト広島巨人横浜阪神中日ヤクルト６６３８２６ヤクルト－６５５２８広島６２４０２８広島６－７６５４巨人５６４７２７巨人５７－３６６横浜５２５１２７横浜５６３－６７阪神３６６６２８阪神２５６６－９中日３３６３３４中日８４６７９・中日は最大67勝する可能性がある・それ以外のチームが68勝しないようにすべての試合を終了できるかどうかを判定すればよい・68勝未満が中日を含めて複数あればプレーオフがあるので優勝の可能性はある最大であと34勝しかできないので中日の最大勝数は67である。すべての試合をこれを上回らないように消化できるか？－ 9 10 “計算とアルゴリズム淺野孝夫・今井浩” Ohmshaより抜粋 s 各組合せの残り試合数 6 対戦残数ヤクルト広島巨人横浜阪神中日ヤクルト－６５５２８広島６－７６５４巨人５７－３６６横浜５６３－６７阪神２５６６－９中日８４６７９－・試合の組み合わせには順序がないので残り試合の表は対角線に対して対称である。・中日の優勝の可能性なので中日は残りを全勝すると考え、それ以外の組み合わせの勝敗を考える。 11 5 5 2 7 6 5 3 6 6 ヤ×広ヤ×巨ヤ×横ヤ×阪広×巨広×横広×阪巨×横巨×阪横×阪各組合せの残り試合数対戦残数ヤクルト広島巨人横浜阪神中日ヤクルト－６５５２８広島６－７６５４巨人５７－３６６横浜５６３－６７阪神２５６６－９中日８４６７９－・中日を除いた残りのチームの組み合わせを考える・各組み合わせの残り試合数を辺容量としてネットワークを構成(図) 12 3 s 6 5 5 2 s 7 6 5 3 6 6 6 ヤ×広ヤ×巨ヤ×横ヤ×阪広×巨広×横広×阪巨×横巨×阪横×阪 6 5 2 7 6 5 3 6 6 ヤ×広ヤ×巨ヤ×横ヤ×阪広×巨広×横広×阪巨×横巨×阪横×阪 6 ヤこの二辺のキャパシティー (他の辺の値は省略) 広巨横阪図のように中日以外の5チームに勝ち数を分配するネットワークを追加する (例えばヤ×広の6試合の勝数はヤクルトまたは広島に分配される→最大6のフローが図の二つの辺に分かれる) チーム勝数負数残数ヤクルト６６３８２６広島６２４０２８巨人５６４７２７横浜５２５１２７残り試合数はこれらのキャパシティーの合計で51試合(かならず消化しなければならない試合数) s 5 5 2 7 6 5 3 6 ヤ広 1 阪神３６６６２８中日３３６３３４ 13 6 5 巨 5 横 15 11 阪 31 t それぞれのチーム(ヤ～阪の5チーム)が 67勝になるまでの勝数を辺容量として設定したネットワークを追加して完成 14 (3) 画像の2値分解への応用（概略） 6 各画素がノードに対応ヤ×広ヤ×巨ヤ×横ヤ×阪広×巨広×横広×阪巨×横巨×阪横×阪 S ヤ広 1 巨 5 横 15 11 阪 31 t 入力画像図のネットワークの最大フロー f は50 (計算は省略) 合計51のフローをtに流し込むにはどこかの辺のフローがキャパシティーをオーバーする中日以外のチームが68勝以上してしまう(中日の優勝の可能性はない) 15 隣り合う画素同士を辺で結び，画素値が近いものほど重みを大きくするグラフの最小カットを求めることで原画像 2値分解できる． 16 4 画像の2値分解の実際（古文書からの手書き文字の認識*）入力画像 *(平成24年度：坂本研の修士論文研究より抜粋) 「画像データからの知識獲得ツールの開発」文字領域の抽出結果 17 5