グラフ理論#0「グラフとは？」

有限集合$V$と$V$の二点集合の集合$E \subset 2^V$の組$(V,E)$をグラフという。

グラフ$G=(V,E)$に対し、$V$を$V(G)$, $E$を$E(G)$と書くことにする。

$V(G)$の元を頂点、$E(G)$の元を辺と呼ぶ。

$G=(\varnothing,\varnothing)$を空グラフと呼ぶ。

$G$:グラフ

頂点$v$と辺$e$が接続している$:⇔ v \in e$

頂点$v_0, v_1$が隣接している$:⇔ \{v_0,v_1\} \in E(G)$

辺$e_0, e_1$が隣接している$:⇔ e_0\cap e_1 \not = \varnothing$

$G$:グラフ

$H=(V,E)$が$G$の部分グラフであるとは以下を満たすこと:

• $V \subset V(G)$
• $E \subset E(G)$
• $\forall e \in E, e \subset V$

$H$が$G$の部分グラフであることを$H \leq G$と書く。

$v \in V(G)$

$E_G(v):=\{e \in E(G)\ |\ v \in e\}$

$v$に接続している辺全体を取る写像。

グラフ$G,G'$について$\phi:V(G)→V(G')$がグラフ準同型写像$:⇔ \forall \{v_0,v_1\} \in E(G), \phi(\{v_0,v_1\}) \in E(G')$

互いに逆な準同型写像があるとき、$G,G'$は同型という。

$G$:グラフ

$ \mathcal{V} (G):=2^{V(G)}$
$\mathcal{V}(G)$は$𝔽_2$多元環になる。

$\mathcal{V}(G)$を$G$の頂点空間と呼ぶ。
$\mathcal{V}(G)$の元を頂点集合と呼ぶ。

$G$:グラフ

$\mathcal{E}(G):=2^{E(G)}$
$\mathcal{E}(G)$は$𝔽_2$多元環になる。

$\mathcal{E}(G)$を$G$の辺空間と呼ぶ。
$\mathcal{E}(G)$の元を辺集合と呼ぶ。