グラフ (離散数学)
X {\displaystyle X} の元 x {\displaystyle x} は、 x R y {\displaystyle xRy} である場合にのみ X {\displaystyle X} の元 y {\displaystyle y} の直前元 (direct predecessor) となる必要十分条件を満たす。
有向グラフは、あるユーザーが別の人をフォローするTwitter等の情報ネットワークを図に表すことができる。
とりわけ正則的な有向グラフの例としては、有限生成群のケイリーグラフやシュライアーコセットグラフなどが挙げられる。
圏論では、全ての小さい圏が台有向多重グラフ (underlying directed multigraph) を持っており、そこでの頂点は元の圏の対象、辺は元の圏の矢印である。圏論の言葉では、それを小さい圏の圏から箙の圏への忘却関手 (forgetful functor) がある、と表現する。
辺は x {\displaystyle x} と y {\displaystyle y} を「結び」、 x {\displaystyle x} と y {\displaystyle y} に「接続する」と表現される。頂点は、グラフ内にあっても辺を持たない場合もある。辺 ( y , x ) {\displaystyle (y,x)} は ( x , y ) {\displaystyle (x,y)} の「逆向辺 (inverted edge)」と呼ばれる。「多重辺」は、上述の定義だと許されないが、同じ始点と終点を持つ辺が複数あるものを言う。
多重辺を許す条件のより一般的な意味で、有向グラフは以下によって構成される順序三つ組 G = ( V , E , φ ) {\displaystyle G=(V,E,\phi )} として定義される。
V {\displaystyle V} は、頂点の集合
E {\displaystyle E} は、辺(有向辺とも言う)の集合