予選A-D 「ハシポン」
ハシポングラフとは2つの二重辺連結成分からなるグラフです。
二重辺連結成分については、http://www.slideshare.net/chokudai/arc039 を参照してください。 辺を追加して、2つの二重辺連結成分にするには最小何本の辺を追加する必要があるかを求めます。
ただし、ここでは連結な無向単純グラフのみを考えます。
1つの二重辺連結成分にするには
与えられたグラフに辺を追加して1つの二重辺連結成分にすることを考えます。
まず、頂点数2のグラフは2つは多重辺になってしまうので辺を追加できません。よって、頂点数2のグラフは辺を追加して1つの二重辺連結成分にすることができません。
ただし、頂点数が2より大きい、2つの二重辺連結成分からなるグラフは、1本の辺を追加して1つの二重辺連結成分にすることができることには注意が必要です。
ある辺の両端の頂点を1つの頂点にまとめてしまうことを縮約といいます。二重辺連結成分分解をおこない、二重辺連結成分を縮約して1つの頂点にしたグラフを考えます。縮約後のグラフ上では全ての辺が橋であり、グラフは木になっています。この木の頂点数2の場合は既に考えたので、この木の頂点数は3以上とします。
この木の葉の数が2の場合 葉の間に辺を1本追加することで、1つの二重辺連結成分にすることができます。
この木の葉の数が3の場合 2つの葉を選んでその間に辺を1本追加し二重辺連結成分を縮約すると、葉の数を2にすることができます。
この木の葉の数が4以上の場合 2つの葉を選んでその間に辺を1本追加し二重辺連結成分を縮約したとき、 その縮約した頂点が葉になる場合は葉が1つ減り、 その縮約した頂点が葉にならない場合は葉が2つ減ります。 また、その縮約した頂点が葉にならないような2つの葉の選び方はかならず存在します。(証明略)
以上より、1つの二重辺連結成分にするために追加する必要がある辺の本数は、元のグラフが n 個の二重辺連結成分だったとすると、n = 1 の場合は 0 、 n > 1 の場合は floor(n / 2) 、になります。
ただし、頂点数2の場合は除きます。
2つの二重辺連結成分にするには
二重辺連結成分を縮約した木を考えます。
辺(u,v) を選び、u側の葉の数をm, v側の葉の数をnとします。
木の葉の数をLとすると、 m + n = L になります。
頂点u, vの次数に関して場合分けをします。ただし、 uの次数 <= vの次数 とします。
uの次数 = 1, vの次数 = 1の場合 答えは 0 です。uの次数 = 1, vの次数 = 2の場合 m = 1, n = L - 1であり、 答えは floor(L / 2) です。uの次数 = 1, vの次数 > 2の場合 m = 1, n = L - 1であり、 答えは floor((L - 1) / 2) です。uの次数 = 2, vの次数 = 2の場合 答えは floor((m+1) / 2) + floor((n+1) / 2) です。uの次数 = 2, vの次数 > 2の場合 答えは floor((m+1) / 2) + floor(n / 2) です。uの次数 > 2, vの次数 > 2の場合 答えは floor(m / 2) + floor(n / 2) です。
木の頂点数が2であれば、1. に、3以上であれば 2.～6. になります。
3.になるような辺が存在するのであれば、この答えが最小となります。
存在しないのであれば、floor(m / 2) + floor(n / 2) >= floor(L / 2) なので、
2.の答えが最小となります。