ハイパーグラフの頂点被覆
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/11/22 03:31 UTC 版)
「頂点被覆」の記事における「ハイパーグラフの頂点被覆」の解説
頂点被覆はハイパーグラフにも自然に一般化でき、単に「ハイパーグラフの頂点被覆」とも呼ばれるが、ヒッティングセット (hitting set) という呼び方が一般化している。また、組合せ論的には横断 (transversal) とも呼ぶ。さらに言えば、ヒッティングセットと集合被覆は等価である。 形式的には、ハイパーグラフ H=(V,E) は頂点集合 V とハイパーエッジ集合 E から成る。集合 S ⊆ V がヒッティングセットとなるのは、全てのハイパーエッジ e ∈ E について S ∩ e ≠ ∅ が成り立つ場合である。計算問題としての「最小ヒッティングセット」と「ヒッティングセット問題」はグラフの場合と同様に定義される。 なお、ハイパーエッジの最大サイズが2のハイパーグラフは普通のグラフと同じである。ハイパーエッジの大きさを d までに制限すると、最小d-ヒッティングセットを求める問題にはd-近似アルゴリズムがある。
※この「ハイパーグラフの頂点被覆」の解説は、「頂点被覆」の解説の一部です。
「ハイパーグラフの頂点被覆」を含む「頂点被覆」の記事については、「頂点被覆」の概要を参照ください。
ウィキペディア小見出し辞書の「ハイパーグラフの頂点被覆」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- ハイパーグラフの頂点被覆のページへのリンク
