最大マッチング最小被覆定理とは？

辞典・百科事典の検索サービス - Weblio辞書

初めての方へ

参加元一覧


用語解説|全文検索
Weblio 辞書 > 学問 > OR事典 > 最大マッチング最小被覆定理の意味・解説 

OR事典
日本オペレーションズ・リサーチ学会日本オペレーションズ・リサーチ学会

最大マッチング最小被覆定理

読み方：さいだいまっちんぐさいしょうひふくていり
【英】：maximum-matching minimum-cover theorem

2部グラフ G = (V, A) \, において, 最大マッチングの枝数と最小被覆の点数は等しい, すなわち


\max\{|M| \mid M \subseteq Aは G \, のマッチング\} \,

= \min\{|U| \mid U \subseteq V \, は G \, の被覆\}, \,


という定理. ケーニグ(König)の定理, またはケーニグ・エゲルヴァーリ(König-Egerváry)の定理とも呼ばれる.

「OR事典」の他の用語
グラフ･ネットワーク：  循環フロー  最大フローアルゴリズム  最大フロー最小カット定理  最大マッチング最小被覆定理  最小木問題  最小費用フロー問題  最短路問題

索引トップ用語の索引ランキングカテゴリー


>> 「最大マッチング最小被覆定理」を解説文に含む用語の一覧

>> 「最大マッチング最小被覆定理」を含む用語の索引
最大マッチング最小被覆定理のページへのリンク
「最大マッチング最小被覆定理」の関連用語
1
マッチング問題
OR事典
32% |||||

注目の情報

最大マッチング最小被覆定理のお隣キーワード

暴露目標探知確率

最大エントロピー法

最大カット問題

最大クリーク問題

最大フローアルゴリズム

最大フロー最小カット定理

最大マッチング最小被覆定理

最大剰余数法

最大空円

最大除数法

最小コア

最小シュタイナー木

最小二乗法

モバイル
モバイル版のWeblioは、下記のURLからアクセスしてください。
http://m.weblio.jp/
» モバイルで「最大マッチング最小被覆定理」を見る
_ _   

最大マッチング最小被覆定理のページの著作権
Weblio 辞書情報提供元は参加元一覧にて確認できます。

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

©2012 Weblio RSS