辺被覆

グラフ理論において、グラフの辺被覆とは、グラフのすべての頂点がその集合の少なくとも1つの辺の端点となるような辺の集合です。コンピュータサイエンスにおいて、最小辺被覆問題は、最小サイズの辺被覆を見つける問題です。これは被覆問題のクラスに属し、 多項式時間で解くことができる最適化問題です

定義

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

最小辺被覆とは、可能な限り最小の大きさの辺被覆のことです。辺被覆数 ρ ( G )は、最小辺被覆の大きさです。次の図は、最小辺被覆の例を示しています（ここでも、集合Cは赤で示されています）。

右の図は辺被覆であるだけでなく、マッチングでもあることに注意してください。特に、これは完全マッチング、つまりMのどの頂点も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つの要素を被覆します

注釈

1. Garey & Johnson (1979)、p. 79では、辺被覆と頂点被覆を、類似した問題のペアの一例として挙げています。これらの問題のうち、1つは多項式時間で解くことができますが、もう1つはNP困難です。p. 190も参照してください
2. Lawler, Eugene L. (2001), 組合せ最適化：ネットワークとマトロイド, Dover Publications, pp.  222– 223, ISBN 978-0-486-41453-9。
3. 「最小辺被覆と最大マッチングの合計が頂点数であることを証明しなさい」Mathematics Stack Exchange。2024年2月18日閲覧

参考文献

• ワイスタイン、エリック・W.「エッジカバー」。MathWorld
• ゲイリー、マイケル・R. ;ジョンソン、デイビッド・S. (1979)、「コンピュータとイントラクタビリティ：NP完全性理論へのガイド」、WHフリーマン、ISBN 0-7167-1045-5。