グラフと一筆書き(その 1)

離散数学

久しぶりの日記は、一筆書きを「数学」してみます。

ある種の同値関係

空集合ではない集合 V に対し、V\times V 上の同値関係を
(v_1,v_2)\sim(w_1,w_2)\stackrel{\mathrm{def}}{\Leftrightarrow}\{v_1,v_2\}=\{w_1,w_2\}
と定義します。これは同値関係になります。ところでこれは一体どういった同値関係なのでしょうか。
(v,v) の同値類は \{(v,v)\} です。実際 (v,v)\sim(w_1,w_2) とすると、\{v,v\}=\{v\} であることから \{w_1,w_2\}=\{v\} でなければいけないので w_1=w_2=v となるからです。
では (v_1,v_2)(v_1\neq v_2) の同値類はどうでしょうか。(v_1,v_2)\sim(w_1,w_2) とすると、w_1\in\{w_1,w_2\}=\{v_1,v_2\} なので、w_1=v_1 か w_1=v_2 です。このとき明らかに

  • w_1=v_1 ならば w_2=v_2
  • w_1=v_2 ならば w_2=v_1

でなければならないので、(v_1,v_2)(v_1\neq v_2) の同値類は \{(v_1,v_2),(v_2,v_1)\}
となります。
この同値関係によって V\times V を分類した商集合を \tilde{V} と書くことにします。また、(v_1,v_2) の同値類を [v_1,v_2] と書くことにします。すぐにわかることですが [v_1,v_2]=[v_2,v_1] です。

グラフの定義

数学的に、グラフ G とは G=(V,E,\varphi) のことです。ここで V は頂点の集合、E は辺の集合で、\varphi:E\to\tilde{V} です。e\in E に対して \varphi(e)=[v,w] のとき、e は v と w を結ぶと言います \varphi(e)=[v,v] のとき、e はループであると言います。また、[v,w]\in\tilde{V} に対して、\varphi(e)=[v,w] となる e\in E は一つとは限りません。これは、二つの頂点を結ぶ辺は複数あっても良い、ということに他なりません。実際に \varphi(e)=[v,w] となる e\in E が複数あるとき、これらの辺のことを多重辺と言います。
ループ、及び多重辺を含まないグラフのことを単純グラフと言います。

連結性

頂点の集合 V に対し
v\sim w\stackrel{\mathrm{def}}{\Leftrightarrow}\exists e\in E(\varphi(e)=[v,w])
として関係を入れます。この関係は対称律を満たしますが、反射律と推移律を満たしません。そこで、これを反射律と推移律を満たすように拡張し、V 上の同値関係を作ります。この同値関係による V の商集合がただ一つの元からなるとき、V は連結であると言います。
では、具体的にグラフが連結であるとはどういうことでしょうか。上の関係を拡張して作った V 上の同値関係を \approx で表すことにします。
\approx は反射律を満たすので v\approx v は常に成り立ちます。では、v\neq w で v\approx w というのはいかなる状況でしょうか。
それは
v=v_0\sim v_1\sim\cdots\sim v_{m-1}\sim v_m=w (m は 1 でも良い)
となる頂点 v_1,\ldots,v_{m-1} が存在することに他なりません。すると、\sim の定義により
\varphi(e_i)=[v_{i-1},v_i] (i=1,\ldots,m)
なる e_i\in E が存在します。すなわち、v から、いくつかの辺を通って w まで行くことができる、というわけです。これを v から w ヘの歩道と言います。歩道の中でも、e_1,\ldots,e_m が相異なるものを小道と言い、小道の中でも v_0(=v),v_1,\ldots,v_{m-1} が相異なり、また w=v_m\not\in\{v_1,\ldots,v_{m-1}\} であるものを道と言います。特に v=w のとき、小道や道は閉じていると言い、少なくとも 1 本の辺を持つ閉じた道を特に閉路と言います。
このことから分かるように、グラフが連結であるとは、どの相異なる 2 頂点に対しても、その 2 点を結ぶ道があることを言っているのに他なりません。