Vertex cycle cover とは

数学では、グラフGの頂点サイクルカバー(一般に単にサイクルカバーと呼ばれる)は、Gのサブグラフであり、Gのすべての頂点を含むサイクルのセットである。
カバーのサイクルが共通の頂点を持たない場合、カバーは頂点 – 分離または時には単に分離したサイクルカバーと呼ばれます。この場合、サイクルの集合は、Gのスパニング・サブグラフを構成する。無向グラフ(存在する場合)の独立したサイクル・カバーは、問題を大きなグラフで完璧な一致を見つける問題に変換することによって多項式時間で見つけることができる。
カバーのサイクルに共通のエッジがない場合、カバーはエッジ・ディスジョイントまたは単にディスジョイント・サイクル・カバーと呼ばれます。
有向グラフに関して、有向グラフについても同様の定義が存在する。