エッジカバー

グラフ理論では、グラフのエッジ カバーとは、グラフのすべての頂点が少なくとも 1 つのエッジに接続されているエッジの集合です。コンピューター サイエンスでは、最小エッジ カバー問題は、最小サイズのエッジ カバーを見つける問題です。これは、カバー問題のクラスに属し、多項式時間で解決できる最適化問題です。

正式には、グラフGの辺被覆とは、 Gの各頂点がCの少なくとも 1 つの辺と接続する辺Cの集合です。集合C はGの頂点を被覆すると言われています。次の図は、 2 つのグラフの辺被覆の例を示しています (集合Cは赤でマークされています)。

最小辺被覆とは、可能な限り小さいサイズの辺被覆のことです。辺被覆数 ρ ( G )は、最小辺被覆のサイズです。次の図は、最小辺被覆の例を示しています (ここでも、集合Cは赤でマークされています)。

右の図はエッジカバーだけでなくマッチングでもあることに注意してください。特に、これは完全マッチング、つまりすべての頂点がM内の 1 つのエッジと正確に接続しているマッチングMです。完全マッチング (存在する場合) は常に最小エッジカバーです。

• すべてのエッジの集合は、次数 0 の頂点が存在しないと仮定して、エッジ カバーです。
• 完全二部グラフ K _m,nの辺被覆数はmax( m , n )である。

最小のエッジカバーは、最大マッチングを見つけ、それを貪欲に拡張してすべての頂点がカバーされるようにすることで、多項式時間で見つけることができます。 ^{[1] [2]}次の図では、最大マッチングは赤でマークされています。一致しないノードをカバーするために追加された余分なエッジは青でマークされています。（右の図は、最大マッチングが完全なマッチングであるグラフを示しています。したがって、すでにすべての頂点がカバーされており、余分なエッジは必要ありませんでした。）

一方、最小の頂点被覆を見つけるという関連問題はNP困難問題である。^[1]

この図を見ると、最小辺被覆と最大マッチング が与えられているときに、との辺の数をそれぞれ ととすると、次式が得られる理由は既に明らかです。^[3]。確かに には最大マッチング が含まれているので、 の辺は、頂点を覆う最大マッチングの辺と、それぞれが他の 1 つの頂点を覆うその他の辺の間で分解できます。したがって、 がすべての頂点を覆うので、が得られ、必要な等式が得られます。 ${\displaystyle C}$ ${\displaystyle M}$${\displaystyle c}$${\displaystyle m}$${\displaystyle C}$${\displaystyle M}$ ${\displaystyle |V|=c+m}$${\displaystyle C}$${\displaystyle C}$${\displaystyle m}$${\displaystyle 2m}$${\displaystyle cm}$${\displaystyle C}$${\displaystyle |V|}$${\displaystyle |V|=2m+(cm)}$

• 頂点カバー
• 集合被覆- エッジ被覆問題は集合被覆問題の特殊なケースです。つまり、宇宙の要素は頂点であり、各サブセットは正確に 2 つの要素を被覆します。

• Weisstein、Eric W.「Edge Cover」。MathWorld。
• ゲイリー、マイケル・R. ;ジョンソン、デビッド・S. (1979)、「コンピュータと扱いにくさ：NP完全性理論へのガイド」、WHフリーマン、ISBN 0-7167-1045-5。