は頂点(vertex)の空でない有限集合
と辺(edge)の
集合
からなる．辺が頂点の順序対
で与えられる場合，そのグラフは
有向(directed)グラフと呼ばれる．
はの始点(head)，
は
終点(tail)と呼ばれる．辺が互いに異なる頂点である非順序対のグラ
フは無向(undirected)グラフと呼ばれる．辺が互いに異なるということ
から
は有向グラフではあるが，無向グラフの辺ではあり得ない．
有向グラフにおいてがに含まれるならば頂点は頂点
に隣接（adjacent)するという．頂点に隣接する頂点の個数をの
次数（degree)という．