5

グラフの定義いくつか

873
2

グラフ理論で出てくる有向グラフや無向グラフはいろいろな分野で出てくる道具です。そのため定義がいくつか存在し、そのグラフの性質により適用できる演算も変わってきます。

そこで、ここではその有向グラフと無向グラフのそれぞれ対応する定義をいくつか簡単に紹介していきます。

1:頂点を起点にした定義

有向グラフ

集合Vと集合EV×Vの組G=(V, E)を有向グラフと呼ぶ。

そして、Vの元を頂点(またはノード)、e=(s, t)Eを辺(または有向辺、ダイエッジ、エッジ)と呼び、seの始点、teの終点と呼ぶ。

無向グラフ

集合 Vと集合 E{{x, y}x, yV}の組G=(V, E)を無向グラフと呼ぶ。

そして、Vの元を頂点(またはノード)、e={x, y}Eを辺(またはエッジ)と呼び、xyをそれぞれeの端点と呼ぶ。また、|e|=1のとき eを自己ループと呼ぶ。

特徴

この定義は多重辺は許さないが自己ループは許す定義となります。

この定義では"多重辺は許さない"という特徴のおかげで、 隣接行列 が定義できます。
というのも、隣接行列A
A(x, y)={w(x, y)(x から y への辺(無向グラフの場合xyを端点に持つ辺)0(otherwise)
として定義できます。重み関数の値w(x, y)xを始点、yを終点としたときの重みで、重みを考えないときは単に1とします。

この隣接行列は代数的な操作ができるためグラフをそのまま扱うよりも扱いやすいです。そのためグラフの性質を調べることが目的となる分野であるグラフ理論や工学系の分野でこの定義が用いられる傾向にあります。

2:辺を起点にした定義

有向グラフ

集合V, E、関数 dom, cod:EVからなる組G=(V, E, dom, cod)を有向グラフと呼ぶ。

そして、Vの元を頂点、eEを辺、dom(e)eの始点、cod(e)eの終点と呼ぶ。

無向グラフ

集合V, E、関数g:E{{x, y}(x, y)V×V}からなる組G=(V, E, g)を無向グラフと呼ぶ。

そして、Vの元を頂点、eEを辺、g(e)の元をeの端点と呼ぶ。

特徴

この定義は多重辺も自己ループも扱うことができる定義となります。

辺から頂点を取得する定義になので頂点より辺の方が重要だと考える分野で使われる傾向にあります。例えばこの定義の有向グラフは圏論や表現論の分野で使われています。他にもフローなどの辺をよく並べる必要がある分野でも見かけることがあります。

また、domcodをまとめてϕ=(dom, cod):EV×Vとし、G=(V, E, ϕ)を有向グラフとして定義する亜種も存在します。

3:同じ頂点間の辺をグルーピングした定義

有向グラフ

集合Vi, jVに対して定義されるお互いに共通を持たない集合Ei, jからなる集合族E={Ei, ji, jV}を考える。このとき組G=(V, E)を有向グラフと呼ぶ。

そしてVの元を頂点、Ei, jiからjの辺の集合(辺集合)、eEi, jiからjへの辺、iを辺eの始点、jを辺eの終点と呼ぶ。

無向グラフ

集合Vi, jVに対して定義されるお互いに共通を持たない集合Ei, jからなる集合族E={Ei, ji, jV,Ei, j=Ej, i}を考える。このとき組G=(V, E)を無向グラフと呼ぶ。

そしてVの元を頂点、Ei, jijを端点に持つ辺の集合(辺集合)、eEi, jijを端点に持つ辺、ijを辺eの端点と呼ぶ。

特徴

この定義は多重辺も自己ループも扱うことができる定義となります。

辺を頂点のペアでグルーピングした後に辺を起点にして考える定義のため、 辺を起点にした定義 と利用される分野もほぼ同じです。例えばこの有向グラフの定義は圏論のHom(i, j)で定義する小さい圏で見られます。

4:異なる頂点の組を辺とみる定義

有向グラフ

Vを集合とし、V, 2Vの異なる2つの元s, tからなる順序対(s, t)の全体とする。このときVV, 2の部分集合Eとの組G=(V, E)を有向グラフと呼ぶ。

そして、Vの元を頂点、e=(s, t)Eを辺、sを辺eの始点、tを辺eの終点と呼ぶ。

無向グラフ

Vを集合とし、(V, 2)Vの異なる2つの元x, yからなる集合{x, y}の全体とする。このときV(V, 2)の部分集合Eとの組G=(V, E)を無向グラフと呼ぶ。

そして、Vの元を頂点、e={x, y}Eを辺、xyを辺eの端点と呼ぶ。

特徴

この定義は多重辺も自己ループも許さない定義です。

この定義では頂点と頂点を選んで辺を張るようにして構築するグラフを扱う工学分野で使われる印象にあります。
また、最初の 頂点を起点にした定義 と同じで多重辺を許さないので同様に隣接行列を定義できます。しかし、この定義では自己ループが許されていないので隣接行列の対角成分は0となります。
さらに、無向グラフの場合に(V, 2)の"2つの元"という制限を取っ払ってVの非空な部分集合の全体のP(V){}に置き換えた場合、この無向グラフの定義は (無向)ハイパーグラフ の定義となります。このハイパーグラフは組合せ論のブロックデザインで利用されていたりします。

5:結合関係に注目した定義

有向グラフ

V,Eを集合とし、VE上の二項関係Is, Itで任意のeEに対してある元x, yVが存在しIs(V×{e})={x}×{e}It(V×{e})={y}×{e}が成り立っているものを考える。このとき、G=(V, E, Is, It)を有向グラフと呼ぶ。

そして、Vの元を頂点、eEを辺、xを辺eの始点、yを辺eの終点と呼ぶ。また、xからyへとeで接続しているともいう。そして、IsItをそれぞれフラグ集合(または、結合関係)と呼ぶ。さらに、頂点xが辺eの始点のときxIse、頂点yが辺eの終点のときyIteと表記する。

無向グラフ

V,Eを集合とし、VE上の二項関係Iで任意のeEに対してある元x, yVが存在しI(V×{e})={x, y}×{e}が成り立っているものを考える。このとき組G=(V, E, I)を無向グラフと呼ぶ。

そして、Vの元を頂点、eEを辺、xyを辺eの端点と呼ぶ。また、xyeに接続しているともいう。そして、Iをフラグ集合(または、結合関係)と呼ぶ。さらに、頂点xが辺eの端点のときxIeと表記する。

特徴

この定義は多重辺と自己ループを許す定義となります。

この定義は先に接続情報をとってきているだけなので 辺を起点にした定義 の見方を変えただけの定義となります。無向グラフですがよく使われる分野は例えば 結合幾何学(英語版) があります。結合幾何学の結合構造の定義がまさしくこの定義の個数制限を削除した形の拡張になっています。
また、頂点と辺を入れ替える事として定義される双対という概念を考える際、この接続に注目した定義のほうが考えやすいというのもあります。

ちなみにこの結合関係について調べるときに使われる|V(G)|×|E(G)| 結合行列 B

Gが有向グラフの場合は
B(v, e)={1(vIse)1(vIte)0(otherwise)

Gが無向グラフの場合は
B(v, e)={1(vIe)0(otherwise)

で定義されます。

まとめ

グラフは問題を解決するための道具として利用されるため目的別に定義が変わってくるのは仕方ないです。しかし、このように定義が複数あるのは初学者にとって辛いです。グラフ理論についてよく知ってから定義のバリエーションに触れたほうがわかりやすいと思うので、初学者は自分の得意分野から入って応用中心にグラフを学んでいったほうがグラフ理論の入門には向いていると思います。
グラフ理論及び離散数学のググラビリティのひどさはどうにかできないのだろうか

もし今回説明した定義以外にも知っている方がいればコメントにて教えてください。適宜追加します。

以上です。

投稿日:2021125
OptHub AI Competition

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。
バッチを贈って投稿者を応援しよう

バッチを贈ると投稿者に現金やAmazonのギフトカードが還元されます。

投稿者

ogata_k
ogata_k
11
1462
興味の赴くまま数学をやってます。 (有向・無向・ハイパー)グラフが好きです。

コメント

他の人のコメント

コメントはありません。
読み込み中...
読み込み中
  1. 1:頂点を起点にした定義
  2. 有向グラフ
  3. 無向グラフ
  4. 特徴
  5. 2:辺を起点にした定義
  6. 有向グラフ
  7. 無向グラフ
  8. 特徴
  9. 3:同じ頂点間の辺をグルーピングした定義
  10. 有向グラフ
  11. 無向グラフ
  12. 特徴
  13. 4:異なる頂点の組を辺とみる定義
  14. 有向グラフ
  15. 無向グラフ
  16. 特徴
  17. 5:結合関係に注目した定義
  18. 有向グラフ
  19. 無向グラフ
  20. 特徴
  21. まとめ