隣接行列
隣接行列は、グラフを操作するためのコンピュータプログラムにおけるグラフの表現のためのデータ構造として使うことができる。この応用のためにも使われる主な代替データ構造は隣接リストである。
隣接行列中の各成分は1ビットしか必要としないため、隣接行列は非常にコンパクトなやり方で表すことができ、有向グラフを表わすためにはわずか|V |/8バイト、無向グラフを表わすためには(パック三角形式を用い、行列の下部三角部分のみを格納することによって)わずか約 |V |/16しか占めない。わずかにより簡潔な表現も可能であるものの、この方法は全てのn頂点グラフを表すために必要な最小ビット数の情報理論的下界に近付く。テキストファイルにグラフを格納するためには、全てのバイトがテキスト文字であることを(例えばBase64表現を使うことによって)保証するためにバイト毎により少ないビットした使うことができない。無駄な空間を避けることに加えて、このコンパクトさは参照の局所性を促す。
隣接行列A1およびA2を持つ2つの有向または無向グラフG1およびG2が与えられると仮定する。G1およびG2は、
P A 1 P − 1 = A 2 {\displaystyle PA_{1}P^{-1}=A_{2}}
というような置換行列Pが存在する時かつその時に限り同型である。
具体的には、A1およびA2は相似であり、したがって同一の最小多項式、固有多項式、固有値、行列式、跡を有する。したがってこれらは、グラフの同型不変量として機能する。しかしながら、2つのグラフは同じ固有値の組を持つかもしれないが、同型ではない。こういった線型作用素は等スペクトル(英語版)的と言われる。