第8回 独立性と構造を利用する計算
グラフ理論・動的計画法・整列アルゴリズム
| 試験時間(目安) | 満点 | 問題数 |
|---|---|---|
| 180分 | 100点 | 全3問 |
問題1 · グラフ理論(35点)¶
辺集合の線形独立性と全域森¶
単純無向グラフ は非連結でもよい。、、連結成分数を とする。辺部分集合を長さ の0-1ベクトルで表し、加算は各座標の排他的論理和とする。各頂点の次数が偶数になる辺集合全体をサイクル空間 と呼ぶ。空集合も含める。 の各連結成分の全域木を合わせた全域森 を固定する。以下では体 上の線形独立性を用いる。
(1) 全域森の辺数(5点)¶
全域森の辺数が になることを、木の辺数の性質から示せ。辺を一つずつ追加して閉路を作らない限り採用する方法で、処理終了時に全域森を得られることを証明せよ。
(2) 基本閉路と空間の次元(6点)¶
に含まれない辺 を加えてできる唯一の閉路を とする。すべての が線形独立であることを示せ。また、任意の から非森辺を消去すると空集合になることを示し、 の次元を求めよ。
(3) 基本閉路の具体例(7点)¶
、、 とする。ij は無向辺 を表す。基本閉路をすべて求め、 を基本閉路の和で表せ。 が に属することも直接確認せよ。
(4) 接続行列の階数(6点)¶
頂点-辺接続行列 を、辺の両端の行だけが1の 行列とする。 の階数が であることを示せ。各成分の行の和が0であることによる上界と、森の列の独立性による下界を別々に示すこと。
(5) 辺追加による変化(5点)¶
新しい辺を1本追加したとき、その両端が同じ連結成分にある場合と異なる場合について、接続行列の階数およびサイクル空間の次元がどう変わるかを求めよ。各変化を組合せ的にも説明せよ。
(6) 交換性と最大重みの全域森(6点)¶
森の辺集合 が を満たすとき、 に追加しても閉路を作らない辺が に存在することを証明せよ。さらに重みの降順で閉路を作らない辺を採用する方法が最大重みの全域森を得ることを交換法で示せ。負の重みも許す。
参考解答・採点の観点 — 問題1
(1) 全域森の辺数
頂点の木は 本の辺を持つので、成分について合計すると 。辺を一度ずつ調べ、異なる採用成分を結ぶ辺だけを採用する。採用辺は常に森である。終了後、 ではつながる二頂点が採用森で分離していると、両者を結ぶ の経路のどこかに採用成分をまたぐ辺がある。その辺は処理時にも閉路を作らず採用されるはずなので矛盾。
(2) 基本閉路と空間の次元
各 には非森辺 が1本だけ含まれる。他の には が含まれないため、非空の基本閉路の和は0にならず、独立である。 に含まれる各非森辺 について を加えて消去すると、残る集合は森内で全頂点が偶次数。森内の非空辺集合には次数1の頂点があるので、残りは空である。基本閉路は を張り、次元は非森辺数 。
(3) 基本閉路の具体例
、、。 であり、23が打ち消される。 は閉路 の辺集合で、頂点の次数は2、6の次数は0。したがって 。次元は。
(4) 接続行列の階数
各成分内の全行を加えると、各辺が2回現れるため0。成分ごとに独立な行関係が1本あり、階数。一方、森の列に線形関係があると、その係数1の辺集合は全頂点偶次数になる。非空の森には次数1の頂点があるので不可能。森の 列は独立であり、階数。よって等号。 は全頂点偶次数と同じ条件なので でもある。
(5) 辺追加による変化
同じ成分内なら は変わらず が1増える。階数 は不変、サイクル次元 は1増える。既存の端点間経路と新辺が新しい閉路方向を与える。異なる成分間なら が1減り、階数は1増えるがサイクル次元は不変。新辺は両成分を結ぶ橋となり、閉路を作らない。
(6) 交換性と最大重みの全域森
の連結成分内だけに の全辺があると仮定する。各 成分 内の の森辺数は高々 。合計して となり矛盾。よって成分をまたぐ の辺がある。
貪欲法の選択済み辺を含む最適全域森を維持する。次の採用辺 が最適森にないなら、最適森へ を加えた閉路から選択済みでない辺 を除く。 は より先に採用されなかった辺で、。実際、より重い を先に拒否したなら当時の選択済み辺だけで の両端がつながり、それらを含む最適森に も入ることはできない。置換は重みを減らさず、選択済み辺を増やす。負の辺でも全域森には 本を必ず採用するため同じ証明が成立する。
問題2 · 動的計画法(35点)¶
ちょうど K 頂点を選ぶ木上の独立集合¶
頂点の木 の各頂点 に整数重み がある。重みは負でもよい。隣接する二頂点を同時に選ばず、ちょうど 頂点を選ぶときの重み和を最大化する。 とする。木を任意の根で根付き木にし、各頂点の子は固定した順序で処理する。同じ最大重みを達成する異なる頂点集合の数も求めたい。実現不可能な状態の最適値は とする。
(1) 状態と初期値(5点)¶
根 の部分木について、 を選ぶかどうかと、選ぶ総数を区別する状態を定義せよ。子をまだ処理していない段階の初期値を示し、負の重みのときに「高々 個」の問題へ変えてしまわないための注意を述べよ。
(2) 子の取り込みと集合数(7点)¶
子 のDPを親 の途中結果へ取り込む式を導け。 と の選択状態の制約、個数の分配、実現不能な組合せを明記せよ。最適な集合数を同時に更新する式も示せ。
(3) 具体例と最適集合(7点)¶
根1、辺 、重み とする。根1について、選択状態ごとに の最適値を求めよ。 の最適値、最適集合数、すべての最適集合を示せ。
(4) 正しさと一意分解(5点)¶
部分木に関する帰納法で正しさを示せ。固定した子の処理順において、同じ頂点集合を異なる個数分配から重複して数えない理由も説明せよ。
(5) 計算量と復元(5点)¶
全体の時間・空間計算量を示せ。最適集合を復元するために、各子を取り込んだ段階の分割情報を保存する方法を説明し、復元時に必要な処理量を求めよ。
(6) 一本の追加辺(6点)¶
に既存でない辺 を1本だけ追加したグラフを考える。追加辺を除いた木に対するDPを定数回実行して、ちょうど 頂点の最適値と集合数を求める方法を示せ。場合分けした解集合が重複しないことも確認せよ。
参考解答・採点の観点 — 問題2
(1) 状態と初期値
を の部分木で 頂点を選び、 の選択状態が の最適値とする。 だけの初期状態は 、、その他は。実現可能な状態の集合数は1、その他は0。最終結果は 根根)。負重みでも個数 の状態だけを答え、0との最大を取ってはならない。
(2) 子の取り込みと集合数
子 を追加する前の表を 、新しい表を とする。。最大化は 、、 の実現可能な組だけで行う。各候補の集合数は 。より良い値なら数を置換し、同点なら加算する。子を1個ずつ処理することで、他の子との独立性を使ったナップサック型併合になる。
(3) 具体例と最適集合
| 根1の状態 | |||||
|---|---|---|---|---|---|
| 非選択 | 0 | 7 | 13 | 15 | |
| 選択 | 4 | 11 | 15 | 19 |
の最適値は15。最適集合は 、、 の3個。根選択の状態に2個、非選択の状態に1個がある。
(4) 正しさと一意分解
の選択を固定すると、異なる子の部分木間に辺はなく、各子 との制約は だけ。任意の解は各子の選択集合へ一意に分解される。重みは加算できるため、各分配で最適な部分解を選べば十分。処理済み部分と新しい子の頂点集合は互いに素なので組合せ数は積。固定された処理順では、各集合がその子から選ぶ数 と子根の状態 を一意に定めるため、分配間の重複はない。
(5) 計算量と復元
各親子の併合に 、全体 算術演算。各頂点の完成表に 空間。復元のため、各子を取り込んだ段階・親状態・個数について、最適な を一組記録する。取り込み段階は全体で 個なので保存量も 。根から子を取り込んだ逆順に分離し、その子の表へ進む。各取り込み段階を一度だけ訪れるため復元は 、出力は 。正確な集合数の大整数演算には別途ビット費用がかかる。
(6) 一本の追加辺
追加辺の端点状態 (非選択,非選択)、(非選択,選択)、(選択,非選択) の3通りをそれぞれ固定する。固定頂点では、指定と異なる の初期状態をにすれば同じ木DPを使える。各場合の最適値の最大を答え、最大値を達成する場合の個数を加える。端点状態は集合ごとに一意なので場合間の重複はない。追加辺の唯一の制約を漏れなく表す。時間 、空間 のオーダーは変わらない。
問題3 · 整列アルゴリズム(30点)¶
転倒数が教える整列の難しさ¶
個のレコードには比較可能なキーと元位置がある。安定整列後の各レコードの位置を安定順位と呼び、同じキーでは元位置の順に順位を付ける。転倒数 は かつ を満たす組の数である。同じキーは転倒に含めない。添字と順位は1始まりとする。要素間の交換を隣接交換に限る場合と、安定順位の変位が制限される場合を考える。
(1) 転倒数と安定順位(4点)¶
入力 の転倒数、安定整列結果、各元位置の安定順位を求めよ。安定順位と元位置の差の絶対値の最大値 も求めよ。
(2) 併合による転倒数の計数(6点)¶
安定なマージソートに転倒数の計数を加えよ。右側の要素を左側より先に出力する際に何個加算するか、同じキーをどう扱うかを明記し、時間・補助空間計算量を示せ。
(3) 最小隣接交換数(5点)¶
安定整列に必要な隣接交換の最小回数が と等しいことを証明せよ。キーが等しいレコードを交換しないことも含めて示し、交換予算 のもとで可能かどうかの判定法を求めよ。
(4) 挿入整列の処理量(5点)¶
挿入整列の処理量を として評価せよ。各移動と転倒との対応を説明し、整列済みの入力と逆順の相異なるキーの入力における処理量を比較せよ。
(5) 変位保証と最小ヒープ(6点)¶
すべてのレコードについて、安定順位と元位置の差が高々 であると保証される。先頭 個の候補を最小ヒープに入れ、出力のたびに次の1個を補う整列法を示せ。安定性と正しさを証明し、時間・空間計算量を求めよ。
(6) 比較回数の下界(4点)¶
、 が の倍数で、キーは相異なるとする。長さ の整列済みブロックの内部を任意に置換した入力族を用い、変位保証があっても比較整列には 回の比較が必要となることを示せ。
参考解答・採点の観点 — 問題3
(1) 転倒数と安定順位
の後のの4組、との1組、との1組で 。安定整列は 。元位置順の安定順位は 、変位は なので 。
(2) 併合による転倒数の計数
左右を再帰整列して転倒数を合計する。併合中、右の先頭キーが左の先頭より厳密に小さければ、残る左の全要素と転倒を作るため、未出力の左要素数を加える。等しいなら左を先に出し、加算しない。左右内部は再帰、左右をまたぐ転倒は併合で一度だけ数える。時間 、補助空間 。
(3) 最小隣接交換数
レコードを (キー,元位置) で比較すると、その転倒数は厳密なキー転倒 と等しい。隣接交換はこの全順序の転倒数を高々1しか減らせないため少なくとも 回必要。隣接する逆転対だけを交換すれば各回1減り、 回で安定整列に到達する。同キー対は逆転でないため交換しない。予算内で可能である条件は 。
(4) 挿入整列の処理量
挿入時、直前のキーが厳密に大きい間だけ右へ移動する。各移動は、挿入要素と先行する大きい要素の転倒を一つ解消する。全移動回数は 。各外側反復の固定処理と停止比較を加えて 。整列済みでは 、相異なるキーの逆順では なので 。同キーを移動しないため安定である。
(5) 変位保証と最小ヒープ
比較キーを (元キー,元位置) とする。最初の 個をヒープへ入れ、最小を出力するたびに次の未読要素を入れる。順位 の要素の元位置は高々 なので、 番目を選ぶ時点では必ず読み込まれている。以前の最小はすでに出力されているため、ヒープの最小が順位 。元位置で同キーの順も守る。時間 、ヒープ空間 。 では入力順に出力すれば 。
(6) 比較回数の下界
とする。各長さ のブロックのキー範囲を他のブロックと分離し、内部だけを置換する。変位は 以下で、入力数は 。比較決定木の最悪高さは少なくとも 。 では 。例えば後半の少なくとも 個の因子を用い、小さい の場合は定数を調整すればよい。よって 。ヒープ法のオーダーは最適である。