行列のグラフと消去グラフ

対称行列 $A\in M_n(\mathbb{R})$ のグラフ $G(A)$ を、頂点集合 $\{1,\ldots,n\}$、辺集合 $\{\{i,j\}:i\ne j,\ a_{ij}\ne0\}$ の無向グラフとする。消去グラフの辺集合 $E_k$（頂点集合 $\{k,\ldots,n\}$ の上）を、$E_1=G(A)$ の辺集合とし、

で定める。すなわち頂点 $k$ を消し、その隣接点どうしをすべて辺で結ぶ。$E_k$ に属するが $G(A)$ の辺でないものを fill-in（の位置）という。