グラフ

グラフの定義

まずはグラフを定義する。

有限集合VVの部分集合の族Eの対G=(V,E)ハイパーグラフ (hypergraph)と呼ぶ。

Eが異なるk個の元からなるVの部分集合の族のとき、G=(V,E)k-ハイパーグラフという。特にEが異なる2元からなるVの部分集合の族のとき、G=(V,E)を単純グラフと呼ぶ。

V の異なる k 個の要素全体のなす集合を [V]k によりあらわす。k-ハイパーグラフは、E[V]k となる、対 (V,E) のことであり、グラフは、E[V]2 となる、対 (V,E) のことである。

以下では単純グラフのことをグラフ (graph)と呼ぶ。

グラフG=(V,E)の集合Vを頂点集合、集合Eを辺集合と呼びそれぞれV(G), E(G)と書く。

V(G)の元を頂点 (vertex)、 E(G)の元を (edge)と呼ぶ。

{u,v}E(G)を単にuvあるいはvuと書く。

グラフGの頂点の数 |V|オーダーあるいは位数 (order)、辺の数 |E|サイズあるいは大きさ (size)と呼ぶ。G のオーダーを |G| によりあらわし、サイズを e(G) によりあらわす。

G=(V,E) がオーダーn のグラフであるとき、
0|E|(n2)=n(n1)2
となる。

頂点e=uvE(G)のとき、uv隣接する (adjacent)と言い、ue接続する (incident) と言う。また euv結ぶ (join) と言い、頂点 u, v を辺 e端点 (endvertex) という。

グラフHV(H)V(G)かつE(H)E(G)を満たすとき、HGサブグラフあるいは部分グラフ (subgraph)と呼ぶ。
V(H)=VV で、E(H)x,yV となる辺 xyE(G) をすべて含んでいるとき、HV により誘導される (induced, spanned) 部分グラフであるといい、G[V] によりあらわす。

V(G)をどのように二つの集合X,Yに分割してもあるxX,yYが存在してxyE(G)となるとき、G連結グラフ (connected graph) と呼ぶ。

グラフ G1=(V1,E1) と グラフ G2=(V2,E2)同型 (isomorphic) であるとは、頂点の集合の全単射 ψ:V1V2, xψx が存在し、xyE1ψxψyE2 となることをいう。グラフの構造について議論するときは、同型なグラフを同一視して議論することも多い。

代表的なグラフ

グラフ理論の議論をする際によく表れる代表的なグラフを定義する。

任意の頂点が隣接するグラフを完全グラフ (complete graph)と呼び、オーダーnの完全グラフをKnと書く。e(Kn)=(n2)=n(n1)2 となる。

どの頂点も隣接しないグラフを空グラフ (empty graph)と呼び、オーダーnの完全グラフをEnと書く。e(En)=0 となる。また、E1=K1 である。

隣り合う頂点のみが隣接するように一列に並べられるグラフをパスグラフと呼び、オーダーn+1のパスグラフをPnと書く。Pn長さ (length)を n と定める。パスグラフを単にパスあるいは (path) ともいう。

隣り合う頂点のみが隣接するように円周上に並べられるグラフをサイクルグラフと呼び、オーダーnのサイクルグラフをCnと書く。Cn の長さを n と定める。サイクルグラフを単にサイクルあるいは閉路 (cycle) ともいう。Cnn角形ともいう。

任意の頂点の次数が等しいグラフを正則グラフ (regular graph)と呼ぶ。

Mathpediaを支援する

現在のページ

グラフ
  1. グラフの定義
  2. 代表的なグラフ
前のページへ
2 / 14
次のページへ
前ページへ
グラフ理論入門の表紙
次ページへ