2

二部グラフG = ( U , V , E ) が与えられた場合、 Gの連結成分の 1 つの「側」であるVのすべての (最大) サブセットを見つけたいと考えています。

たとえば、入射行列の場合

    0 1 0 0 0 1
    1 0 0 0 0 1
    0 0 0 0 0 0
A = 0 0 0 0 1 0
    0 0 1 0 1 0
    0 1 0 0 0 0
    0 0 0 1 0 0

ここで、行インデックスはUを表し、列インデックスはVを表し、出力はセット {0, 1, 5}、{2, 4}、および {3} になります。

これは標準的な問題と同等ですか? もっと言えば、効率的な解決策はありますか?

4

1 に答える 1

1

これは、辺と頂点の数が線形であるグラフのすべての連結要素を見つけることに似ています。このアプローチの標準アルゴリズムは、すべての頂点に対して幅優先または深さ優先の検索を行うことです。

このアルゴリズムに関連する定数を減らすことを除いて、グラフの 2 部構成の性質を利用することで複雑さがスピードアップするとは思いません。

于 2012-11-06T17:12:13.190 に答える