エッジカバー

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

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

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

右側の図は、辺被覆であるだけでなく、マッチングでもあることに注意してください。特に、これは完全マッチングです。つまり、M 内のすべての頂点が、 M内のちょうど 1 つの辺と接続しているマッチングMです。完全マッチング (存在する場合) は常に最小辺被覆です。

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

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

画像を見ると、なぜ特定の最小エッジカバーに対して${\displaystyle C}$最大一致${\displaystyle M}$許可する${\displaystyle c}$そして${\displaystyle m}$エッジの数を${\displaystyle C}$そして${\displaystyle M}$それぞれ、次のようになります。^{[ 3 ]}${\displaystyle |V|=c+m}$。 確かに、${\displaystyle C}$最大マッチングが含まれているため、エッジは${\displaystyle C}$分解できる${\displaystyle m}$最大マッチングのエッジを覆う${\displaystyle 2m}$頂点、そして${\displaystyle cm}$他の辺はそれぞれ他の頂点を1つずつ覆っています。したがって、${\displaystyle C}$すべての${\displaystyle |V|}$頂点、${\displaystyle |V|=2m+(cm)}$望ましい平等性を実現する。

• 頂点カバー
• 集合被覆問題― 辺被覆問題は集合被覆問題の特殊なケースです。宇宙の要素は頂点であり、各部分集合はちょうど2つの要素を覆います。

• ワイススタイン、エリック W. 「エッジカバー」 . MathWorld .
• Garey, Michael R. ; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , WH Freeman, ISBN 0-7167-1045-5。