応用数学
有向グラフ・無向グラフ グラフ(Graph)は、V(Vertex)とE(Edge)からなる図形で、G = ( V , E )と表す。 Vは、頂点の集合のこと。節点ともいう。 Eは、2つの頂点を連結する辺の集合のこと。枝ともいう。 有向グラフ 頂点V1と頂点V2に、順序があるグラフのこと。 頂点に入ってくる辺の数を入次数、出ていく辺の数を出次数という。 また、入次数と出次数の和を次数という。 無向グラフ 頂点V1と頂点V2に順序がないグラフのこと。 有向グラフにおいて、頂点V1と頂点V2を連結する辺は、順序を ( V1 , V2 ) で表現することができる。この時、頂点V1を始点、頂点V2を終点という。 自己ループは、始点と終点が同一である辺のこと。 多重辺は、始点と終点を共有する複数の辺のこと。並列辺ともいう。 歩道・経路 歩道は、グラフの頂点と辺を結んだもの。全ての頂点が異なるものを経路、全ての辺が異なるものを小道という。 ある頂点から出発して同じ頂点に戻る歩道について、全ての頂点が異なる場合を閉路、全ての辺が異なる場合を回路というよ。 サイクリックグラフ・非サイクリックグラフ 有向グラフは、閉路の有無により次のように分かれる。 サイクリックグラフ 閉路がある有向グラフのこと。 点線の部分が閉路になるよ。 非サイクリックグラフ 閉路がない有向グラフのこと。 辺の向きに頂点を並べることができ、この頂点の並びをトポロジカル順序という。 グラフの種類 グラフには、次のような種類がある。 グラフ 名称