最後に、グラフと線型代数の関係について簡単な話題を紹介します。
プログラミングコンテストにおいて、入力としてグラフが与えられることがとても一般的です。受け取ったプログラムの中でこれを保持する形式としては、次の2つがよく知られています。
コンテストにおいては、隣接頂点が取り出しやすく（したがって全探索がシンプルに書ける）、疎なグラフに対して空間計算量が有利な隣接リストを用いることが多いですが、今回は線型代数の話題なので隣接行列を扱います *1。
隣接行列は、グラフ G = (V, E) に対して定まる次のような行列です。
この行列に対して線形代数的な操作を施すことで、グラフに関する様々な情報を調べることができます。詳しくは、2年前の競技プログラミングアドベントカレンダーで fura2 さんの書かれた次の記事が参考になるでしょう。
今年の夏合宿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 での状態ベクトルをとすると、次の式が成立します。
これを用いて連立一次方程式を立てて解きます。これは解の個数も含めてすでに解説済みですね。
出題者による解説もあります。
*1： とは言いましたがほとんど例題だけです。すみません。