📂グラフ理論

グラフの行列表現

定義 ¹

グラフ $G(V,E)$ が与えられたとしよう。

次数行列

各頂点 $v_{i}\in V$ の次数 $d(v_{i})$を簡単に $d_{i}$と表記しよう。次のような行列を $G$ の次数行列^{degree matrix}と呼び、$D(G)$ または単に $D$と表記する。

$$ D(G) = \mathrm{diag} (d_{1}, \dots, d_{n}) = \begin{bmatrix} d_{1} & 0 & \cdots & 0 \\ 0 & d_{2} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & d_{n} \end{bmatrix} $$

ここで、$\mathrm{diag}$ は対角行列である。

隣接行列

次のような正方行列を $G$ の隣接行列^{adjacent matrix}と呼び、$A(G)$ または単に $A$と表記する。

$$ A = [a_{ij}] = \begin{cases} 1 &, ij \in E(G) \\ 0 &,ij \notin E(G) \end{cases} $$

隣接行列は離散的にも豊富な性質を有し、行列の形を保持しているため、線形代数の様々な理論を適用することができる。特にその固有値は、ネットワークを応用する様々なモデルで頻繁に言及される。

接続行列

次のような行列を $G$ の接続行列^{incident matrix}と呼び、$M(G)$ または単に $M$と表記する。

$$ M = [m_{ij}] = \begin{cases} 1 &, \text{vertex } i \text{ is incident with edge } j \\ 0 &, \text{otherwise} \end{cases} $$

有向接続行列

$G$が有向グラフであるとしよう。次のような行列を $G$ の有向接続行列^{directed incident matrix}と呼び、$N(G)$ または単に $N$と表記する。

$$ N = [n_{ij}] = \begin{cases} 1 &, \text{vertex } i \text{ is tail of edge } j \\ -1 &, \text{vertex } i \text{ is head of edge } j \\ 0 &, \text{otherwise} \end{cases} $$

例

上記のようなグラフに対して、次のような行列が得られる。

$$ D = \begin{matrix} & v_{1} & v_{2} & v_{3} & v_{4} & v_{5} & v_{6} & v_{7} & v_{8} \\ v_{1} & 3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ v_{2} & 0 & 2 & 0 & 0 & 0 & 0 & 0 & 0 \\ v_{3} & 0 & 0 & 2 & 0 & 0 & 0 & 0 & 0 \\ v_{4} & 0 & 0 & 0 & 6 & 0 & 0 & 0 & 0 \\ v_{5} & 0 & 0 & 0 & 0 & 2 & 0 & 0 & 0 \\ v_{6} & 0 & 0 & 0 & 0 & 0 & 2 & 0 & 0 \\ v_{7} & 0 & 0 & 0 & 0 & 0 & 0 & 3 & 0 \\ v_{8} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} $$

$$ A = \begin{matrix} & v_{1} & v_{2} & v_{3} & v_{4} & v_{5} & v_{6} & v_{7} & v_{8} \\ v_{1} & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ v_{2} & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ v_{3} & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ v_{4} & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 0 \\ v_{5} & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ v_{6} & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ v_{7} & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\ v_{8} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} $$

$$ M = \begin{matrix} & e_{1} & e_{2} & e_{3} & e_{4} & e_{5} & e_{6} & e_{7} & e_{8} & e_{9} & e_{10} \\ v_{1} & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ v_{2} & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ v_{3} & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ v_{4} & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ v_{5} & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ v_{6} & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ v_{7} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ v_{8} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} $$

上記のような有向グラフに対する有向接続行列は、次のようになる。

$$ N = \begin{matrix} & e_{1} & e_{2} & e_{3} & e_{4} & e_{5} & e_{6} & e_{7} & e_{8} & e_{9} & e_{10} \\ v_{1} & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ v_{2} & -1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ v_{3} & 0 & -1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ v_{4} & 0 & 0 & -1 & -1 & -1 & 1 & 1 & 1 & 0 & 0 \\ v_{5} & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 1 & 0 \\ v_{6} & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 1 \\ v_{7} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & -1 & -1 \\ v_{8} & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{matrix} $$