東京大学 新領域創成科学研究科 メディカル情報生命専攻 2026年1月実施 問題8
Author
祭音Myyura
Description
を点集合 、辺集合 の単純連結無向グラフとする。 の要素数を とする。 を 2 分割したもの を のカットと呼ぶ。
ここで と は , , , , , を満たし、 と を入れ替えたペア
、 は区別しないものとする。カット のカットサイズを と をまたぐ辺の個数として定義する。また、カットサイズ をもつカットの個数を の重複度 と定義する。以下の問に導出も含めて答えよ。
(1) 以下のグラフ について、全ての可能なカットサイズ とその重複度 を求めよ。
(2) が完全グラフ、すなわち のとき、可能なカットサイ
ズ とその重複度 を全て求めよ。
(3) が環状グラフ、すなわち のとき、カットサイズの最小値 とその重複度 を求めよ。
(4) の最小カットサイズ をもつカットの一つを とする。このとき の中で、 と をまたぐ辺の割合は 以下であることを示せ。必要であれば、性質 を用いてもよい。ただし、 は の要素数、 は点 に接続する辺の数を表す。
Kai
(1)
の場合（4通り）
- : カットされる辺は 。
- : カットされる辺は 。
- : カットされる辺は 。
- : カットされる辺は 。
の場合（3通り）
- : カットされる辺は 。
- : カットされる辺は 。
- : カットされる辺は 。
以上の結果から、可能なカットサイズ とその重複度 は以下のようになります。
(2)
が完全グラフの場合、任意の2頂点間に辺が存在します。
カット において、 の要素数を （ただし ）、 の要素数を とします。
に属する 個の頂点のそれぞれは、 に属する 個の頂点すべてと辺で結ばれているため、カットサイズ は にのみ依存し、次のように表されます。
ここで、 と の区別はないため、 の範囲を に限定してすべてのカットを網羅できます。
重複度 は、 個の頂点から要素数 の集合 を選ぶ組み合わせの数に基づきます。
の場合:
を選ぶごとに一意のカットが定まるため、組み合わせの数がそのまま重複度になります。
の場合（ が偶数のときのみ存在）:
を選ぶ操作において、ある集合を選んだ場合と、その補集合を選んだ場合とで同じカットを2回数え上げてしまうため、 倍する必要があります。
(3)
頂点集合を と に分割したとき、グラフの輪をたどると、 の頂点から の頂点へ移動する回数と、 の頂点から の頂点へ戻る回数は必ず等しくなります。したがって、環状グラフにおける任意のカットサイズは必ず 偶数 になります。
であり、グラフは連結しているためカットサイズが になることはありません。よって、正の偶数の最小値である が最小カットサイズとなります。
カットサイズが になるということは、環状グラフを構成する 本の辺の中から、切断する2本の辺を選ぶことと同義です。どの2本を選んでもグラフは2つの部分集合に分割されるため、重複度は 本の辺から2本を選ぶ組み合わせの数になります。
(4)
グラフ の各頂点 に対して、その頂点 1 つだけを片側に取るカット
を考える。このカットのカットサイズは、頂点 に接続している辺の本数に等しいので、
である。最小カットサイズ は、すべてのカットサイズの中での最小値であるから、任意の頂点 に対して
が成り立つ。この不等式をすべての頂点 について足し合わせると、
となる。左辺は を 回足したものなので、
である。また、握手補題より
であるから、
を得る。両辺を で割ると、
となる。ここで、最小カット のカットサイズは であるため、 と をまたぐ辺の割合は
である。したがって、この割合は 以下であることが示された。