はなちるのマイノート

Unityをメインとした技術ブログ。自分らしくまったりやっていきたいと思いますー!

グラフ理論の基礎についてのメモ①

はじめに

今回はグラフ理論の基礎について書きたいと思います。

細かい証明などは一切なく、色々な用語や定理などを爆速で列挙していきます。

グラフ

グラフGは点集合をV,辺集合をEとしたとき G=(V, E)と書かれます。

辺に向きがあるときは有向グラフといい,辺がないときは無向グラフになります。

f:id:hanaaaaaachiru:20200608003030p:plain

辺eが点対(u,v)のとき,色々な用語があります。

  • 辺eは点uと点vを結ぶ(Join)
  • 辺eはuおよびvに接続している(incident)
  • 点uと点vは辺eの端点(end)
  • u=vなる辺はループ(loop)
  • 同じ点対の辺は多重辺(multiple edges)

f:id:hanaaaaaachiru:20200608004120p:plain

単純グラフ・多重グラフ

ループも多重辺もないグラフを単純グラフ(simple graph)といいます。

逆に多重辺もありえる一般のグラフを多重グラフ(multiple graph)と呼ばれます。

有限グラフと無限グラフ

グラフGに含まれる点の個数|V|および辺の本数|E|が有限であれば有限グラフ(finite graph)といいます。

逆に点の個数もしくは辺の個数が無限であるグラフは無限グラフ(infinite graph)と呼ばれます。


またグラフGに含まれる点の個数を V(G),辺の本数を E(G)と書くこともあります。

次数

点vに接続している辺の本数d(v)をvの次数(degree)といいます。

次数の総和 \sum_{v \in V}d(v)は偶数になることが知られています。

また次数0の点を孤立点と呼びます。

部分グラフ

グラフG=(V,E)の辺および点のいくつかを消去して得られるグラフはGの部分グラフ(sub-graph)と呼ばれます。

 グラフG=(V,E)に対し、 V'\subseteq V かつE' \subseteq EなるグラフG'=(V',E')はGの部分グラフ

特に V=V'のときはGの全域部分グラフ(spanning subgraph)といいます。

また一部の頂点を取り出し、その頂点対の辺の有無が元のグラフと一致するグラフを誘導部分グラフ(induced subgraph)と呼びます。

f:id:hanaaaaaachiru:20200608010352p:plain

歩道

グラフGの歩道W(walk)は連続した点と辺の列です。

f:id:hanaaaaaachiru:20200608015024p:plain

始まりの点を始点(initial vertex),終わりの点を終点(terminal vertex)といい、歩道に現れる辺の総数を歩道の長さといいます。

歩道にはいくつかの種類があります。

  • 歩道の全ての「辺」が異なる  => 小道(trail)
  • 歩道の全ての「点」が異なる  => 道(path)
  • 始点と終点が一致している小道 => 回路(circuit)
  • 始点と終点が一致している道  => 閉路(cycle)

一般的に以下のような関係になっています。

  • 道 => 小道
  • 回路 => 小道
  • 閉路 => 道
  • 閉路 => 回路

f:id:hanaaaaaachiru:20200608015803p:plain

連結性

グラフGの任意な2点間に道があるとき、Gは連結(connected)であるといいます。

連結でないグラフはいくつかの極大な連結部分グラフに分割でき、それを連結成分(connected component)もしくは成分と呼ばれます。

f:id:hanaaaaaachiru:20200609181902p:plain

完全グラフ

どの2点の間にも1本の辺がある単純グラフを完全グラフ(complete graph)といいます。

f:id:hanaaaaaachiru:20200609182435p:plain

n個の点からなる完全グラフ K_nと書き、 K_nには \left(\begin{array}{c}n\\ 2\end{array}\right)=n(n-1)/2の辺があることが知られています。

2部グラフ,正則グラフ

G=(V,E)のVを適当に2つの部分集合XとYに分割し、Gのどの辺もXの点とYの点を結び、Xの点どうし,Yの点どうしを結ぶ辺はないようにしたグラフと2部グラフ(bipartite graph)でいいます。

 G=(X\cup Y, E)と書かれ、XとYは2部グラフのGの点クラス(partite graph)と呼ばれます。

グラフGのすべての閉路の長さが偶数 <=> Gは2部グラフ

またXの任意の点とYん任意の点を結ぶ辺が必ずあるときGは完全2部グラフ(complete bipartite graph)といい、 r=|X|, s=|Y|のとき K_{r,s}と書きます。

さらにグラフGの全ての点の次数がkであるとき、Gはk次の正則グラフ(regular graph)と呼びます。

f:id:hanaaaaaachiru:20200609193518p:plain

林,木

連結で閉路のないグラフを木(tree)といい、連結とは限らないが閉路がないグラフを林(forest)といいます。

f:id:hanaaaaaachiru:20200609200821p:plain

また木には以下のような定理が成り立ちます。

木G=(V,E)の点数n=|V|と辺数m=|E|の間には、m=n-1の関係がある

全域木,最小全域木

グラフGのの全域部分グラフでかつ木であるものをグラフGの全域木(spanning tree),またはGの木といいます。

また辺の重みの和が最小な木を最小全域木(minimum spanning tree)と呼びます。

f:id:hanaaaaaachiru:20200609224322p:plain

さいごに

メモ②に続く。。。