読み方：むこうグラフ

無向グラフ【undirected graph】

無向グラフとは？

点とそれらを結ぶ線からなるグラフ構造のうち、各線に向きが定められていないもの。結び付けられた二つの点の間に方向の区別がなく、どちらから見ても同じ関係として扱う。

グラフ理論では、複数の頂点（ノード）を辺（エッジ）で繋いだ構造について考察する。無向グラフでは辺に向きがなく、頂点Aと頂点Bを結ぶ辺は、「AからBへの関係」と「BからAへの関係」を区別せず一つの接続として扱う。

相互関係や対称的な繋がりを記述する際に利用され、友人関係、道路網、通信網の物理接続など、双方向のやり取りや往来が前提となる対象の表現に適している。ある頂点に接続する辺の本数を「次数」と呼び、ネットワーク内の接続の多さを表す指標として用いられる。

無向グラフでは、頂点から別の頂点へ辺をたどって到達できるかどうかにより「連結性」が定義される。任意の二頂点間に経路が存在する場合、そのグラフは「連結である」と呼ばれ、複数のまとまりに分かれる場合はそれぞれ「連結成分」として区別される。すべての頂点同士が直接辺で結ばれているものは「完全グラフ」という。

2つのノード間に複数の辺がある場合を「多重辺」と呼び、これらを許容しないグラフを「単純グラフ」という。ある頂点から出発して同じ頂点に戻ってくる循環的な経路（閉路）を含まない連結な無向グラフは「木構造」（ツリー）と呼ばれ、階層的な構造の表現に適している。辺の数を最小限に抑えて全頂点を接続する「最小全域木」などのバリエーションがある。

無向グラフは電力網や鉄道路線のようなネットワーク構造の表現に広く応用されており、地図上での経路探索、化学における分子構造の記述などに用いられる。経路探索では、二点間の最短距離を求める問題がしばしば登場し、「幅優先探索」や「深さ優先探索」といったアルゴリズムで解かれる。