Hatena::Grouptopcoder

pepsin-amylaseの日記

 | 

2013-12-03競技プログラミング アドベントカレンダー Div.2013 3日目

隣接行列と線型代数

20:43

最後に、グラフと線型代数の関係について簡単な話題を紹介します。

プログラミングコンテストにおいて、入力としてグラフが与えられることがとても一般的です。受け取ったプログラムの中でこれを保持する形式としては、次の2つがよく知られています。

コンテストにおいては、隣接頂点が取り出しやすく(したがって全探索がシンプルに書ける)、疎なグラフに対して空間計算量が有利な隣接リストを用いることが多いですが、今回は線型代数の話題なので隣接行列を扱います *1

隣接行列は、グラフ G = (V, E) に対して定まる次のような行列です。

  • 各頂点に自然数を割り当てる。|V| 次元の行列 A の i, j 成分が、グラフ G の頂点 i から j への辺が存在するとき 1、そうでないとき 0 になっているならば、A は G の隣接行列である。

この行列に対して線形代数的な操作を施すことで、グラフに関する様々な情報を調べることができます。詳しくは、2年前の競技プログラミングアドベントカレンダーで fura2 さんの書かれた次の記事が参考になるでしょう。

External Memory グラフと線形代数

例題 Graph Automata Player

今年の夏合宿4日目に出題された問題です。

問題はこちらです。F: Graph Automata Player - Japan Alumni Group Summer Camp 2013 Day 4 | AtCoder

問題概要

有向グラフ(頂点数 300 以下)が与えられる。任意の時刻において、各頂点は 0, 1 いずれかの状態を持つ。時刻 t でのグラフの状態が与えられた時、時刻 t+1 での 頂点 v の状態は次のように決まる。

v から出ている辺で時刻 t での行き先の頂点の状態が 1 であるような辺が奇数個ならば 1、そうでなければ 0。

ある時刻での状態が与えられるので、T(1億以下)だけ前の状態を求めよ。条件を満たす状態が複数ありうる場合や状態が矛盾している場合は適切なエラーを出力すること。

解法

グラフの接続行列を A、時刻 t での状態ベクトルをv_tとすると、次の式が成立します。

A \cdot v_t = v_{t+1} (mod 2)

これを用いて連立一次方程式を立てて解きます。これは解の個数も含めてすでに解説済みですね。

出題者による解説もあります。

有効なWikiNameではありません - ACM-ICPC Japanese Alumni Group

*1: とは言いましたがほとんど例題だけです。すみません。

 |