グラフ理論の基礎

頂点 は、グラフの中で人・駅・コンピュータなどの対象や地点を表す 点 である。

グラフ とは、いくつかの頂点と、頂点どうしを結ぶ線 (辺) の組で物事のつながりを表した図である。頂点は「何がつながっているか」の「何」にあたり、丸や点で描かれる。どの頂点を選ぶかは表したい対象しだいで、同じ鉄道網でも駅を頂点にすることも、路線を頂点にすることもできる。

たとえ地図に打った待ち合わせ場所の印のようなもの。印そのものは場所を表すだけで、印の間をどう行くかは別の線が受け持つ。

覚え方図形の三角形で、辺と辺が出会う角の点を「頂点」と呼ぶのと同じ字。

この用語の過去問 1 題 頂点 →

ノード は、グラフの 頂点 を英語由来の呼び名で言ったもので、指すものは頂点と同じである。

IT の分野では、ネットワークにつながる機器や、木構造・リストなどのデータ構造の要素もノードと呼ぶ。どれも「つながりの端に置かれる要素」という点で、グラフの頂点と同じ役割を持つ。

覚え方英語の node はもともと「結び目」の意味。網の糸が交わる結び目を思い浮かべるとよい。

この用語の過去問 1 題 ノード →

辺 は、2 つの頂点を結び、その間に つながり や関係があることを表す線である。

辺の両端には必ず頂点があり、どの 2 つの頂点を結ぶかによって関係が決まる。辺には距離・時間・費用などの値を付けることがあり、この値を 重み という。重み付きの辺を使えば、ある地点から別の地点までの道のりを辺の値の合計として比べられる。

たとえ町と町を結ぶ道路のようなもの。道路があれば 2 つの町がつながり、道路ごとに所要時間を書き込んでおけば遠回りかどうかも分かる。

覚え方三角形の「辺」と同じ字で、角の点 (頂点) と角の点を結ぶ線と覚える。

この用語の過去問 1 題 辺 →

エッジ は、グラフの 辺 を英語由来の呼び名で言ったもので、指すものは辺と同じである。

頂点をノードと呼ぶ文脈では、辺もエッジと呼ぶことが多く、「ノードとエッジ」の組でグラフを説明する。ネットワークの分野では、機器 (ノード) の間をつなぐ回線や接続をエッジとみなすことがある。なお、エッジコンピューティングの「エッジ」は、ネットワークの末端 (利用者や機器に近い側) という別の意味である。

覚え方英語の edge は「へり・縁」の意味。図形の縁、つまり角と角を結ぶ線と結び付けて覚える。

この用語の過去問 1 題 エッジ →

有向グラフ は、辺に 向き があり、辺を矢印で描くグラフである。

← 図は横にスクロールできます →

矢印は根元の頂点から先の頂点へ向かう関係を表し、逆向きの関係は別の矢印がない限り成り立たない。作業の前後関係、Web ページのリンク、一方通行の道路網などが有向グラフで表される。

たとえ一方通行の標識がある道路網のようなもの。標識の向きにしか進めず、戻るには別の道が要る。

覚え方「有向」は文字どおり「向きが有る」。矢じりが付いているかどうかを見る。

この用語の過去問 1 題 有向グラフ →

無向グラフ は、辺に 向き がなく、辺を矢じりのない線で描くグラフである。

← 図は横にスクロールできます →

辺で結ばれた 2 つの頂点は対等で、どちらから見ても同じ関係が成り立つ。互いに知り合いである関係や、両方向に通れる道路網などが無向グラフで表される。

たとえ握手のようなもの。A が B と握手していれば、B も A と握手している。

覚え方「有向」と一字違いの「無向」。「無」は矢じりが無いと結び付ける。