隣接と接続

数学的な扱いを行う場合, それは集合の対であり, 図としての表現は意味をなさない.

そのため, 図として見れば自明な性質や状態に対しても, 厳密な定義を与える必要がある.

以下に示すのは, グラフの辺や頂点における最も基本的な性質, 頂点同士が辺で結ばれているか? と, 辺と頂点はつながっているか? を定義したものである.

部分グラフと部分グラフ同型

グラフの性質として, そのグラフの一部に特定の形が表れているか否かが重要になる場合がある. また, グラフに関する解析をするときに, グラフをいくつかの部分に分割してそれぞれの結果を得, 最後に統合するような手段もよく使われる.

これらの場合に必要になるのが部分グラフの概念である.

同型-2

前回の記事で抽象的な話をしていたが, 

同型についてもう少し具体的な例を示す.

まず, 次の 2 つのグラフを考える.

\( G = \left(\{1, 2, 3\}, \{\{ 1, 2\},\{ 2, 3\},\{ 1, 3\}\}\right)  \)

\( H = \left(\{a, b, c\}, \{\{ a, b\},\{ b, c\},\{ a, c\}\}\right) \)

これらはどちらもグラフとして図示すれば三角形になる.

しかし, グラフを構成している要素が異なる以上, G = H ではあり得ない.

この「違うグラフ」である「同じ形をしたグラフ」を結びつけるのが同型である.

同型

グラフは実用的には, その頂点と辺の関係性のみが重要となり, 

頂点を意味する集合が何であるかが問題になることは少ない.

それゆえ, 頂点と辺の関係性が同じであるようなグラフは同じものであるとして扱いたい.

ところが, 定義にある通り, グラフは本質的に集合の組であるから, 

用いている集合が異なっていれば同じものと扱うことはできない.

これはリンゴ 3 個とみかん 3 個を同じ 3 として扱うことができないようなもので

とても不便である.

グラフを有意義に扱うためには, 頂点と辺の関係性が同じグラフを同じものであると扱うための同値関係が必要となる, それが同型である.

対応と写像

2つの集合 A と B が存在したときに, 

A の要素と B の要素の間に関係を与えることがある.

このような関係を対応と呼ぶ.

対応は, A の要素 a と B の要素 b が与えられたときに

a と b に関係があるかないかのみを定める.

写像とは対応の 1 種であるが, 方向が定まっていて, 

A から B への写像となると, A のどの要素を選んでも, 

それと対応している B の要素はただ 1 つになっている.

特に, A から B への写像 σ で A の任意の 2 要素 a と a' で

その写像先 b と b' が異なっている場合, σ は 1 対 1 写像であるという.

グラフの定義

\( 2 \) つの集合 \(V\) と \(E\) の組 \( (V, E) \) を考える. このとき, \( E \) の要素が全て \( V \) の要素\( 2 \)つからなる集合であるならば, この組 \( (V, E) \) は グラフ であると言う.

集合の組 \( G = (V, E) \) がグラフであるとき, 最初の集合 \( V \) の要素を \( G \) の頂点, 

次の集合 \( E \) の要素を \( G \) の辺と呼ぶ.

集合論の基礎

グラフの定義を行うまえに, 集合論の基礎をふまえておく必要がある.

ここでは集合について簡単に説明する.

集合とは何らかのものの集まりであり, 個々の 「もの」を要素と呼ぶ.

集合の表現には中括弧を用い, その中に集合の要素を並べて書く. 例えば, \( a \) と \( b \) と \( c \) を集めた集合を \( \{ a, b, c \} \) と表す.

集合を表す際に, 要素の並べ方は自由である. 故に, \( \{a,b,c\} \) と \( \{a,c,b\} \) は同じ集合を表す.

一方で組または,列というものが存在し, こちらは括弧を用いて表記する. これは要素の並び方に意味があり, \( (a,b,c) \) と \( (a,c,b) \) は違う列を表す.

他にも書くことができそうだけど, 必要になるたびに追記する