隣接行列
2つの部分がr個とs個の頂点を持つ2部グラフの隣接グラフAは以下の形式で書くことができる。
A = ( 0 r , r B B T 0 s , s ) , {\displaystyle A={\begin{pmatrix}0_{r,r}&B\\B^{T}&0_{s,s}\end{pmatrix}},}
上式において、Bはr × s 行列、0r,rおよび0s,sはr × rおよびs × sゼロ行列を表す。この場合、より小さな行列Bがグラフを一意に表し、Aの残りの部分は冗長として捨てることができる。Bはbiadjacency行列と呼ばれることがある。
形式的に、G = (U, V, E)を部分U = {u1, ..., ur}およびV = {v1, ..., vs}を持つ2部グラフとする。Biadjacency行列は、 (ui, vj) ∈ Eの時かつその時に限りbi,j = 1のr × s 0–1行列Bである。
Gが2部多重グラフまたは重み付きグラフならば、要素 bi,jは頂点間の辺の数、または辺(ui, vj)の重みをそれぞれ取る。
Aが無向または有向グラフGの隣接行列とすると、行列A(すなわちAのn個の複製の積)は興味深い解釈を持つ: 要素(i, j)は頂点iから頂点jへの長さnの(有向または無向)歩道の数を与える。nが、あるi、jについてAの要素(i, j)が正となるような最小の非負整数とすると、nは頂点iと頂点jとの間の距離である。これは、例えば、無向グラフG中の三角形の数が厳密にAの跡を6で割った数となることを暗に示す。ここで留意すべきは、隣接行列はグラフが連結しているかどうかを決定するために使うことができることである。