グラフ理論で出てくる有向グラフや無向グラフはいろいろな分野で出てくる道具です。そのため定義がいくつか存在し、そのグラフの性質により適用できる演算も変わってきます。
そこで、ここではその有向グラフと無向グラフのそれぞれ対応する定義をいくつか簡単に紹介していきます。
集合
そして、
集合
そして、
この定義は多重辺は許さないが自己ループは許す定義となります。
この定義では"多重辺は許さない"という特徴のおかげで、
隣接行列
が定義できます。
というのも、隣接行列
として定義できます。重み関数の値
この隣接行列は代数的な操作ができるためグラフをそのまま扱うよりも扱いやすいです。そのためグラフの性質を調べることが目的となる分野であるグラフ理論や工学系の分野でこの定義が用いられる傾向にあります。
集合
そして、
集合
そして、
この定義は多重辺も自己ループも扱うことができる定義となります。
辺から頂点を取得する定義になので頂点より辺の方が重要だと考える分野で使われる傾向にあります。例えばこの定義の有向グラフは圏論や表現論の分野で使われています。他にもフローなどの辺をよく並べる必要がある分野でも見かけることがあります。
また、
集合
そして
集合
そして
この定義は多重辺も自己ループも扱うことができる定義となります。
辺を頂点のペアでグルーピングした後に辺を起点にして考える定義のため、
辺を起点にした定義
と利用される分野もほぼ同じです。例えばこの有向グラフの定義は圏論の
そして、
そして、
この定義は多重辺も自己ループも許さない定義です。
この定義では頂点と頂点を選んで辺を張るようにして構築するグラフを扱う工学分野で使われる印象にあります。
また、最初の
頂点を起点にした定義
と同じで多重辺を許さないので同様に隣接行列を定義できます。しかし、この定義では自己ループが許されていないので隣接行列の対角成分は
さらに、無向グラフの場合に
そして、
そして、
この定義は多重辺と自己ループを許す定義となります。
この定義は先に接続情報をとってきているだけなので
辺を起点にした定義
の見方を変えただけの定義となります。無向グラフですがよく使われる分野は例えば
結合幾何学(英語版)
があります。結合幾何学の結合構造の定義がまさしくこの定義の個数制限を削除した形の拡張になっています。
また、頂点と辺を入れ替える事として定義される双対という概念を考える際、この接続に注目した定義のほうが考えやすいというのもあります。
ちなみにこの結合関係について調べるときに使われる
で定義されます。
グラフは問題を解決するための道具として利用されるため目的別に定義が変わってくるのは仕方ないです。しかし、このように定義が複数あるのは初学者にとって辛いです。グラフ理論についてよく知ってから定義のバリエーションに触れたほうがわかりやすいと思うので、初学者は自分の得意分野から入って応用中心にグラフを学んでいったほうがグラフ理論の入門には向いていると思います。グラフ理論及び離散数学のググラビリティのひどさはどうにかできないのだろうか
もし今回説明した定義以外にも知っている方がいればコメントにて教えてください。適宜追加します。
以上です。