本ユニットでは、物事の「つながり」を表す離散数学の道具であるグラフ理論の基礎を学びます。グラフを形づくる頂点(ノード)と辺(エッジ)という2つの構成要素、そして辺に向きを持つ有向グラフと持たない無向グラフの違いを押さえます。経路や関係性をモデル化する基本概念として、応用数学分野で出題されます。
グラフ上で対象や地点を表す点。辺で結ばれる要素そのもの。
頂点は、グラフの中で「もの」や「場所」を表す点です。例えば路線図なら駅、人間関係図なら一人ひとりの人が頂点にあたります。 グラフは、この頂点と、頂点同士を結ぶ辺の2つで構成されます。頂点が対象そのものを表し、辺がそのつながりを表す、という役割分担が基本です。試験では、英語表記の「ノード」と同じ意味であること、辺との役割の違いを区別できることが問われます。
たとえ路線図にかかれた一つひとつの「駅」のようなもの。それ自体が地点を表し、線路(辺)でほかの駅と結ばれます。
記憶フック頂点といえばグラフ上の点(対象・地点)
頂点の英語表記(node)。グラフ上の点を指す同義語。
ノード(node)は、頂点の英語での呼び方で、意味は頂点とまったく同じです。グラフ上で対象や地点を表す点を指します。 IT の分野ではネットワークの機器やデータ構造の要素を「ノード」と呼ぶことも多く、文脈によって頂点・ノードが使い分けられます。試験では、頂点=ノードという和英の対応を覚えておけば十分で、両者は同じものを別の言葉で呼んでいるだけだと理解しておきましょう。
たとえ「駅」を英語で「ステーション」と呼ぶのと同じで、頂点を英語にしただけ。指しているものは同一です。
記憶フックノードといえば頂点の英語表記(同じ意味)
2つの頂点を結び、つながりや関係を表すグラフの線。
辺は、2つの頂点を結ぶ線で、それらの間に「つながり」や「関係」があることを表します。路線図なら駅と駅を結ぶ線路、人間関係図なら友人関係の線が辺にあたります。 グラフは頂点と辺の2要素からできており、辺は必ず頂点と頂点の間に引かれます。試験では、英語表記の「エッジ」と同じ意味であること、対象を表す頂点に対して辺は関係を表すという役割の違いが問われます。
たとえ駅と駅を結ぶ「線路」のようなもの。線路があれば2つの駅は行き来でき、つながっていることを示します。
記憶フック辺といえば頂点同士を結ぶつながりの線
辺の英語表記(edge)。頂点を結ぶ線を指す同義語。
エッジ(edge)は、辺の英語での呼び方で、意味は辺とまったく同じです。2つの頂点(ノード)を結び、関係やつながりを表します。 ノードとエッジという英語の組で語られることも多く、頂点と辺の和英対応とセットで覚えると整理しやすくなります。試験では、辺=エッジという対応を押さえておけばよく、両者は同じものを呼び分けているだけだと理解しておきましょう。
たとえ「線路」を英語で言い換えただけのようなもの。辺をエッジと呼んでも、結んでいる役割は変わりません。
記憶フックエッジといえば辺の英語表記(同じ意味)
辺に向き(矢印)があり、一方向のつながりを表すグラフ。
有向グラフは、辺に向きがあるグラフで、辺が矢印で描かれます。AからBへは行けてもBからAへは行けない、というように一方通行の関係を表せます。 一方通行の道路、Web ページ間のリンク、作業の前後関係などが有向グラフで表されます。試験では、向きのない無向グラフとの対比が頻出で、「矢印がある=有向」「行き来の方向が決まっている関係」を有向グラフと判断できることがポイントです。
たとえ一方通行の道路網のようなもの。「こちらからあちらへは行けるが逆は行けない」という向きのある道を矢印で表します。
記憶フック有向グラフといえば矢印付きの一方向のつながり
辺に向きがなく、双方向のつながりを表すグラフ。
無向グラフは、辺に向きがないグラフで、辺は単純な線で描かれます。AとBが結ばれていれば、AからBへもBからAへも行き来できる、双方向の関係を表します。 相互に通行できる道路、友人関係(互いに友達)などが無向グラフで表されます。試験では、向きのある有向グラフとの対比が頻出で、「矢印がない=無向」「行き来が両方向の対等な関係」を無向グラフと判断できることがポイントです。
たとえ対面通行の道路網のようなもの。「どちらからでも行き来できる」つながりを、向きのない線で表します。
記憶フック無向グラフといえば向きなしの双方向のつながり
関連の過去問演習は今後のアップデートで追加予定です。