8

2部グラフ(V1, V2, E)があります。
V2から点をいくつか削除し、それら点に紐付いていた枝を削除することで、すべてのv∈V1が1本のみの枝を持つ部分グラフ(V1, V', E')を作りたいのですが、
そのようなV'の存在の有無を判定し、また、その条件を満たすV'を少なくとも1つ得るには、どうすればいいでしょうか。

図のように、V2からいくつか点を削除したV'を得たいです。
このようなV'が複数ある場合も、1通りのみ得られたら構いません。

V2の、上から2個目と4個目の点を削除すると、すべてのv∈V1は1本のみの枝を持つ

2
  • V1の枝を強制的に1本に切り落として、V2から枝がない要素を削除すればお望みのグラフになると思うのですが、それではなにかいけないのでしょうか?
    – sken2
    2015年9月15日 0:11
  • 枝のみを削除することはできません。そうすると、切り落とす枝の選び方を考えなければ、うまくいかないかと。
    – gyu-don
    2015年9月15日 3:22

2 件の回答 2

9

グラフを、対応する論理式に落とし込んで変形していくことにより解けそうです。

考え方

まず、v1,i ∈ V1 と v2,j ∈ V2 がどう繋っているか、表にしてみます。
質問で例示されたグラフでは以下のようになります。o の印があるところが辺で繋がっている組み合わせです。添字 i, j は、図の一番上を1として順番に振りました。

                   V2
          v2,1|v2,2|v2,3|v2,4
         -----+----+----+-----
    v1,1|   o |  o |    |
   -----+-----+----+----+-----
    v1,2|     |  o |  o |
V1 -----+-----+----+----+-----
    v1,3|   o |  o |    |  o
   -----+-----+----+----+-----
    v1,4|     |    |  o |

さて、一行目に着目してみると、 v1,1 は、v2,1 と v2,2 に繋っていますから、v1,1 に 1 本だけ枝が伸びた状態を実現するには、 v2,1 と v2,2 のどちらか一方のみが残されている必要があります。
ここで、 v2,j の状態を以下のように表します。

  • xj : v2,j が残された状態
  • ¬xj : v2,j が削除された状態

これを用いて、「v2,1 と v2,2 のどちらか一方のみが残されている」状態を表すと、以下のようになります。

(x1 ∧ ¬x2) ∨ (¬x1 ∧ x2)

つまり、関連する xj のうち、ひとつのみを肯定形、残りを否定形にして and で繋いだ形の全パターンを or で繋いだものです。
二行目以降も同様に、それぞれ以下のように表せます。

(x2 ∧ ¬x3) ∨ (¬x2 ∧ x3)
(x1 ∧ ¬x2 ∧ ¬x4) ∨ (¬x1 ∧ x2 ∧ ¬x4) ∨ (¬x1 ∧ ¬x2 ∧ x4)
x3

目的の条件を満足するためには、これらすべてを満たす必要がありますから、すべて and で繋げます。

((x1 ∧ ¬x2) ∨ (¬x1 ∧ x2))
∧ ((x2 ∧ ¬x3) ∨ (¬x2 ∧ x3))
∧ ((x1 ∧ ¬x2 ∧ ¬x4) ∨ (¬x1 ∧ x2 ∧ ¬x4) ∨ (¬x1 ∧ ¬x2 ∧ x4))
∧ (x3)

これを展開していきます。途中、 ⊥ になったもの、つまり、論理積の中に xj と ¬xj が同時に表れたものはどんどん消していきます。

((x1 ∧ ¬x2 ∧ x2 ∧ ¬x3) ∨ (x1 ∧ ¬x2 ∧ ¬x2 ∧ x3)
∨ (¬x1 ∧ x2 ∧ x2 ∧ ¬x3) ∨(¬x1 ∧ x2 ∧ ¬x2 ∧ x3))
∧ ((x1 ∧ ¬x2 ∧ ¬x4) ∨ (¬x1 ∧ x2 ∧ ¬x4) ∨ (¬x1 ∧ ¬x2 ∧ x4))
∧ (x3)

= ((x1 ∧ ¬x2 ∧ x3) ∨ (¬x1 ∧ x2 ∧ ¬x3))
∧ ((x1 ∧ ¬x2 ∧ ¬x4) ∨ (¬x1 ∧ x2 ∧ ¬x4) ∨ (¬x1 ∧ ¬x2 ∧ x4))
∧ (x3)
...
= x1 ∧ ¬x2 ∧ x3 ∧ ¬x4

最終的に得られた式に残っている否定形は ¬x2 と ¬x4 ですから、v2,2 と v2,4 を削除すればよいことが分かります。

例 - 解なし

以下の例を考えます。

解なし例

このグラフの枝情報を同様に表にします。

                V2
          v2,1|v2,2|v2,3
         -----+----+-----
    v1,1|   o |  o |
   -----+-----+----+----
V1  v1,2|     |  o |  o
   -----+-----+----+----
    v1,3|   o |    |  o

これを論理式に落とし込んで変形すると

((x1 ∧ ¬x2) ∨ (¬x1 ∧ x2))
∧ ((x2 ∧ ¬x3) ∨ (¬x2 ∧ x3))
∧ ((x3 ∧ ¬x1) ∨ (¬x3 ∧ x1))

= ⊥

となり、解なしとなります。

例 - 重解

以下の例を考えます。

重解例

このグラフの枝情報を同様に表にします。

                V2
          v2,1|v2,2|v2,3
         -----+----+-----
    v1,1|   o |  o |
   -----+-----+----+----
V1  v1,2|   o |  o |
   -----+-----+----+----
    v1,3|   o |    |  o

これを論理式に落とし込んで変形すると

((x1 ∧ ¬x2) ∨ (¬x1 ∧ x2))
∧ ((x1 ∧ ¬x2) ∨ (¬x1 ∧ x2))
∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3))

= (x1 ∧ ¬x2 ∧ ¬x3) ∨ (¬x1 ∧ x2 ∧ x3)

となります。ふたつの項が残るので、

  • v2,2 と v2,3 を削除する (x1 ∧ ¬x2 ∧ ¬x3 に対応)
  • v2,1 を削除する (¬x1 ∧ x2 ∧ x3 に対応)

の2通りの解があることが分かります。

1

Exact Cover という Wikipedia にも載ってる有名問題です.

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。