グラフの定義いくつか

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

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

１：頂点を起点にした定義

有向グラフ

集合$V$と集合$E \subseteq V \times V$の組$G = \paren{V,\ E}$を有向グラフと呼ぶ。

そして、$V$の元を頂点（またはノード）、$e=\paren{s,\ t} \in E $を辺（または有向辺、ダイエッジ、エッジ）と呼び、$s$を$e$の始点、$t$を$e$の終点と呼ぶ。

無向グラフ

集合 $V$と集合 $E \subseteq \brace{\brace{x,\ y} \mid x,\ y \in V}$の組$G = \paren{V,\ E}$を無向グラフと呼ぶ。

そして、$V$の元を頂点（またはノード）、$e=\brace{x,\ y} \in E$を辺（またはエッジ）と呼び、$x$と$y$をそれぞれ$e$の端点と呼ぶ。また、$\abs{e} = 1$のとき $e$を自己ループと呼ぶ。

特徴

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

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

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

２：辺を起点にした定義

有向グラフ

集合$V,\ E$、関数 $\fname{dom},\ \fname{cod}: E \to V$からなる組$G = \paren{V,\ E,\ \fname{dom},\ \fname{cod}}$を有向グラフと呼ぶ。

そして、$V$の元を頂点、$e \in E$を辺、$\fnp{dom}{e}$を$e$の始点、$\fnp{cod}{e}$を$e$の終点と呼ぶ。

無向グラフ

集合$V,\ E$、関数$\fname{g}: E \to \brace{\brace{x,\ y} \mid \paren{x,\ y} \in V \times V}$からなる組$G = \paren{V,\ E,\ \fname{g}}$を無向グラフと呼ぶ。

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

特徴

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

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

また、$\fname{dom}$と$\fname{cod}$をまとめて$\phi = \paren{\fname{dom},\ \fname{cod}}:E \to V \times V$とし、$G = \paren{V,\ E,\ \phi}$を有向グラフとして定義する亜種も存在します。

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

有向グラフ

集合$V$と$i,\ j \in V$に対して定義されるお互いに共通を持たない集合$E_{i,\ j} $からなる集合族$E = \brace{E_{i,\ j} \mid i,\ j∈V}$を考える。このとき組$G = \paren{V,\ E}$を有向グラフと呼ぶ。

そして$V$の元を頂点、$E_{i,\ j}$を$i$から$j$の辺の集合（辺集合）、$e \in E_{i,\ j}$を$i$から$j$への辺、$i$を辺$e$の始点、$j$を辺$e$の終点と呼ぶ。

無向グラフ

集合$V$と$i,\ j \in V$に対して定義されるお互いに共通を持たない集合$E_{i,\ j}$からなる集合族$E = \brace{E_{i,\ j} \mid {i,\ j} \in V, E_{i,\ j} = E_{j,\ i} }$を考える。このとき組$G = \paren{V,\ E}$を無向グラフと呼ぶ。

そして$V$の元を頂点、$E_{i,\ j}$を$i$と$j$を端点に持つ辺の集合（辺集合）、$e \in E_{i,\ j}$を$i$と$j$を端点に持つ辺、$i$と$j$を辺$e$の端点と呼ぶ。

特徴

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

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

４：異なる頂点の組を辺とみる定義

有向グラフ

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

そして、$V$の元を頂点、$e = \paren{s,\ t} \in E$を辺、$s$を辺$e$の始点、$t$を辺$e$の終点と呼ぶ。

無向グラフ

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

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

特徴

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

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

５：結合関係に注目した定義

有向グラフ

$V$,$E$を集合とし、$V$と$E$上の二項関係$I_s$, $I_t$で任意の$e \in E$に対してある元$x,\ y \in V$が存在し$I_s \cap \paren{V \times \brace{e}} = \brace{x} \times \brace{e}$、$I_t \cap \paren{V \times \brace{e}} = \brace{y} \times \brace{e}$が成り立っているものを考える。このとき、$G=\paren{V,\ E,\ I_s,\ I_t}$を有向グラフと呼ぶ。

そして、$V$の元を頂点、$e \in E$を辺、$x$を辺$e$の始点、$y$を辺$e$の終点と呼ぶ。また、$x$から$y$へと$e$で接続しているともいう。そして、$I_s$と$I_t$をそれぞれフラグ集合（または、結合関係）と呼ぶ。さらに、頂点$x$が辺$e$の始点のとき$xI_se$、頂点$y$が辺$e$の終点のとき$yI_te$と表記する。

無向グラフ

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

そして、$V$の元を頂点、$e \in E$を辺、$x$と$y$を辺$e$の端点と呼ぶ。また、$x$と$y$は$e$に接続しているともいう。そして、$I$をフラグ集合（または、結合関係）と呼ぶ。さらに、頂点$x$が辺$e$の端点のとき$xIe$と表記する。

特徴

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

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

ちなみにこの結合関係について調べるときに使われる$\abs{\fnp{V}{G}} \times \abs{\fnp{E}{G}} $の 結合行列 $B$は

$G$が有向グラフの場合は
$$ \fnp{B}{v,\ e} = \begin{cases} -1 & (vI_se) \\ 1 & (vI_te) \\ 0 & (\text{otherwise}) \end{cases} $$

$G$が無向グラフの場合は
$$ \fnp{B}{v,\ e} = \begin{cases} 1 & (vIe) \\ 0 & (\text{otherwise}) \end{cases} $$

で定義されます。

まとめ

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

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

以上です。