EdgeCoverQ

EdgeCoverQ[g,elist]

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

詳細

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

予備知識

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

例題

すべて開くすべて閉じる

例  (2)

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

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

スコープ  (6)

無向グラフを調べる：

有向グラフ：

多重グラフ：

混合グラフ：

EdgeCoverQはグラフではない式に対してはFalseを与える：

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

アプリケーション  (2)

すべての辺被覆を列挙する：

辺のすべての部分集合を列挙し被覆を選ぶ：

被覆をハイライトする：

すべての最小辺被覆を列挙する：

最小辺被覆の長さを求める：

長さが3の辺の部分集合すべてを求め被覆を選ぶ：

最小被覆をハイライトする：

特性と関係  (4)

孤立した頂点がないグラフの場合，EdgeListは辺被覆である：

最小の辺被覆はFindEdgeCoverで求められる：

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

連結グラフの場合，独立辺集合と辺被覆の合計のサイズは頂点数に等しい：

Wolfram Research (2010), EdgeCoverQ, Wolfram言語関数， https://reference.wolfram.com/language/ref/EdgeCoverQ.html （2014年に更新）.

テキスト

Wolfram Research (2010), EdgeCoverQ, Wolfram言語関数， https://reference.wolfram.com/language/ref/EdgeCoverQ.html （2014年に更新）.

CMS

Wolfram Language. 2010. "EdgeCoverQ." Wolfram Language & System Documentation Center. Wolfram Research. Last Modified 2014. https://reference.wolfram.com/language/ref/EdgeCoverQ.html.

APA

Wolfram Language. (2010). EdgeCoverQ. Wolfram Language & System Documentation Center. Retrieved from https://reference.wolfram.com/language/ref/EdgeCoverQ.html

BibTeX

@misc{reference.wolfram_2024_edgecoverq, author="Wolfram Research", title="{EdgeCoverQ}", year="2014", howpublished="\url{https://reference.wolfram.com/language/ref/EdgeCoverQ.html}", note=[Accessed: 18-November-2024 ]}

BibLaTeX

@online{reference.wolfram_2024_edgecoverq, organization={Wolfram Research}, title={EdgeCoverQ}, year={2014}, url={https://reference.wolfram.com/language/ref/EdgeCoverQ.html}, note=[Accessed: 18-November-2024 ]}