logo

グラフの行列表現 📂グラフ理論

グラフの行列表現

定義 1

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

次数行列

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

D(G)=diag(d1,…,dn)=[d10⋯00d2⋯0⋮⋮⋱⋮00⋯dn] 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}

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

隣接行列

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

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

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

接続行列

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

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

有向接続行列

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

N=[nij]={1,vertex i is tail of edge j−1,vertex i is head of edge j0,otherwise 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}

例

2.png

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

D=v1v2v3v4v5v6v7v8v130000000v202000000v300200000v400060000v500002000v600000200v700000030v800000000 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=v1v2v3v4v5v6v7v8v101110000v210010000v310010000v411101110v500010010v600010010v700011100v800000000 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=e1e2e3e4e5e6e7e8e9e10v11110000000v21001000000v30100100000v40011111100v50000010010v60000001001v70000000111v80000000000 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}

3.png

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

N=e1e2e3e4e5e6e7e8e9e10v11110000000v2−1001000000v30−100100000v400−1−1−111100v500000−10010v6000000−1001v70000000−1−1−1v80000000000 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}

  1. Wilson. (1970). Introduction to Graph Theory: p14. ↩︎