グラフ理論

用語

頂点集合(vertex set)、ニ頂点を結ぶ辺集合(edge set)からなる構造のこと。形式的には、グラフGは頂点集合V(G)、辺集合E(G)と表す。

例えば、以下のようなグラフGを考える。

この場合、

V(G) = {A, B, C, D}
E(G) = {AD, BD, CD}

となる。

あるグラフGとその一つの頂点vに対して、vと辺で結ばられている頂点の集合のことをvの近傍(neighborhood)という。

vから出ている辺の数をvのGでの次数(degree)という。

任意のグラフGで全頂点の次数の和はGの辺数の2倍である。

${\sum_{v\in V(G)} deg(G) = 2|E(G)|}$

V(G)が全て辺で結ばれているグラフを完全グラフ(complete graph)という。

頂点数がnの完全グラフを ${K_n}$ と書く。

また、握手補題を用いると、以下の定理が導かれる。

${K_n}$ の辺の数は ${\frac{n(n-1)}{2}}$ である。

${|E(K_n)| = \frac{n(n-1)}{2}}$

グラフGのV(G)を"A,B内に辺がない"を満たすA,Bへ分割できるとき、2部グラフ(bipartite graph)という。

A,Bに分割したとき、Aの全頂点がBの全頂点と結ばれているグラフを完全二部グラフ(complete bipartite graph)という。

Aの頂点数がr, Bの頂点数がsのときの完全二部グラフは ${K_{r,s}}$ と書く。

二部グラフと歩道の関係について以下の定理が成り立つ。

二部グラフの閉じた歩道の長さは偶数である。 (続)