グラフ理論（グラフりろん、）は、ノード（節点・頂点）の集合とエッジ（枝・辺）の集合で構成されるグラフに関する数学の理論である。グラフ (データ構造) などの応用がある。グラフによって、様々なものの関連を表すことができる。例えば、鉄道や路線バス等の路線図を考える際には、駅（ノード）がどのように路線（エッジ）で結ばれているかが問題となる。線路が具体的にどのような曲線を描いているかは本質的な問題とならないことが多い。したがって、路線図では駅間の距離や微妙な配置、路線の形状などがしばしば地理上の実際とは異なって描かれている。路線図の利用者にとっては、駅と駅の「つながり方」が主に重要な情報なのである。このように、「つながり方」に着目して抽象化された「点とそれらをむすぶ線」の概念がグラフであり、グラフがもつ様々な性質を探求するのがグラフ理論である。つながり方だけではなく「どちらからどちらにつながっているか」をも問題にする場合、エッジに矢印をつける。このようなグラフを有向グラフまたは、ダイグラフという。矢印のないグラフは、無向グラフという。日常的な問題や工学的問題の多くをグラフとして考えることができる。グラフ理論は、1736年に「ケーニヒスベルクの問題」と呼ばれるパズルに対してオイラーが解法を示したのが起源のひとつとされる。この問題は、一筆書きと深く関連している。集合 "V" , "E" と、"E" の元（げん、要素）に、二つの "V" を元の対で対応させる写像の三つ組を有向グラフという。"V" の元を "G" の頂点またはノード、"E" の元を "G" の辺または弧と呼ぶ。P("V") を "V" の冪集合とする。"E" の元に "V" の 部分集合を対応させる写像があって、"E" の任意の元 "e" の像が "g"("e") = {"v

出典:wikipedia