隣接行列と隣接リスト

定義 2.3（「グラフアルゴリズム」§2）

$V=\{v_1,\ldots,v_n\}$ と番号付けされたグラフ $G=(V,E)$ に対し、 $n \times n$ 行列 $A$ を

A_{ij} = \begin{cases} 1 & (v_i \text{ と } v_j \text{ が辺で結ばれている、有向グラフなら } (v_i,v_j) \in E) \\ 0 & (\text{そうでない}) \end{cases}

で定め、 $G$ の隣接行列という。重み付きグラフでは $1$ の代わりに重み $w$ を置き、辺がないところには $\infty$ を置く。

各頂点 $u$ に対し、 $u$ に隣接する頂点（有向グラフでは $u$ を始点とする辺の終点）を並べたリスト $\mathrm{Adj}[u]$ の組を、 $G$ の隣接リストという。

閉包の状態

定義

定義は閉包の起点です（証明を要しません）。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。

証明で明示的に参照している定理は、まだありません。