Search on the blog

2016年10月2日日曜日

直線型グラフのマッチング数

 以下のような直線型グラフのマッチングについて考える。
一般にノード数nの直線型グラフからk個のマッチングを選ぶパターン数はn-kCkとなる。

例えば上のグラフの場合(n=6)は、
k = 1なら6-1C= 5、
k = 2なら6-2C= 6、
k = 3なら6-3C= 1
となり、実際に個数を数えてみると正しいことが分かる。

何をやってるかというと、マッチングに使われる枝の左側のノードを選んでいるわけである。普通にノードを選ぶだけだと一つのノードが複数のマッチングに属してしまうかもしれないので、あらかじめ右側の端点に使われるノードを除いておく。

すると左側のノードの選び方により一意にマッチングが決定する。逆にマッチングの選び方に対して、左側のノードの選び方は一意に決まる。よって一対一の対応にあるのでこの方法で数え上げができることが分かる。




0 件のコメント:

コメントを投稿