グラフ (離散数学)
「有向木 (polytree, directed tree, oriented tree, singly connected network)」とは、有向グラフの一種であって、その有向辺をすべて無向辺に置き換えたものが木グラフになるような有向非巡回グラフである。
同様に、「有向森」は、その有向辺をすべて無向辺に置き換えたものが森グラフになるような有向非巡回グラフである。
グラフ(有向グラフと区別して「無向グラフ」とか、多重グラフと区別して「単純グラフ」とも呼ばれたりもする)とは順序対 G = (V, E) である。ここで V は頂点 (vertex) と呼ばれる元の集合、E は頂点の対の集合でありその元は辺 (edge) と呼ばれる。
辺 {x, y} に含まれる頂点 xとy は、その辺の「端点」と呼ばれる。辺は頂点 x と y を「結び (join)」、x や y に「接続する (incident)」と言い表す。頂点がいかなる辺にも含まれないこともあり、その場合は他のどの頂点とも結ばれていない。
頂点をそれ自身と結ぶ辺である「ループ(自己ループとも)」を許すグラフもある。このように一般化されたグラフは「ループ付きグラフ (graphs with loops)」と呼ばれる。文脈からループを許すことが自明な場合は単にグラフと呼んだりもする。
「多重グラフ (multigraph) 」とは、2つの頂点間に複数の辺がある「多重辺」を許すように一般化したグラフである。一部のテキストでは、多重グラフのことを単にグラフと呼んでいたりもする。多重辺を許すにあたり、上述の辺に関する定義を頂点対の(通常の)集合ではなく、頂点対の多重集合に変更する必要がある。