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

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

$G$:グラフ

頂点$v \in V(G)$と辺$e \in E(G)$が接続している$:⇔ v \in e$

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

辺$e_0, e_1 \in E(G)$が隣接している$:⇔ 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\}$

$G$:グラフ
$V \subset V(G)$
$E \subset E(G)$
$H \leq G$
とする。

$$G \setminus E := (V(G),E(G) \setminus E)$$

$$G - V := (V(G) \setminus V, E(G) \setminus \bigcup_{v \in V}{E_G(v)})$$

$$H+E := (V(H) \cup \bigcup_{e \in E}{e}, E(H) \cup E)$$

$$G|_E:=(\bigcup_{e \in E}e,E)$$

これらはグラフ。

$H_0,H_1$:グラフ

$H_0 \sqcup H_1:=(V(H_0) \sqcup V(H_1),E(H_0) \sqcup E(H_1))$

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

像の像を考えて$\phi(E(G)) \subset 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)$の元を辺集合と呼ぶ。