無向グラフとは？むこうぐらふ
無向グラフとは、辺に向きがなく、辺でつながれた2つの頂点の関係が対等であるグラフ。頂点Aから頂点Bへ行けるなら必ずBからAへも行ける。友人関係や道路網のように往復できるつながりを表すのに使い、隣接行列（頂点どうしが辺でつながっていれば1、いなければ0を並べた表）で表すと対角線を挟んで対称な行列になり、辺1本が行列の2か所に現れる。
最終更新：2026-10-09
この語が出る過去問を解く →背景
ものごとのつながりには、片方向にしか進めないものと、どちらからでも通れるものがある。作業の前後関係や一方通行の道は向きを持つが、通信ケーブルでつながれた機器同士や共通の科目を履修した学生同士は向きを持たない。両者を同じ表現で扱うと誤った経路を数えてしまうため、辺に向きを持たせるかどうかで型を分けている。
具体例
ネットワークの配線図は、ケーブルにどちら向きという区別がないので無向グラフとして扱い、全機器をつなぐ総ケーブル長が最小になる配線を計算するのにも使われる。カーナビの一方通行を含む道路網は、向きのある有向グラフとして扱う。
試験での引っ掛け
次数（1つの頂点につながる辺の本数）の合計は辺の数の2倍になる。1本の辺が両端それぞれの次数に数えられるためで、辺の数と取り違えないこと。頂点数nの完全無向グラフ（すべての頂点の組が辺で結ばれたグラフ）の辺の数はn(n−1)/2本であり、有向グラフのn(n−1)本と混同しやすい。
関連用語
出た過去問
出典：令和元年度 秋期 基本情報技術者試験 午前 問3（IPA）
ノードとノードの間のエッジの有無を、隣接行列を用いて表す。ある無向グラフの隣接行列が次の場合、グラフで表現したものはどれか。ここで、ノードを隣接行列の行と列に対…
正解：ノードをa,b,c,d,[すき間]e,fの順に並べ、直線でa-b、b-c、c-d、e-fを結び、さらに弧でc-e（dの上を通る）とb-d（cの下を通る）を結んだグラフ
要点：隣接行列の1の位置＝辺。次数を数えて図と照合する
無向グラフの隣接行列は対称行列になり、値が1のマス（行,列）の組がそのまま辺を表す。この行列で1が立っているのは a-b、b-c、b-d、c-d、c-e、e-f の6組であり、辺の数は6本、各頂点の次数は a=1、b=3、c=3、d=2、e=2、f=1 となる。この6本の辺をすべて過不足なく備えた図が正解であり、次数の分布（次数1の頂点が a と f の2つだけ）を数えるだけでも絞り込める。
出典：令和6年度 公開問題 基本情報技術者試験 科目B 問3（IPA）
次のプログラム中の に入れる正しい答えを、解答群の中から選べ。ここで、配列の要素番号は1から始まる。 図1に示すグラフの頂点には、1から順に整数で番号が付けられ…
正解：adjMatrix[u, v] ← 1 adjMatrix[v, u] ← 1
要点：無向グラフの隣接行列は対称。両方向の成分を1にする
隣接行列では、頂点uと頂点vを結ぶ辺があるときにu行v列を1にする。無向グラフなので辺に向きはなく、行列は対称になるためv行u列も同時に1にしなければならない。片方だけでは対称行列にならず、図2の隣接行列を再現できない。
出典・参考
公式シラバスの1 基礎理論 ＞ 2. 応用数学 ＞ (5) グラフ理論に掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。