2部グラフ(V1, V2, E)があります。
V2から点をいくつか削除し、それら点に紐付いていた枝を削除することで、すべてのv∈V1が1本のみの枝を持つ部分グラフ(V1, V', E')を作りたいのですが、
そのようなV'の存在の有無を判定し、また、その条件を満たすV'を少なくとも1つ得るには、どうすればいいでしょうか。
図のように、V2からいくつか点を削除したV'を得たいです。
このようなV'が複数ある場合も、1通りのみ得られたら構いません。
2部グラフ(V1, V2, E)があります。
V2から点をいくつか削除し、それら点に紐付いていた枝を削除することで、すべてのv∈V1が1本のみの枝を持つ部分グラフ(V1, V', E')を作りたいのですが、
そのようなV'の存在の有無を判定し、また、その条件を満たすV'を少なくとも1つ得るには、どうすればいいでしょうか。
図のように、V2からいくつか点を削除したV'を得たいです。
このようなV'が複数ある場合も、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 の状態を以下のように表します。
これを用いて、「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)
となります。ふたつの項が残るので、
の2通りの解があることが分かります。