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

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

[![V2の、上から2個目と4個目の点を削除すると、すべてのv∈V1は1本のみの枝を持つ](https://i.stack.imgur.com/voDmO.jpg)](https://i.stack.imgur.com/voDmO.jpg)
CC BY-SA 3.0
2015-09-14T14:58:23.743
16606
2020-02-18T15:05:53.817
2015-09-14T16:17:44.997
754
12269
question
アルゴリズム グラフ理論
2部グラフ(V1, V2, E)で、V2からいくつか頂点を削除し、すべてのv∈V1が、1本のみの枝をもつようにするには？
グラフを、対応する論理式に落とし込んで変形していくことにより解けそうです。

## 考え方

まず、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 を削除すればよいことが分かります。

## 例 - 解なし

以下の例を考えます。

[![解なし例](https://i.stack.imgur.com/XjPA4.png)](https://i.stack.imgur.com/XjPA4.png)

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

```

                    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))
>
> = ⊥

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

## 例 - 重解

以下の例を考えます。

[![重解例](https://i.stack.imgur.com/rPz9q.png)](https://i.stack.imgur.com/rPz9q.png)

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

```

                    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通りの解があることが分かります。
CC BY-SA 3.0
2015-09-15T11:38:06.400
16643
2015-09-15T12:20:14.283
2015-09-15T12:20:14.283
7831
7831
16606
answer
Exact Cover という Wikipedia にも載ってる有名問題です．
CC BY-SA 4.0
2020-02-18T15:05:53.817
63160
2020-02-18T15:05:53.817
37877
16606
answer