Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

第8回 独立性と構造を利用する計算

グラフ理論・動的計画法・整列アルゴリズム

← 备考目录

試験時間(目安)満点問題数
180分100点全3問
問題分野テーマ配点
問題1グラフ理論辺集合の線形独立性と全域森35点
問題2動的計画法ちょうど K 頂点を選ぶ木上の独立集合35点
問題3整列アルゴリズム転倒数が教える整列の難しさ30点

問題1 · グラフ理論(35点)

辺集合の線形独立性と全域森

単純無向グラフ G=(V,E)G=(V,E) は非連結でもよい。n=∣V∣n=\vert V\vert、m=∣E∣m=\vert E\vert、連結成分数を cc とする。辺部分集合を長さ mm の0-1ベクトルで表し、加算は各座標の排他的論理和とする。各頂点の次数が偶数になる辺集合全体をサイクル空間 ZZ と呼ぶ。空集合も含める。GG の各連結成分の全域木を合わせた全域森 FF を固定する。以下では体 F2F_{2} 上の線形独立性を用いる。

(1) 全域森の辺数(5点)

全域森の辺数が n−cn-c になることを、木の辺数の性質から示せ。辺を一つずつ追加して閉路を作らない限り採用する方法で、処理終了時に全域森を得られることを証明せよ。

(2) 基本閉路と空間の次元(6点)

FF に含まれない辺 ee を加えてできる唯一の閉路を CeC_{e} とする。すべての CeC_{e} が線形独立であることを示せ。また、任意の z∈Zz\in Z から非森辺を消去すると空集合になることを示し、ZZ の次元を求めよ。

(3) 基本閉路の具体例(7点)

V={1,…,6}V=\{1,\ldots ,6\}、E={12,23,13,34,45,56,46,25}E=\{12,23,13,34,45,56,46,25\}、F={12,23,34,45,56}F=\{12,23,34,45,56\} とする。ij は無向辺 {i,j}\{i,j\} を表す。基本閉路をすべて求め、S={12,13,34,45,25}S=\{12,13,34,45,25\} を基本閉路の和で表せ。SS が ZZ に属することも直接確認せよ。

(4) 接続行列の階数(6点)

頂点-辺接続行列 BB を、辺の両端の行だけが1の n×mn\times m 行列とする。BB の階数が n−cn-c であることを示せ。各成分の行の和が0であることによる上界と、森の列の独立性による下界を別々に示すこと。

(5) 辺追加による変化(5点)

新しい辺を1本追加したとき、その両端が同じ連結成分にある場合と異なる場合について、接続行列の階数およびサイクル空間の次元がどう変わるかを求めよ。各変化を組合せ的にも説明せよ。

(6) 交換性と最大重みの全域森(6点)

森の辺集合 I,JI,J が ∣I∣<∣J∣\vert I\vert <\vert J\vert を満たすとき、II に追加しても閉路を作らない辺が J∖IJ\setminus I に存在することを証明せよ。さらに重みの降順で閉路を作らない辺を採用する方法が最大重みの全域森を得ることを交換法で示せ。負の重みも許す。

問題2 · 動的計画法(35点)

ちょうど K 頂点を選ぶ木上の独立集合

nn 頂点の木 TT の各頂点 vv に整数重み w(v)w(v) がある。重みは負でもよい。隣接する二頂点を同時に選ばず、ちょうど KK 頂点を選ぶときの重み和を最大化する。1≤K≤n1\le K\le n とする。木を任意の根で根付き木にし、各頂点の子は固定した順序で処理する。同じ最大重みを達成する異なる頂点集合の数も求めたい。実現不可能な状態の最適値は −∞-\infty とする。

(1) 状態と初期値(5点)

根 vv の部分木について、vv を選ぶかどうかと、選ぶ総数を区別する状態を定義せよ。子をまだ処理していない段階の初期値を示し、負の重みのときに「高々 KK 個」の問題へ変えてしまわないための注意を述べよ。

(2) 子の取り込みと集合数(7点)

子 uu のDPを親 vv の途中結果へ取り込む式を導け。vv と uu の選択状態の制約、個数の分配、実現不能な組合せを明記せよ。最適な集合数を同時に更新する式も示せ。

(3) 具体例と最適集合(7点)

根1、辺 {1,2},{1,3},{2,4},{2,5},{3,6}\{1,2\},\{1,3\},\{2,4\},\{2,5\},\{3,6\}、重み (4,6,5,4,4,7)(4,6,5,4,4,7) とする。根1について、選択状態ごとに k=0,…,4k=0,\ldots ,4 の最適値を求めよ。K=3K=3 の最適値、最適集合数、すべての最適集合を示せ。

(4) 正しさと一意分解(5点)

部分木に関する帰納法で正しさを示せ。固定した子の処理順において、同じ頂点集合を異なる個数分配から重複して数えない理由も説明せよ。

(5) 計算量と復元(5点)

全体の時間・空間計算量を示せ。最適集合を復元するために、各子を取り込んだ段階の分割情報を保存する方法を説明し、復元時に必要な処理量を求めよ。

(6) 一本の追加辺(6点)

TT に既存でない辺 {a,b}\{a,b\} を1本だけ追加したグラフを考える。追加辺を除いた木に対するDPを定数回実行して、ちょうど KK 頂点の最適値と集合数を求める方法を示せ。場合分けした解集合が重複しないことも確認せよ。

問題3 · 整列アルゴリズム(30点)

転倒数が教える整列の難しさ

NN 個のレコードには比較可能なキーと元位置がある。安定整列後の各レコードの位置を安定順位と呼び、同じキーでは元位置の順に順位を付ける。転倒数 II は i<ji<j かつ key⁡(A[i])>key⁡(A[j])\operatorname{key}(A[i])>\operatorname{key}(A[j]) を満たす組の数である。同じキーは転倒に含めない。添字と順位は1始まりとする。要素間の交換を隣接交換に限る場合と、安定順位の変位が制限される場合を考える。

(1) 転倒数と安定順位(4点)

入力 [3a,1a,2a,1b,3b,2b][3_{a},1_{a},2_{a},1_{b},3_{b},2_{b}] の転倒数、安定整列結果、各元位置の安定順位を求めよ。安定順位と元位置の差の絶対値の最大値 dd も求めよ。

(2) 併合による転倒数の計数(6点)

安定なマージソートに転倒数の計数を加えよ。右側の要素を左側より先に出力する際に何個加算するか、同じキーをどう扱うかを明記し、時間・補助空間計算量を示せ。

(3) 最小隣接交換数(5点)

安定整列に必要な隣接交換の最小回数が II と等しいことを証明せよ。キーが等しいレコードを交換しないことも含めて示し、交換予算 BB のもとで可能かどうかの判定法を求めよ。

(4) 挿入整列の処理量(5点)

挿入整列の処理量を O(N+I)O(N+I) として評価せよ。各移動と転倒との対応を説明し、整列済みの入力と逆順の相異なるキーの入力における処理量を比較せよ。

(5) 変位保証と最小ヒープ(6点)

すべてのレコードについて、安定順位と元位置の差が高々 dd であると保証される。先頭 d+1d+1 個の候補を最小ヒープに入れ、出力のたびに次の1個を補う整列法を示せ。安定性と正しさを証明し、時間・空間計算量を求めよ。

(6) 比較回数の下界(4点)

d≥1d\ge 1、NN が d+1d+1 の倍数で、キーは相異なるとする。長さ d+1d+1 の整列済みブロックの内部を任意に置換した入力族を用い、変位保証があっても比較整列には Ω(Nlog⁡(d+1))\Omega (N \log(d+1)) 回の比較が必要となることを示せ。