また、根つき木に関する用語として、他に以下のようなものがある。有向木.グラフ理論グラフ理論(グラフりろん、)は、ノード(節点・頂点、点)の集合とエッジ(枝・辺、線)の集合で構成されるグラフに関する数学の理論である。グラフ(データ構造)などの応用がある。概要.グラフによって、様々なものの関連を表すことができる。例えば、鉄道や路線バス等の路線図を考える際には、駅(節点)がどのように路線(辺)で結ばれているかが問題となる一方、線路が具体的にどのような曲線を描いているかは本質的な問題とならないことが多い。したがって、路線図では駅間の距離や微妙な配置、路線の形状などがしばしば地理上の実際とは異なって描かれている。つまり、路線図の利用者にとっては、駅と駅の「つながり方」が主に重要な情報なのである。このように、「つながり方」に着目して抽象化された「点とそれらをむすぶ線」の概念がグラフであり、グラフがもつ様々な性質を探求するのがグラフ理論である。つながり方だけではなく「どちらからどちらにつながっているか」をも問題にする場合、エッジに矢印をつける。このようなグラフを有向グラフ、または、ダイグラフという。矢印のないグラフは、無向グラフという。グラフを表現するのに、図ではなく、隣接行列を用いることがある。無向グラフの隣接行列は、対称行列になる。例えば、上のグラフは、次の隣接行列で表現できる。グラフの例.日常的な問題や工学的問題の多くをグラフとして考えることができる。起源.形式的な定義.有向グラフ.集合,と、の元(げん、要素)に、二つのを元の対で対応させる写像の三つ組を有向グラフという。の元をの頂点またはノード、の元をの辺または弧と呼ぶ。となるはループに対応し、となるは多重辺に対応する。無向グラフ.をの冪集合とする。の元にの部分集合を対応させる写像用語.以下では単にグラフといった時には無向グラフを指す。頂点と辺.頂点の集合は、辺の集合はで表す。グラフが先に与えられている場合には、頂点集合を、辺集合をと表すこともある。数学以外の分野では、頂点を節点、辺を枝と呼ぶことが多い。辺を弧やリンクと呼ぶこともある。重み付きグラフ.