グラフの基本概念
New
Section: Mathematics

グラフ理論とは

グラフ理論とは、グラフに関する(離散)数学の理論である。

グラフとは

それではグラフとは何なのか。

グラフといえば、折れ線グラフや円グラフ、関数グラフを思い浮かぶかもしれない。

しかしここでいうグラフとは、点の集まりとその点の対を結ぶ辺から構成された構造である。

以下の図は、4つの点a,b,c,da, b, c, dと5つの辺から構成されたグラフである。

a
b
c
d

グラフの定義

グラフのイメージが湧いてきたと思うので、具体的なグラフの定義を紹介する。

グラフ(graph) は順序対G=(V(G),E(G))G=(V(G), E(G))で構成される:

  • V(G)={v1,v2,,vn}V(G)=\{v_1, v_2, \cdots, v_n\}点の集合(vertex set)
  • E(G)={e1,e2,,em}{{vi,vj}vi,vjV(G)ij}E(G)=\{e_1, e_2, \cdots, e_m\} \subseteq \{ \{v_i, v_j\} \mid v_i, v_j \in V(G) \land i \neq j \}は点の非順序対である辺の集合(edge set)

曖昧さを無くした場合、この対象は無向単純グラフと呼ばれる。つまり多重グラフやループグラフは含まれていない。

この記事では時に明記しない限り有限な単純グラフを扱い、単純グラフをグラフと呼ぶ。

a
b
c
d

グラフGGにおいて、V(G)V(G)E(G)E(G)は、

V(G)={a,b,c,d}E(G)={{a,b},{a,c},{b,d},{c,d}}\begin{aligned} V(G) &= \{ a, b, c, d \} \\ E(G) &= \{ \{a, b\}, \{a, c\}, \{b, d\}, \{c, d\} \} \\ \end{aligned}

点や辺の関係

位数と大きさ

それぞれの集合の要素の数は次のように呼ばれている。

グラフGGにおいて、

  • V(G)V(G)の要素の個数V(G)|V(G)|GG位数(order)
  • E(G)E(G)の要素の個数E(G)|E(G)|GGサイズ(size)

また位数pとサイズqであるグラフを (p,q)-グラフ((p,q)-graph) という。

グラフGGが位数pであるとき、サイズqの最大値(完全グラフのサイズ)はいくらであるか。

まず具体的なpにおけるqの最大値を考えると、

例えばp=0p=0のとき、q=0q=0である。

次にp=1p=1のとき、q=0q=0である。

a

p=2p=2のとき、q=1q=1である。

a
b

p=3p=3のとき、q=3q=3である。

a
b
c

p=4p=4のとき、q=6q=6である。

a
b
c
d

つまり、ある点は他の全ての点と結ばれて辺となっている。

よって、

max(q)={0p=0,1(p2)p2max(q) = \begin{cases} 0 & p = 0, 1 \\ {p \choose 2} & p \ge 2 \end{cases}

点と(点|辺)の関係

グラフGGにおいて、e={u,v}E(G)e=\{u, v\} \in E(G)とするとき

e
u
v

  • uuと点vv隣接(adjacent) している
  • uuと点vvは辺ee端点(endpoint)
    • eeとその端点は 接続(incident) している

辺と辺の関係

グラフGGにおいて、e,fE(G),efe, f \in E(G), e \ne fとするとき

  • efe \cap f \ne \emptysetのとき、辺eeと辺ff隣接(adjacent) している

点の近傍と次数

グラフGGにおいて、

  • vV(G)v \in V(G)において、NG(v)={uV(G){u,v}E(G)}N_G(v)=\{u \in V(G) \mid \{u,v\} \in E(G)\}とし、これを点vv近傍 という
  • vV(G)v \in V(G)において、dG(v)=NG(v)d_G(v)=|N_G(v)|を点vv次数(degree) という
    • 次数が0の点を孤立点(isolated vertex)
    • 次数が偶数の点を偶点(even vertex)
    • 次数が奇数の点を奇点(odd vertex)
    • グラフGG最小次数(minimum vertex degree)δ(G)\delta (G)
    • グラフGG最大次数(maximum vertex degree)Δ(G)\Delta (G)

以上から次の定理が導かれる。

(p,q)-グラフGGにおいて、

i=1pdG(vi)=2q\sum_{i=1}^p d_G(v_i) = 2 q

握手補題を用いて、次の系が導かれる。

グラフの奇点は、偶数個存在する

グラフの種類

同型写像と同型

あるグラフがどの種類になるか判定するうえで必要なものとして、二つのグラフが同じであるかを知る必要がある。グラフが等しいか判断できないと、あるグラフの種類を知ることができない。

そのためにまずは、2つのグラフが同じであることを表している同型について説明していく。

グラフG1=(V(G1),E(G1))G_1=(V(G_1), E(G_1))とグラフG2=(V(G2),E(G2))G_2=(V(G_2), E(G_2))において、

  • 以下の条件を満たす写像f:V(G1)V(G2)f: V(G_1) \rightarrow V(G_2)同型写像(isomorphism) という

    1. 全単射写像
    2. 任意の2点u,vV(G1)u, v \in V(G_1)において、{u,v}E(G1)    {f(u),f(v)}E(G2)\{u, v\} \in E(G_1) \iff \{f(u), f(v)\} \in E(G_2)
  • 同型写像f:V(G1)V(G2)f:V(G_1) \rightarrow V(G_2)が存在するとき、グラフG1G_1とグラフG2G_2同型(isomorphic) G1G2G_1 \cong G_2である

部分グラフ

グラフGGとグラフGG^{\prime}において、

  • V(G)V(G)V(G^{\prime}) \subseteq V(G)かつE(G)E(G)E(G^{\prime}) \subseteq E(G)のとき、グラフGG^{\prime}はグラフGG部分グラフ(subgraph) という
  • 特にV(G)=V(G)V(G^{\prime}) = V(G)のとき、グラフGG^{\prime}はグラフGG全域部分グラフ(spanning subgraph) という

誘導部分グラフ

グラフGGとグラフGG^{\prime}において、

  • 次の条件を満たすとき、グラフGG^{\prime}はグラフGG(点)誘導部分グラフ((vertex) induced subgraph)

    1. V(G)V(G)V(G^{\prime}) \subseteq V(G)
    2. GG^{\prime}の任意の2点u,vV(G)u, v \in V(G^{\prime})において、{u,v}E(G)    {u,v}E(G)\{u, v\} \in E(G^{\prime}) \iff \{u, v\} \in E(G)
  • 次の条件を満たすとき、グラフGG^{\prime}はグラフGG辺誘導部分グラフ(edge induced subgraph)

    1. E(G)E(G)E(G^{\prime}) \subseteq E(G)
    2. GG^{\prime}の任意の辺e={u,v}E(G)e=\{u, v\} \in E(G^{\prime})において、u,vV(G)    u,vV(G)u, v \in V(G^{\prime}) \iff u, v \in V(G)

点誘導部分グラフはV(G)V(G^{\prime})、辺誘導部分グラフはE(G)E(G^{\prime})が決まった時点で、一意に存在する

正則グラフ

  • 各点の次数が全て等しいグラフを、 正則グラフ(regular graph)
  • 各点の次数がrrの正則グラフを、 r-正則グラフ(r-regular graph)

完全グラフ

  • 任意の2点が隣接しているグラフを、 完全グラフ(complete graph)
  • 位数ppの完全グラフをKpK_p
  • KpK_pのサイズはq=(p2)q = {p \choose 2}

補グラフ

次の条件を満たすとき、グラフGˉ\bar{G}とグラフGGは互いに互いの 補グラフ(complement graph)

  1. V(Gˉ)=V(G)V(\bar{G})=V(G)
  2. 任意の2点{u,v}E(Gˉ)    {u,v}E(G)\{u, v\} \notin E(\bar{G}) \iff \{u, v\} \in E(G)

(p,q)(p,q)-グラフGGとその補グラフである(p,qˉ)(p, \bar{q})-グラフGˉ\bar{G}において、

q+qˉ=(p2)q + \bar{q} = {p \choose 2}

自己補グラフ

グラフGGとその補グラフGˉ\bar{G}において、同型GGˉG \cong \bar{G}であるとき、Gˉ\bar{G}自己補グラフ(self-complementary graph)

n部グラフ

グラフGGにおいて、

  • V(G)V(G)nn個の部分集合V1,V2,,VnV_1, V_2, \cdots, V_nに分割され、任意の辺eE(G)e \in E(G)の2点が違う部分集合に属するとき、n部グラフ(n-partite graph)

完全n部グラフ

グラフGGにおいて、

  • 任意の点において、隣接している全ての点がその点と違う部分集合に属するとき、完全n部グラフ(complete n-partite graph)
  • V1=p1,V2=p2,,Vn=pn|V_1| = p_1, |V_2| = p_2, \cdots, |V_n| = p_nとすると、Kp1,p2,,pnK_{p_1,p_2, \cdots, p_n}で表される

二部グラフ

n=2n = 2のn部グラフを二部グラフ(bipartite graph)

グラフの演算

グラフG1G_1とグラフG2G_2において、次の条件を満たすとき、グラフGGG1G_1G2G_2和(union) といい、G=G1G2G=G_1 \cup G_2で表される

  1. V(G)=V(G1)V(G2)V(G) = V(G_1) \cup V_(G_2)
  2. E(G)=E(G1)E(G2)E(G) = E(G_1) \cup E_(G_2)

結び

グラフG1G_1とグラフG2G_2において、次の条件を満たすとき、グラフGGG1G_1G2G_2結び(join) といい、G=G1+G2G=G_1 + G_2で表される

  1. V(G)=V(G1)V(G2)V(G) = V(G_1) \cup V_(G_2)
  2. E(G)=E(G1)E(G2){{u,v}uV(G1)vV(G2)}E(G) = E(G_1) \cup E_(G_2) \cup \{\{u, v\} \mid u \in V(G_1) \land v \in V(G_2)\}

完全二部グラフになる

デカルト積

グラフG1G_1とグラフG2G_2において、次の条件を満たすとき、グラフGGG1G_1G2G_2デカルト積(cartesian product) といい、G=G1×G2G=G_1 \times G_2で表される

  1. V(G)={(u,v)uV(G1)vV(G2)}V(G) = \{(u, v) \mid u \in V(G_1) \land v \in V(G_2)\}
  2. {(u1,v1),(u2,v2)}E(G)    (u1=u2(v1,v2)E(G2))(v1=v2(u1,u2)E(G1))\{(u_1, v_1), (u_2, v_2)\}\in E(G) \iff (u_1 = u_2 \land (v_1,v_2) \in E(G_2)) \lor (v_1 = v_2 \land (u_1,u_2) \in E(G_1))

次数列

グラフGGにおいて、

全ての点の次数を広義単調減少となるように並べた列を、グラフGG次数列(degree sequence)

  • 次数列の和は、偶数
  • 互いに非同型の2つのグラフにおいて、同じ次数列を持つこともある

以下のグラフの次数列は、

a
b
c
d

(3, 3, 2, 2)

グラフの列

次数列っぽい列において、それがいくつかのグラフになっているかどうかを判定したいような問題(次数列問題 (degree sequence problem))がある。

グラフの列(graphic sequence) とは、その順序対が、いくつかのグラフの次数列になっていることをいう。

広義単調減少となるように並べた自然数の列(d1,d2,,dn)(d_1, d_2, \cdots, d_n)において、

以下の条件を満たすとき、列はあるグラフの次数列である。

  1. i=1n\sum_{i=1}^nは偶数
  2. 全てのkk、範囲は(1kn)(1 \le k \le n)において i=1kdik(k1)+i=k+1nmin(di,k)\sum_{i=1}^k d_i \le k (k-1) + \sum_{i=k+1}^n min(d_i, k)

参考文献

  • 織田 進・佐藤 淳郎, グラフ理論の基礎・基本 
  • 仁平 政一・西尾 義典, グラフ理論 序説 改訂版 
  • Wikipedia