グラフ理論

Graph Theory

ぐらふりろん

頂点（ノード）と辺（エッジ）からなるグラフ構造を扱う数学分野。無向グラフ、有向グラフ、重みつきグラフ、完全グラフなどの種類があり、ネットワーク設計、最短経路問題、スケジューリングなどに応用される。

基礎理論 > 応用数学

関連キーワードの用語

2つの集合A、Bの少なくとも一方に属する要素全体からなる集合。A∪Bと表記し、ベン図では両方の円を合わせた領域に相当する。論理和（OR）に対応し、要素数は|A∪B|=|A|+|B|-|A∩B|で求められる。

2つの集合A、Bの両方に属する要素全体からなる集合。A∩Bと表記し、ベン図では両方の円が重なる領域に相当する。論理積（AND）に対応する。

全体集合Uに対して、集合Aに属さない要素全体からなる集合。A̅またはA^cと表記する。論理否定（NOT）に対応し、ド・モルガンの法則により和集合・積集合の補集合を変換できる。

真または偽の値をとる命題と、否定・論理和・論理積・含意などの論理結合子で構成される論理体系。真理値表を用いて論理式の真偽を判定でき、デジタル回路設計やプログラムの条件式の基盤となる。

グラフや木構造を探索する際、可能な限り深い方向に進み、行き止まりになったら戻って別の枝を探索するアルゴリズム。スタック（再帰呼出し）を用いて実装される。迷路探索やトポロジカルソートに利用。

グラフや木構造を探索する際、始点から近い順に全隣接ノードを探索してから次の階層に進むアルゴリズム。キューを用いて実装される。重みなしグラフの最短経路探索に適しており、Web巡回やSNSの友達推薦に応用。