離散グラフの基本

問題

下の図のようなグラフ$G$について、次の問いに答えよ。

$(1)\quad$ グラフ$G$の頂点の数と辺の数を求めよ。

$(2)\quad$ 各頂点の次数を求め、次数の合計を求めよ。

$(3)\quad$ グラフ$G$は連結グラフであるか答えよ。

解説

離散グラフ（グラフ理論）の基本について解説します。

離散グラフって、関数のグラフとは違うんですか？

いい質問だね！関数のグラフとはまったく違うものだよ。

離散グラフは「点」と「点をつなぐ線」でできた図形のことなんだ。

地図の駅と路線、SNSの人間関係など、つながりを表すときに使うよ。

それでは問題を解いていきましょう。

まずは図を見ながら、頂点と辺を数えてみよう。

頂点は$A, B, C, D, E$の$5$個です。

辺は$AB, AD, AE, BC, BE, CD, CE, DE$の$8$本です。

よって、頂点の数は$\underline{5}$、辺の数は$\underline{8}$となります。

辺を数えるときは、同じ辺を2回数えないように注意してね！

次数は、その頂点から出ている辺の本数を数えればいいよ。

各頂点について、接続している辺を確認します。

• 頂点$A$：辺$AB, AD, AE$の$3$本 $\Rightarrow \deg(A)=3$

• 頂点$B$：辺$AB, BC, BE$の$3$本 $\Rightarrow \deg(B)=3$

• 頂点$C$：辺$BC, CD, CE$の$3$本 $\Rightarrow \deg(C)=3$

• 頂点$D$：辺$AD, CD, DE$の$3$本 $\Rightarrow \deg(D)=3$

• 頂点$E$：辺$AE, BE, CE, DE$の$4$本 $\Rightarrow \deg(E)=4$

次数の合計は $3+3+3+3+4=\underline{16}$ です。

次数の合計が$16$で、辺の数が$8$本...ちょうど$2$倍ですね！

よく気づいたね！実はこれは偶然ではないんだ。

どんなグラフでも成り立つ重要な性質だよ。

この問題でも、次数の合計$16 = 2 \times 8$（辺の数）が確かに成り立っていますね。

連結かどうかは、どの頂点からどの頂点へも辺をたどって移動できるかを確認すればいいよ。

頂点$E$はすべての他の頂点（$A, B, C, D$）と辺で直接つながっています。

したがって、任意の$2$頂点間は少なくとも頂点$E$を経由して移動できます。

例えば$A$から$C$へは、$A \to E \to C$ と移動できます（直接つながっていなくても、辺をたどれればOKです）。

よって、グラフ$G$は$\underline{\text{連結グラフである}}$。

すべての頂点が直接つながっていなくても、間接的にたどれれば連結なんですね！

その通り！逆に、辺をたどってもたどり着けない頂点のペアが$1$つでもあれば、連結ではないよ。

そのようなグラフを$\textcolor{red}{\text{非連結グラフ}}$と呼ぶんだ。

ここでは離散グラフ（グラフ理論）の基本的な用語と性質について学習しました。

頂点・辺・次数という基本概念と、握手補題（次数の合計＝辺の数の$2$倍）を押さえておきましょう。

グラフ理論はネットワークや経路問題など、様々な場面で応用される分野です。ぜひ基本をマスターしてくださいね！