WolframのWebサイトのコンテンツとインタラクトしたりフォームを送信したりするためには，JavaScriptを有効にしてください．有効にする方法

FindEdgeCover

FindEdgeCover[g]

グラフ g の辺の数が最小の辺被覆を求める．

FindEdgeCover[{vw,…}]

規則 vw を使ってグラフ g を指定する．

詳細

辺被覆はすべての頂点に接続している辺集合である．

FindEdgeCoverは辺のリストを返す．
辺被覆が見付からない場合，FindEdgeCoverは空のリストを返す．
FindEdgeCoverは，無向グラフ，有向グラフ，重み付きグラフ，多重グラフ，混合グラフに使うことができる．

予備知識

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

例題

すべて開くすべて閉じる

例 (1)

辺被覆を求める：

被覆を示す：

スコープ (8)

FindEdgeCoverは無向グラフに使うことができる：

有向グラフ：

重み付きグラフ：

多重グラフ：

混合グラフ：

規則を使ってグラフを指定する：

FindEdgeCoverは辺被覆が存在しない場合は空の結果を返す：

FindEdgeCoverは，大きいグラフに使うことができる：

特性と関係 (5)

辺被覆内の辺はすべての頂点に結合している：

辺集合が辺被覆かどうかをEdgeCoverQを使って調べる：

連結グラフの場合，独立辺集合と辺被覆のサイズの和は頂点数に一致する：

完全二部グラフにはの辺被覆がある：

StarGraphの辺被覆はそのすべての辺を含む：

トップへ