グラフの被覆と独立集合

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

参照項目参照項目

完全な部分グラフ

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

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

頂点被覆

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

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

辺被覆

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

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

独立頂点集合

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

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

独立辺集合

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

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

New to Mathematica? Find your learning path »
Have a question? Ask support »