グラフ理論
グラフ理論は、1736年に「ケーニヒスベルクの問題」と呼ばれるパズルに対してオイラーが解法を示したのが起源のひとつとされる。この問題は、一筆書きと深く関連している。
グラフの辺に重み(コスト)が付いているグラフを、重み付きグラフと呼ぶ。乗換案内図の場合、駅間の所要時間が「重み」にあたる。重み付きグラフはネットワークとも呼ばれる(フローネットワーク, ベイジアンネットワーク, ニューラルネットワークなど)。
2022年から日本で導入される高等学校新学習指導要領の数学C(公式配布されるのは2024年4月)には「図、表、統計グラフ、離散グラフ及び行列などを用いて、日常の事象や社会の事象などを数学的に表現し、考察すること」とあり、日本では初めてグラフ理論にかかわる分野が高等学校の数学教科書に掲載される予定である。ただし、その分野を入試に出題する大学は殆どない。
集合 V , E と、E の元(げん、要素)に、二つの V を元の対で対応させる写像
f : E → V × V {\displaystyle f\colon \ E\to V\times V}
の三つ組
G := ( f , V , E ) {\displaystyle G:=(f,V,E)}
を有向グラフという。V の元を G の頂点またはノード、E の元を G の辺または弧と呼ぶ。f(e)=(v, v)となるe∈Eはループに対応し、f(a)=f(b)となるa,b∈Eは多重辺に対応する。