跳到主要内容

東京大学 新領域創成科学研究科 メディカル情報生命専攻 2026年1月実施 問題8

标签：

Author​

祭音Myyura

Description​

G=(V,E)G = (V, E) を点集合 VV、辺集合 EE の単純連結無向グラフとする。VV の要素数を nn とする。VV を 2 分割したもの C=(S,T)C=(S,T) を GG のカットと呼ぶ。

ここで SS と TT は S⊂VS \subset V, T⊂VT \subset V, S≠∅S \neq \empty, T≠∅T \neq \empty, S∩T=∅S \cap T = \emptyset,S∪T=VS \cup T=V を満たし、SS と TT を入れ替えたペア (S,T)(S, T)、(T,S)(T,S) は区別しないものとする。カット CC のカットサイズを SS と TT をまたぐ辺の個数として定義する。また、カットサイズ ss をもつカットの個数を ss の重複度 m(s)m(s) と定義する。以下の問に導出も含めて答えよ。

(1) 以下のグラフ G0G_0 について、全ての可能なカットサイズ ss とその重複度 m(s)m(s) を求めよ。

(2) GG が完全グラフ、すなわち V={1,…,n},E={(i,j)∣i,j=1,…,n,i<j}V=\{1, \ldots, n\}, E =\{(i,j) \mid i,j = 1,\ldots,n,i <j \} のとき、可能なカットサイ ズ ss とその重複度 m(s)m(s) を全て求めよ。

(3) GG が環状グラフ、すなわち V={1,…,n},E={(i,i+1)∣i=1,…,n−1}∪{(n,1)}V=\{1, \ldots ,n\}, E =\{(i,i+1) \mid i =1,\ldots,n−1\} \cup \{(n,1)\} のとき、カットサイズの最小値 smin⁡s_{\min} とその重複度 m(smin)m(s_\text{min}) を求めよ。

(4) GG の最小カットサイズ smin⁡s_{\min} をもつカットの一つを Cmin=(Smin⁡,Tmin⁡)C_\text{min} = (S_{\min}, T_{\min}) とする。このとき EE の中で、Smin⁡S_{\min} と Tmin⁡T_{\min} をまたぐ辺の割合は 2/n2/n 以下であることを示せ。必要であれば、性質 ∣E∣=∑v∈Vdeg(v)/2|E|= \sum_{v \in V} \text{deg}(v)/2 を用いてもよい。ただし、∣E∣|E| は EE の要素数、deg(v)\text{deg}(v) は点 vv に接続する辺の数を表す。

Kai​

(1)​

∣S∣=1,∣T∣=3|S|=1, |T|=3 の場合（4通り）

  • S={1},T={2,3,4}S=\{1\}, T=\{2,3,4\} : カットされる辺は (1,3),(1,4)(1,3), (1,4)。s=2s = 2
  • S={2},T={1,3,4}S=\{2\}, T=\{1,3,4\} : カットされる辺は (2,3),(2,4)(2,3), (2,4)。s=2s = 2
  • S={3},T={1,2,4}S=\{3\}, T=\{1,2,4\} : カットされる辺は (3,1),(3,2),(3,4)(3,1), (3,2), (3,4)。s=3s = 3
  • S={4},T={1,2,3}S=\{4\}, T=\{1,2,3\} : カットされる辺は (4,1),(4,2),(4,3)(4,1), (4,2), (4,3)。s=3s = 3

∣S∣=2,∣T∣=2|S|=2, |T|=2 の場合（3通り）

  • S={1,2},T={3,4}S=\{1,2\}, T=\{3,4\} : カットされる辺は (1,3),(1,4),(2,3),(2,4)(1,3), (1,4), (2,3), (2,4)。s=4s = 4
  • S={1,3},T={2,4}S=\{1,3\}, T=\{2,4\} : カットされる辺は (1,4),(3,2),(3,4)(1,4), (3,2), (3,4)。s=3s = 3
  • S={1,4},T={2,3}S=\{1,4\}, T=\{2,3\} : カットされる辺は (1,3),(4,2),(4,3)(1,3), (4,2), (4,3)。s=3s = 3

以上の結果から、可能なカットサイズ ss とその重複度 m(s)m(s) は以下のようになります。

  • s=2s = 2 のとき、m(2)=2m(2) = 2
  • s=3s = 3 のとき、m(3)=4m(3) = 4
  • s=4s = 4 のとき、m(4)=1m(4) = 1

(2)​

GG が完全グラフの場合、任意の2頂点間に辺が存在します。 カット C=(S,T)C = (S, T) において、SS の要素数を kk（ただし 1≤k≤n−11 \le k \le n-1）、TT の要素数を n−kn-k とします。

SS に属する kk 個の頂点のそれぞれは、TT に属する n−kn-k 個の頂点すべてと辺で結ばれているため、カットサイズ ss は kk にのみ依存し、次のように表されます。

s=k(n−k)s = k(n-k)

ここで、(S,T)(S, T) と (T,S)(T, S) の区別はないため、kk の範囲を 1≤k≤⌊n/2⌋1 \le k \le \lfloor n/2 \rfloor に限定してすべてのカットを網羅できます。

重複度 m(s)m(s) は、nn 個の頂点から要素数 kk の集合 SS を選ぶ組み合わせの数に基づきます。

k<n/2k < n/2 の場合:

SS を選ぶごとに一意のカットが定まるため、組み合わせの数がそのまま重複度になります。

m(k(n−k))=(nk)m(k(n-k)) = \binom{n}{k}

k=n/2k = n/2 の場合（nn が偶数のときのみ存在）:

SS を選ぶ操作において、ある集合を選んだ場合と、その補集合を選んだ場合とで同じカットを2回数え上げてしまうため、1/21/2 倍する必要があります。

m(k(n−k))=12(nn/2)m(k(n-k)) = \frac{1}{2} \binom{n}{n/2}

(3)​

頂点集合を SS と TT に分割したとき、グラフの輪をたどると、SS の頂点から TT の頂点へ移動する回数と、TT の頂点から SS の頂点へ戻る回数は必ず等しくなります。したがって、環状グラフにおける任意のカットサイズは必ず 偶数 になります。

S≠∅,T≠∅S \neq \emptyset, T \neq \emptyset であり、グラフは連結しているためカットサイズが 00 になることはありません。よって、正の偶数の最小値である smin⁡=2s_{\min} = 2 が最小カットサイズとなります。

カットサイズが 22 になるということは、環状グラフを構成する nn 本の辺の中から、切断する2本の辺を選ぶことと同義です。どの2本を選んでもグラフは2つの部分集合に分割されるため、重複度は nn 本の辺から2本を選ぶ組み合わせの数になります。

m(smin⁡)=(n2)=n(n−1)2m(s_{\min}) = \binom{n}{2} = \frac{n(n-1)}{2}

(4)​

グラフ GG の各頂点 v∈Vv\in V に対して、その頂点 1 つだけを片側に取るカット

Cv=(v,V∖v)C_v=({v},V\setminus{v})

を考える。このカットのカットサイズは、頂点 vv に接続している辺の本数に等しいので、

∣Cv∣=deg⁡(v)|C_v|=\deg(v)

である。最小カットサイズ smin⁡s_{\min} は、すべてのカットサイズの中での最小値であるから、任意の頂点 v∈Vv\in V に対して

smin⁡≤deg⁡(v)s_{\min}\le \deg(v)

が成り立つ。この不等式をすべての頂点 v∈Vv\in V について足し合わせると、

∑v∈Vsmin⁡≤∑v∈Vdeg⁡(v)\sum_{v\in V}s_{\min}\le \sum_{v\in V}\deg(v)

となる。左辺は smin⁡s_{\min} を nn 回足したものなので、

nsmin⁡≤∑v∈Vdeg⁡(v)n s_{\min}\le \sum_{v\in V}\deg(v)

である。また、握手補題より

∑v∈Vdeg⁡(v)=2∣E∣\sum_{v\in V}\deg(v)=2|E|

であるから、

nsmin⁡≤2∣E∣n s_{\min}\le 2|E|

を得る。両辺を n∣E∣n|E| で割ると、

smin⁡∣E∣≤2n\frac{s_{\min}}{|E|}\le \frac{2}{n}

となる。ここで、最小カット Cmin⁡=(Smin⁡,Tmin⁡)C_{\min}=(S_{\min},T_{\min}) のカットサイズは smin⁡s_{\min} であるため、Smin⁡S_{\min} と Tmin⁡T_{\min} をまたぐ辺の割合は

smin⁡∣E∣\frac{s_{\min}}{|E|}

である。したがって、この割合は 2/n2/n 以下であることが示された。

本页目录