FindEdgeCover

FindEdgeCover[g]
グラフ g の辺の数が最小の辺被覆を求める.

詳細詳細

  • 辺被覆はすべての頂点に接続している辺集合である.
  • FindEdgeCoverは辺のリストを返す.
  • 辺被覆が見付からない場合,FindEdgeCoverは空のリストを返す.
  • FindEdgeCoverは,無向グラフ,有向グラフ,重み付きグラフ,多重グラフ,混合グラフに使うことができる.

予備知識
予備知識

  • FindEdgeCoverは,グラフの単一の最小辺被覆を求め,結果を辺のリストとして返す.ここで,辺被覆とは少なくとも1本の辺の端点がグラフ中のすべての頂点に接続している辺の集合である.最小辺被覆は可能な最小数の辺を持つ辺被覆である. 最小辺被覆の応用分野には,ソーシャルネットワーク,生物学,社会科学等がある.
  • グラフ の最小辺被覆のサイズ(つまり,辺の数)は,その辺被覆の数として知られ, で示される.辺被覆は多項式時間で求めることができる.
  • EdgeCoverQを使って指定された辺集合(最小である必要はない)が辺被覆かどうかを調べることができる.EdgeCoverQをグラフの可能なすべての辺の部分集合に適用することで, すべての辺被覆を列挙することができ,辺被覆の数と同じサイズの部分集合に適用することですべての最小辺被覆を列挙することができる. FindVertexCoverは同じ概念を頂点に適用する.
2010年に導入
(8.0)
| 2014年に修正
(10.0)