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

前回の記事で抽象的な話をしていたが, 同型についてもう少し具体的な例を示す. まず, 次の 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 \) つの集合 \(V\) と \(E\) の組 \( (V, E) \) を考える. このとき, \( E \) の要素が全て \( V \) の要素\( 2 \)つからなる集合であるならば, この組 \( (V, E) \) は グラフ であると言う. 集合の組 \( G = (V, E) \) がグラフであるとき, 最初の集…