EdgeCoverQ

EdgeCoverQ[g,elist]
辺のリスト elist がグラフ g の辺被覆である場合にはTrueを,それ以外の場合にはFalseを返す.

詳細詳細

  • 辺被覆はすべての頂点と接続している辺の集合のことである.
  • EdgeCoverQは,無向グラフ,有向グラフ,多重グラフ,混合グラフに用いることができる.

予備知識
予備知識

  • EdgeCoverQは,指定された辺のリストが指定されたグラフの辺被覆かどうかを調べる.辺被覆とは,グラフのすべての頂点に接続している(つまり,辺の端点がグラフの頂点を「被っている」)グラフの辺の集合である.辺被覆の応用分野としては,ソーシャルネットワーク,生物学,社会科学等がある.
  • 指定されたグラフの可能な最小数の辺を持つ辺被覆は,最小辺被覆として知られ,FindEdgeCoverを使って求めることができる.EdgeCoverQを可能なすべての辺の部分集合に適用すると,すべての辺被覆を列挙することができ,最小辺被覆と同じサイズの部分集合に適用すると,すべての最小辺被覆を列挙することができる.
  • VertexCoverQは,同じ概念を頂点に対して適用する.

例題例題すべて開くすべて閉じる

  (2)  (2)

ある辺の集合が完全グラフの辺被覆かどうかを調べる:

In[1]:=
Click for copyable input
Out[1]=

グラフ中のすべての辺集合が辺被覆である訳ではない:

In[1]:=
Click for copyable input
Out[1]=
2010年に導入
(8.0)
| 2014年に修正
(10.0)