グラフの被覆と独立集合

典型的なグラフ問題に,好みが与えられた場合の男性と女性のデートや,さまざまな好みに応じた先生とコース等,異なる事柄を合致させるという問題がある.これらはすべて,最大独立辺問題の例である.同様のリソース割当て問題は被覆と独立集合問題すべてに関連する.

参照項目参照項目

完全な部分グラフ

FindClique 完全な部分グラフを求める

CompleteGraphQ グラフが完全なグラフであるかどうか検証する

頂点被覆

FindVertexCover 全辺に接続する頂点集合を求める

VertexCoverQ 頂点集合が頂点被覆であるかどうか検証する

辺被覆

FindEdgeCover 全頂点に接続する辺集合を求める

EdgeCoverQ 辺集合が辺被覆であるかどうか検証する

独立頂点集合

FindIndependentVertexSet 同じ辺に決して接続することのない頂点集合を求める

IndependentVertexSetQ 頂点集合が独立頂点集合であるかどうか検証する

独立辺集合

FindIndependentEdgeSet 同じ頂点に決して接続することのない辺集合(「適合するもの」)を求める

IndependentEdgeSetQ 辺集合が独立辺集合であるかどうか検証する