隣接行列
単純グラフの (a, b, c)-「隣接行列」は、(i, j) が辺ならばAi,j = a、辺でなければb、対角上にcを持つ。 セイデル隣接行列(英語版)は(−1, 1, 0)-「隣接行列」である。この行列は強正則グラフとツーグラフ(英語版)の研究で使われる。
距離行列は、位置 (i, j) に頂点viと vjとの間の距離を有する。この距離は頂点を連結する最短の道の長さである。辺の長さが明示的に与えられていない限り、道の長さは道中の辺の数である。距離行列は隣接行列の高冪と似ているが、2つの頂点が連結しているかどうか(すなわち、真偽値を含む連結行列)だけを教える代わりに、頂点間の正確な距離を与える。
頂点の組Vを持つ単純グラフについて、隣接行列はその要素A'ijが頂点iから頂点jへの辺が存在する時は1、辺が存在しない時は0であるような |V| × |V|正方行列Aである。この行列の対角要素は全て0である(単純グラフでは頂点からそれ自身への辺〈ループ(英語版)〉は許されないため)。また、代数的グラフ理論において代数変数を持つ非ゼロ要素を置換するために有用なこともある。
同じ概念は2つの頂点間の辺の数を対応する行列要素に格納することや非ゼロの対角要素を許容することによって多重グラフ(英語版)やループを持つグラフへと拡張することができる。ループは、一貫した慣習に従っている限り、1回(単一の辺)数えても2回(2つの頂点-辺接続として)数えてもよい。無向グラフはループを2回数える後者の慣習を使用することが多いが、有向グラフは通常前者の慣習を使用する