数学的な扱いを行う場合, それは集合の対であり, 図としての表現は意味をなさない. そのため, 図として見れば自明な性質や状態に対しても, 厳密な定義を与える必要がある. 以下に示すのは, グラフの辺や頂点における最も基本的な性質, 頂点同士が辺で結ばれ…

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

前回の記事で抽象的な話をしていたが, 同型についてもう少し具体的な例を示す. まず, 次の 2 つのグラフを考える. \( G = \left(\{1, 2, 3\}, \{\{ 1, 2\},\{ 2, 3\},\{ 1, 3\}\}\right) \) \( H = \left(\{a, b, c\}, \{\{ a, b\},\{ b, c\},\{ a, c\}\}\ri…

グラフは実用的には, その頂点と辺の関係性のみが重要となり, 頂点を意味する集合が何であるかが問題になることは少ない. それゆえ, 頂点と辺の関係性が同じであるようなグラフは同じものであるとして扱いたい. ところが, 定義にある通り, グラフは本質的に…

2つの集合 A と B が存在したときに, A の要素と B の要素の間に関係を与えることがある. このような関係を対応と呼ぶ. 対応は, A の要素 a と B の要素 b が与えられたときに a と b に関係があるかないかのみを定める. 写像とは対応の 1 種であるが, 方向…

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