AHL 3.14 — Graph theory（グラフ理論）

ノートWhat you should be able to do
  • 道路網・部屋・回路などの現実の構造を、自分で graph に直せる。何を vertex（頂点）にし、何を edge（辺）にするかを決められる。
  • adjacent（隣り合う）と degree（次数）を読み取り、degree の合計が edge の数の \(2\) 倍になる理由を言える。
  • unweighted / weighted、directed、simple、complete を見分けられる。
  • adjacent と connected（連結）のちがい、connected と strongly connected（強連結）のちがいを説明できる。
  • subgraph（部分グラフ）が何かを言える。
  • tree（木）かどうかを、connected であることと cycle がないことの \(2\) つで判定できる。

The idea

1. Modelling with graphs（現実の場面を点と線の図に直す）

graph theory（グラフ理論）は日本の高校では習わないので、まったく初めてで当たり前です。計算は足し算と数えることだけで、新しいのは言葉とその意味です。このページで言葉を決め、AHL 3.15 で行列を使った計算、AHL 3.16 で道と最適化の algorithm に進みます。公式集にはこの \(3\) ページの欄がありませんが、出てくる関係はどれも短く、理由から作り直せます。

この単元は、道路網や回路などの現実の場面を点と線に直すところから始まります。定義より先に、その作業を見てください。

図 1: 地図から重み付きグラフを作ります。

図 1 の左は地図です。町の位置、道路の曲がりぐあい、地図上の距離——いろいろな情報が入っています。

右は、同じ場面から「どの町とどの町が道でつながっているか」と「その距離」だけを取り出したものです。

重要捨てるのは位置、残すのは接続関係

地図では、町の位置に意味がありました。右の図には、その意味がありません。点をどこに置いても構いません。

残っているのは、つながり方（と、書き込まれた数）だけです。この「位置を捨てて、つながりだけを残した図」が graph（グラフ）です。

同じことは、地図以外でもできます。

表 1: 何を vertex にするか
現実のもの vertex にするもの edge にするもの
道路網 町・交差点 道路
部屋の配置 部屋 ドア・通路
電気回路 接続点 配線
航空路線 空港 路線
ウェブサイト ページ リンク（向きがあります）
ヒント「何を vertex にするか」を先に決めてください

文章題では、まずここで迷います。つながれる側が vertex、つなぐものが edge です。

道路の問題なら、道路そのものを vertex にしてはいけません。町が vertex です。

2. Graphs, vertices and edges（グラフ・頂点・辺）

言葉を決めます。graph は、vertex（頂点）と、それを結ぶ edge（辺）でできた図です。

図 2: グラフの各部分の呼び方です。

図 2 には vertex が \(5\) つ、edge が \(6\) 本あります。vertex の複数形は vertices です。

警告「グラフ」でも、\(y = f(x)\) のグラフとは別のものです

日本語でも英語でも、同じ graph という言葉を使います。関数のグラフとは、まったく別のものです。

この項目の graph には、軸も座標もありません。あるのは「点」と「つながり」だけです。

第1節で位置を捨てたので、同じ graph を、いくらでも違う形に描けます。

図 3: 同じグラフを、\(2\) 通りに描いたものです。

図 3 の \(2\) つは、見た目がまるで違いますが、同じ graph です。vertex の名前も、どれとどれが結ばれているかも、まったく同じだからです。

線の長さも、曲がっているかどうかも、関係ありません。

3. Crossing edges（線の交差は頂点ではない）

線が交差しても、そこは vertex ではありません。図を描き直していると、線どうしが交わることがあります。

図 4: 線の交点は頂点ではありません。

図 4 の左では、\(AD\) と \(BC\) が真ん中で交わっています。その交点は vertex ではありません。

vertex は、丸が描いてあるところだけです。交点に丸がなければ、そこは「たまたま紙の上で線が重なった場所」にすぎません。

右は、まったく同じ graph を、交差しないように描き直したものです。vertex は \(4\) つ、edge は \(4\) 本——左と同じです。

警告交点を数えて、vertex が \(5\) つと答えない

左の図を見て「vertex は \(5\) つ」と書いてしまうのが、この項目のいちばん最初の誤りです。

丸の数を数えてください。 交差は、描き方の都合で出たり消えたりします。

4. Adjacent vertices and edges（隣り合う頂点と辺）

言葉を \(2\) つ入れます。どちらも「\(1\) 本の edge を共有している」という意味です。

  • \(2\) つの vertex が edge \(1\) 本で直接結ばれているとき、その \(2\) つは adjacent vertices（隣接する頂点）といいます
  • \(2\) 本の edge が同じ vertex を共有しているとき、その \(2\) 本は adjacent edges（隣接する辺）といいます

図 2 では、\(A\) と \(B\) は adjacent です。\(A\) と \(E\) は、直接結ばれていないので adjacent ではありません。

Write down the vertices adjacent to \(B\). と問われたら、\(B\) から edge が \(1\) 本で届く先を全部書きます。

5. Degree（次数）

degree（次数）\(\deg(v)\) は、その vertex に付いている edge の「端」の数です。

図 5: 各頂点の次数です。

図 5 で、\(B\) に付いているのは \(BA\)、\(BC\)、\(BD\) の \(3\) 本なので \(\deg(B) = 3\) です。\(E\) には \(1\) 本しか付いていないので \(\deg(E) = 1\) です。

「出ている edge の本数」と言っても、ふつうは同じことになります。ただし、\(1\) か所だけ違う場面があります。

重要loop は、degree に \(2\) と数えます

loop（自己ループ）は、同じ vertex にもどってくる edge です。この edge は、両方の端が同じ vertex に付いています。

ですから、loop \(1\) 本は degree に \(2\) を足します。\(1\) ではありません。

図 6: loop は次数に \(2\) を足します。

図 6 の左では、\(P\) に \(PQ\) と \(PR\) の \(2\) 本が付いていて \(\deg(P) = 2\) です。右で loop を \(1\) 本足すと、その \(1\) 本が赤い点の \(2\) か所で \(P\) に付きます。 ですから端の数は \(2\) 増えて、\(\deg(P) = 4\) になります。

「edge の本数」ではなく「端の数」と覚えておくと、ここで迷いません。

ノートdegree の値だけで、edge の本数は決まりません

\(\deg(v) = 4\) と分かっても、\(v\) に付いている edge が \(4\) 本とはかぎりません。loop が \(1\) 本あれば、edge は \(3\) 本です。

試験に出る graph の多くは loop のない simple graph（第8節）なので、ふだんは気にせずに済みます。loop が描いてあるときだけ、ここに戻ってきてください。

6. The sum of the degrees（次数の合計）

graph のすべての vertex の degree を足すと、edge の数の \(2\) 倍になります。図 5 の degree を全部足すと \(2+3+3+3+1 = 12\) で、edge の数 \(6\) のちょうど \(2\) 倍です。これはいつでも成り立ちます。

\[ \sum \deg(v) = 2 \times (\text{number of edges}) \tag{1}\]

覚えるものではありません。 理由が \(1\) 行だからです。

\(1\) 本の edge には、端が \(2\) つある。

degree は「端の数」でした（第5節）。ですから、graph 全体の degree を足すということは、全部の edge の端を数えていることになります。edge が \(6\) 本なら端は \(12\) 個、それが合計です。

loop も、この \(1\) 行にそのまま従います。loop の \(2\) つの端は同じ vertex に付いているので、その vertex の degree に \(2\) を足します。

ヒント数え忘れの検算に使えます

degree を全部書き出したあと、合計が edge の数の \(2\) 倍になっているかを見てください。合わなければ、どこかで数え落としています。

degree の合計は、必ず偶数です。 奇数になったら、その時点で間違いです。

7. Unweighted and weighted graphs（重みなしグラフと重み付きグラフ）

ここまでの graph は、edge に何も書いてありませんでした。これを unweighted graph（重みなしグラフ）といいます。

図 7: 重みなしグラフと重み付きグラフです。

weighted graph（重み付きグラフ）は、edge \(1\) 本ずつに数が書き込まれた graph です。その数を weight（重み）といいます。

\(2\) つの違いは、答えられる問いの種類です。

表 2: unweighted と weighted
書いてあるもの 答えられる問い
unweighted つながっているかどうかだけ 行けるか。何本の edge を通るか
weighted それに加えて、各 edge の数 どれだけかかるか。どれがいちばん短いか

weight は距離とはかぎりません。時間・費用・容量など、問題文が決めます。

警告weight の大小と、線の長さは無関係です

weight \(9\) の edge が、weight \(2\) の edge より短く描いてあることがあります。図の見た目ではなく、書かれた数を読んでください。

第1節で位置を捨てたので、線の長さには意味がありません。

ノートweight は、AHL 3.16 の主役です

AHL 3.16 の「最短の道」「いちばん軽くつなぐ」という問題は、すべて weighted graph の話です。

このページでは、足して比べられれば十分です。

8. Simple, complete and directed graphs（単純グラフ・完全グラフ・有向グラフ）

問題文でよく出る言い方を、あと \(3\) つ入れます。

図 8: グラフの種類です。
  • simple graph（単純グラフ）… loop も、multiple edge（多重辺。同じ \(2\) 点を結ぶ \(2\) 本以上の edge）もない graph
  • complete graph（完全グラフ）… どの \(2\) つの vertex も edge で結ばれている graph。vertex が \(n\) 個のものを \(K_n\) と書きます

図 8 のいちばん右には、第7節の weighted graph も並べてあります。\(3\) つ目の directed graph は、このあとの見出しで扱います。

complete graph の edge の数

\(K_n\) では、\(n\) 個から \(2\) 個を選ぶ組み合わせの数だけ edge があります。

\[ \text{number of edges of } K_n = \frac{n(n-1)}{2} \tag{2}\]

これも、理由のほうが短いものです。\(1\) つの vertex から \(n-1\) 本ずつ出ているので、端は全部で \(n(n-1)\) 個。式 1 より、edge はその半分です。

検算。 図 8 の \(K_5\) なら \(\dfrac{5 \times 4}{2} = 10\) 本 ✓

電卓の nCr(n, 2) でも同じ値が出ます。\(\dfrac{n(n-1)}{2}\) が「\(n\) 個から \(2\) 個を選ぶ組み合わせ」の式だからです。

directed graph

edge に矢印が付いたものを directed graph（有向グラフ）といいます。一方通行の道路や、\(1\) 方向だけのリンクを表すのに使います。

矢印の付いていない、ここまで見てきたほうの graph は undirected graph（無向グラフ）です。このサイトでは、以降どちらも英語のまま書きます。

図 9: 入次数と出次数です。

矢印が入ってくる本数を in degree（入次数）、出ていく本数を out degree（出次数）といいます。

図 9 の \(D\) には \(C\) と \(B\) から \(2\) 本入り、\(A\) へ \(1\) 本出ているので、in degree \(= 2\)、out degree \(= 1\) です。

in degree の合計も、out degree の合計も、矢印の本数と同じになります。どちらも \(5\) です。\(1\) 本の矢印は、どこかから \(1\) 回出て、どこかへ \(1\) 回入るからです。

警告矢印があるかどうかを、先に見てください

directed graph では、\(A\) から \(B\) へ行けても、\(B\) から \(A\) へ行けるとはかぎりません。

問題文に directed があるか、図に矢印が付いているか。そこを見てから数え始めてください。

例題 1 The graph \(G\) is shown below.

(a) Write down the number of edges of \(G\).

(b) Write down the degree of each vertex, and verify that the sum of the degrees is twice the number of edges.

(c) Explain why \(G\) is a simple graph.

(a) 数えます。\(AB\)、\(AC\)、\(BC\)、\(BD\)、\(CD\)、\(CE\)、\(DE\) の \(7\) 本です。

数え落としが出やすいところなので、\(A\) に付いているもの、\(B\) に付いているもの、と順番に拾ってください。

(b) それぞれの vertex に付いている端の数です（第5節）。

vertex \(A\) \(B\) \(C\) \(D\) \(E\)
\(\deg\) \(2\) \(3\) \(4\) \(3\) \(2\)

\[ 2 + 3 + 4 + 3 + 2 = 14 = 2 \times 7 \]

式 1 のとおりになっています。

(c) simple graph の条件は \(2\) つでした（第8節）。loop がないこと、multiple edge がないことです。

試験ではこう書く

\(G\) is simple because no edge joins a vertex to itself (no loops), and no two vertices are joined by more than one edge (no multiple edges).

（自分自身にもどる edge がなく、同じ \(2\) 点を結ぶ edge が \(2\) 本以上ないから、という意味です。）

ノート解答例（答案用紙にはこう書く）

(a) \(7\)

(b) \[ \deg(A)=2,\quad \deg(B)=3,\quad \deg(C)=4 \] \[ \deg(D)=3,\quad \deg(E)=2 \] \[ 2+3+4+3+2 = 14 = 2 \times 7 \quad ✓ \]

(c) There are no loops and no multiple edges, so \(G\) is simple.

例題 2 A complete graph has \(45\) edges.

(a) Find the number of vertices.

(b) Write down the degree of each vertex.

(a) complete graph の edge の数は \(\dfrac{n(n-1)}{2}\) でした。これを \(45\) とおきます。

\[ \frac{n(n-1)}{2} = 45 \]

\[ n(n-1) = 90 \quad \Rightarrow \quad n^{2} - n - 90 = 0 \]

電卓の Polynomial Root Finder（SL 1.8）に入れると \(n = 10\) と \(n = -9\) が出ます。

vertex の数は負になりません。 \(n = -9\) は捨てて、理由を一言書いてください。

\[ n = 10 \]

検算。 \(\dfrac{10 \times 9}{2} = 45\) ✓

(b) complete graph では、\(1\) つの vertex が自分以外の全部と結ばれています。

\[ \deg = 10 - 1 = 9 \]

検算。 \(10 \times 9 = 90 = 2 \times 45\) ✓（式 1）

ノート解答例（答案用紙にはこう書く）

(a) \[ \frac{n(n-1)}{2} = 45 \quad \Rightarrow \quad n^{2} - n - 90 = 0 \] \[ n = 10 \ \text{or} \ n = -9 \]

\(n\) must be positive, so there are \(10\) vertices.

(b) \(\deg = 9\)

例題 3 The weighted graph below shows the roads between five delivery points. The weights are distances in kilometres.

(a) Write down the degree of vertex \(L\).

(b) Explain why this graph is not complete.

(c) Find the total distance of the route \(H \to S \to P \to M\).

(d) Write down the vertices that are adjacent to \(S\).

(a) \(L\) に付いている edge は \(LH\)、\(LS\)、\(LM\) の \(3\) 本です。\(\deg(L) = 3\)

(b) complete graph は、どの \(2\) 点も結ばれている graph でした。

vertex が \(5\) つなので、complete なら edge は \(\dfrac{5 \times 4}{2} = 10\) 本必要です。この図には \(6\) 本しかありません。

具体例を \(1\) つ挙げるほうが、答案としては強くなります。\(H\) と \(P\) を結ぶ edge がありません。

試験ではこう書く

The graph is not complete because not every pair of vertices is joined by an edge: for example, there is no edge between \(H\) and \(P\).

A complete graph on \(5\) vertices would have \(10\) edges, but this graph has only \(6\).

（すべての組が結ばれてはいないから、という意味です。\(H\) と \(P\) の例と、\(10\) 本と \(6\) 本の対比を添えています。）

(c) 通る edge の weight を足すだけです。

\[ 6 + 7 + 5 = 18 \ \text{km} \]

(d) adjacent は「edge \(1\) 本で直接結ばれている」でした（第4節）。\(S\) から edge が \(1\) 本で届く先を全部書きます。

\[ H,\ L,\ P \]

\(M\) は、\(S \to P \to M\) と乗りつげば行けますが、adjacent ではありません（第9節）。

ノート解答例（答案用紙にはこう書く）

(a) \(\deg(L) = 3\)

(b) Not every pair of vertices is joined: for example, \(H\) and \(P\) are not adjacent. A complete graph on \(5\) vertices has \(10\) edges, but this one has \(6\).

(c) \[ 6 + 7 + 5 = 18 \ \text{km} \]

(d) \(H\), \(L\), \(P\)

9. Adjacent and connected（隣接と連結）

adjacent と connected は似ていますが、指しているものが違います。

図 10: 隣接と連結の違いです。
  • adjacent … edge \(1\) 本で直接結ばれている（第4節）
  • connected（連結）… edge を何本か乗りついで行き来できる

図 10 で、\(A\) と \(B\) は adjacent です。\(A\) と \(D\) は adjacent ではありませんが、\(A \to B \to C \to D\) と乗りついで行けるので connected です。

graph 全体について connected と言うときは、どの \(2\) つの vertex のあいだにも、乗りついで行ける道があるという意味です。

図 11: 連結と強連結の違いです。

図 11 の真ん中は、左半分と右半分のあいだに edge が \(1\) 本もないので、connected ではありません。

警告「\(A\) と \(D\) は結ばれていないから connected ではない」としない

それは adjacent でないというだけです。connected は、乗りついでよいのです。

connected と問われたら、行ける道を \(1\) つ書いて示してください。

10. Strongly connected graphs（強連結なグラフ）

directed graph では、もう \(1\) 段きびしい言い方があります。strongly connected（強連結）は、どの \(2\) つの vertex についても、矢印の向きに従って行き来できるという意味です。

\(A\) から \(B\) へ行けるだけでは足りません。\(B\) から \(A\) へも行けなければなりません。

ヒント一方通行の街だと思ってください

strongly connected は、「どの交差点からどの交差点へも、一方通行の標識を守ったまま行ける」という意味です。

矢印を全部無視すれば connected なのに、向きを守ると行けない場所ができる——これが strongly connected でない graph です。この区別は、AHL 3.15 の transition matrix で必要になります。

例題 4 The directed graph \(D\) is shown below.

(a) Write down the in degree and the out degree of each vertex.

(b) Determine whether \(D\) is strongly connected, justifying your answer.

(a) 矢印を \(1\) 本ずつ見て、入るほうと出るほうに分けて数えます。

vertex \(P\) \(Q\) \(R\) \(S\) \(T\)
in degree \(2\) \(1\) \(1\) \(2\) \(1\)
out degree \(1\) \(2\) \(2\) \(1\) \(1\)

検算。 矢印は \(7\) 本で、in の合計も out の合計も \(7\) です ✓（第8節）

(b) 「どの vertex からどの vertex へも、矢印の向きどおりに行けるか」を見ます。

\(1\) 組ずつ調べると \(20\) 通りになって大変です。全部の vertex を通る一方通行の輪が \(1\) つ見つかれば、それで足ります。

\[ P \to Q \to R \to S \to T \to P \]

この輪をぐるぐる回れば、どの vertex からでも、どの vertex にも行けます。

justifying your answer と書かれているので、この輪を示すところまでが解答です。「はい」だけでは点になりません。

試験ではこう書く

Yes.

The directed cycle \(P \to Q \to R \to S \to T \to P\) passes through every vertex, so from any vertex we can reach any other by following this cycle.

Hence \(D\) is strongly connected.

（すべての vertex を通る有向の輪があるので、どの vertex からもどの vertex へも行ける、という意味です。）

ノート解答例（答案用紙にはこう書く）

(a)

vertex \(P\) \(Q\) \(R\) \(S\) \(T\)
in \(2\) \(1\) \(1\) \(2\) \(1\)
out \(1\) \(2\) \(2\) \(1\) \(1\)

(b) Yes. \(P \to Q \to R \to S \to T \to P\) is a directed cycle through all five vertices, so every vertex can be reached from every other vertex. \(D\) is strongly connected.

11. Subgraphs（部分グラフ）

subgraph（部分グラフ）は、もとの graph から vertex をいくつか選び、edge をいくつか選んだものです。

条件は \(2\) つだけです。

  1. 新しい edge を足さない。 もとの graph にない結び方は、subgraph にも入りません。
  2. 選んだ edge の両端の vertex は、必ず選んでおく。 端のない edge は描けないからです。
図 12: 部分グラフと木です。
重要選んだ vertex のあいだの edge を、全部残す必要はありません

ここを取りちがえやすいところです。\(A\)、\(B\)、\(C\) を選んだからといって、\(AB\)、\(BC\)、\(AC\) を全部入れなければならないわけではありません。 \(AB\) と \(BC\) だけの subgraph も、正しい subgraph です。

いっぽう、選んだ vertex のあいだの edge をすべて残した subgraph には、induced subgraph（誘導部分グラフ）という名前が付いています。試験でこの語が使われることはまれですが、問題文が「これらの頂点のあいだの辺をすべて含む部分グラフ」と書いていたら、それのことです。

問題文が edge をどう指定しているかを、先に読んでください。

12. Trees（木）

tree（木）は、次の \(2\) つを両方みたす graph です。

  1. connected である（第9節）
  2. cycle（閉路。同じ vertex にもどってくる輪）がない

図 12 の右は tree です。\(5\) つの vertex が全部つながっていて、どこをたどっても同じ場所にもどってきません。その部分だけを取り出すと、こうなります。

図 13: 木の例です。

vertex が \(n\) 個の tree は、edge が \(n-1\) 本です

vertex が \(n\) 個の tree は、edge が必ず \(n - 1\) 本です。

\[ \text{a tree with } n \text{ vertices has } n - 1 \text{ edges} \tag{3}\]

\(1\) 本でも足すと cycle ができ、\(1\) 本でも減らすと切りはなされてしまいます。

警告「\(n\) 個と \(n-1\) 本だから tree」は、成り立ちません

これは逆が言えない関係です。\(n\) 個の vertex と \(n-1\) 本の edge があっても、tree でないことがあります。

図 14: 辺の本数を数えるだけでは、木かどうかは判定できません。

図 14 の左は、vertex が \(4\) 個、edge が \(3\) 本です。本数は合っています。しかし

  • \(A\)、\(B\)、\(C\) が輪になっている（cycle がある）
  • \(D\) がどこともつながっていない（connected でない）

ので、tree ではありません。

判定するときは、必ず \(2\) つとも確かめてください。 connected か。cycle がないか。本数を数えるのは、そのあとの検算です。

ノートtree はこのあと使います

AHL 3.16 の minimum spanning tree（最小全域木）は、「全部の vertex を、いちばん軽い重みでつなぐ tree」を探す問題です。

この項目では、言葉の意味と判定のしかただけ押さえておけば十分です。

なお、道のたどり方には walk、trail、path、circuit、cycle という \(5\) つの名前があり、それぞれ意味が違います。ここでは「cycle = もとの場所にもどってくる輪」という、いちばんゆるい理解で構いません。正式な区別は AHL 3.16 の第1節 でまとめて扱います。

Why it works

第6節で、degree の合計が edge の数の \(2\) 倍になる理由を見ました。ここでは、そこから出てくるもう \(1\) つの結論を見ておきます。あとで何度も使うものです。

degree が奇数の vertex は、必ず偶数個ある。

degree が奇数の vertex を odd vertex といいます。なぜ偶数個なのかを見ます。

vertex を、degree が偶数のものと奇数のものに分けます。

\[ \sum \deg(v) = \underbrace{(\text{even vertex の degree の和})}_{\text{偶数どうしの和なので偶数}} + (\text{odd vertex の degree の和}) \]

左辺は 式 1 より \(2 \times (\text{edge の数})\)、つまり偶数です。右辺の第 \(1\) 項も偶数です。

ですから、odd vertex の degree の和も偶数でなければなりません。

奇数を足して偶数になるのは、足した個数が偶数のときだけです（\(3+5 = 8\) は偶数、\(3+5+7 = 15\) は奇数）。したがって、odd vertex の個数は偶数です。

この関係は、英語では handshake lemma（握手の補題）と呼ばれます。「\(1\) 回の握手には手が \(2\) つ要る」からです。試験でこの名前が問われることはありません。

この結論は、AHL 3.16 の Eulerian の判定でそのまま使います。odd vertex の個数が \(0\)、\(2\)、\(4\)、… しかありえないから、判定表に「\(1\) 個のとき」という行が無いのです。

Common errors

警告線が交差したところを、vertex として数える

交点に丸がなければ、そこは vertex ではありません（第3節）。丸の数を数えてください。

同じ graph でも、描き方を変えれば交差は消えます。

警告図の見た目で「別のグラフ」と判断する

線が長いか短いか、曲がっているかどうかで、違う graph だと考えてしまう誤りです。

同じ vertex どうしが結ばれていれば、同じ graph です（図 3）。見るのは「つながりの表」であって、絵ではありません。

警告loop を degree に \(1\) と数える

loop は両端が同じ vertex に付いているので、degree に \(2\) を足します（第5節）。

loop が \(1\) 本だけなら、\(1\) と数えたときに degree の合計が奇数になるので、そこで気づけます。ただし loop が \(2\) 本あると合計は偶数のままで、気づけません。loop を見つけたら、その場で \(2\) と書いてください。

警告degree の合計が奇数になる

式 1 より、degree の合計は必ず偶数です。

奇数が出たら、数え間違いです。もう一度、\(1\) つの vertex ずつ数え直してください。

警告complete graph の edge の数を \(n(n-1)\) とする

\(2\) で割るのを忘れる誤りです。

\(n(n-1)\) は端の数であって、edge の数ではありません。\(A\) と \(B\) を結ぶ edge は \(1\) 本で、「\(A\) から \(B\)」と「\(B\) から \(A\)」を別に数えてはいけません。

警告directed graph で、in と out を分けずに数える

矢印付きの図で \(\deg = 3\) とだけ書いてしまう誤りです。

directed graph では、聞かれているのは in degree と out degree です。\(2\) つに分けて書いてください。

警告adjacent と connected を混同する

adjacent は edge \(1\) 本で直接、connected は乗りついでよい、でした（第9節）。

adjacent と聞かれて乗りついだ先まで書くと、余分なものが入ります。逆に connected と聞かれて「直接つながっていないから」と答えると、意味が変わってしまいます。

警告connected と strongly connected を混同する

strongly connected は directed graph だけの言葉です。矢印のない graph に使ってはいけません。

逆に、矢印のある graph に connected とだけ答えると、向きを見ていないと判断されます。問題文にどちらが書かれているかを見てください。

警告strongly connected の理由を「図を見れば分かる」で済ませる

justify や explain が付いた設問では、行き来できることを示す道を書く必要があります。

例 4 のように、全部の vertex を通る有向の輪を \(1\) つ書くのが、いちばん短い答え方です。

警告subgraph に、もとの graph にない edge を足す

subgraph は「選ぶ」だけです。新しく結ぶことはできません（第11節）。

選んだ vertex どうしでも、もとの graph で結ばれていなければ、subgraph でも結べません。

警告「\(n\) 個の vertex と \(n-1\) 本の edge」だけで tree と判定する

本数が合っていても、cycle があったり、切りはなされた vertex があったりします（図 14）。

判定は、connected かとcycle がないかの \(2\) つです（第12節）。本数は、そのあとの検算に使ってください。

Using your GDC (TI-Nspire CX II)

この項目は、電卓よりも紙と鉛筆の項目です。 図を読んで数える作業が中心なので、電卓の出番は多くありません。

とはいえ、\(3\) つだけ使い道があります。

1. Number of edges of a complete graph（完全グラフの辺の数）

complete graph の edge の数 \(\dfrac{n(n-1)}{2}\) は、組み合わせの nCr で出せます。

nCr(12, 2)

\(66\) と返ります。\(K_{12}\) の edge の数です。手で \(\dfrac{12 \times 11}{2}\) と計算しても同じですが、桁が大きいときはこちらが速いです。

2. Finding the number of vertices（辺の数から頂点の数を求める）

逆に、edge の数から vertex の数を出すこともできます。例 2 のように \(\dfrac{n(n-1)}{2} = 45\) を解くときは、\(2\) 次方程式なので Polynomial Root Finder が使えます。

menu → Algebra → Polynomial Tools → Find Roots of Polynomial

Degree の欄に \(2\)、係数に \(1\)、\(-1\)、\(-90\) と入れると、\(10\) と \(-9\) が返ります。（この Degree は polynomial（多項式）の次数のことで、vertex の degree とは別のものです。）

警告電卓が返した負の解は、必ず捨ててください

vertex の数は負になりません。捨てた理由を答案に一言書くところまでが解答です（SL 1.8）。

3. Summing the degrees（次数の合計を求める）

vertex が多いときは、degree をリストに入れて sum() で足すと、数え落としが見つけやすくなります。sum( は catalog から選べます（SL 1.2 と同じ関数です）。

\(\texttt{sum}\left(\{2,\ 3,\ 4,\ 3,\ 2\}\right)\)

\(14\) と返れば、edge が \(7\) 本のはずです。合っていなければ、数え直しの合図です。

ノートadjacency matrix（隣接行列）は、次の項目です

「つながりを行列で書く」やり方——adjacency matrix（隣接行列）——は AHL 3.15 で扱います。そこからは、電卓の出番が一気に増えます。

この項目では、言葉と数え方に集中してください。

Exercises

1 The graph below has vertices \(A\), \(B\), \(C\), \(D\), \(E\) and \(F\).

(a) Write down the number of edges.

(b) Write down the degree of each vertex.

(c) Verify your answers using the sum of the degrees.

(a) \(8\)

(b) \[ \deg(A)=3,\quad \deg(B)=2,\quad \deg(C)=4 \] \[ \deg(D)=3,\quad \deg(E)=2,\quad \deg(F)=2 \]

(c) \[ 3+2+4+3+2+2 = 16 = 2 \times 8 \quad ✓ \]

(a) \(AB\)、\(AC\)、\(AD\)、\(BC\)、\(CD\)、\(DE\)、\(EF\)、\(CF\) の \(8\) 本です。\(1\) つの vertex に付いているものを順に拾うと、数え落としが減ります。

(b) \(1\) つの vertex ずつ、付いている edge の端を数えます。\(C\) には \(AC\)、\(BC\)、\(CD\)、\(CF\) の \(4\) 本が付いているので \(\deg(C) = 4\) です。

(c) 合計 \(16\) が \(8\) の \(2\) 倍になっているので、(a) と (b) は食い違ってはいません（式 1）。

ただし、これで「両方合っている」とまでは言えません。edge を \(1\) 本まるごと数え落とすと、その両端の degree も同時に \(1\) ずつ減るので、合計はやはり \(2\) 倍のままになります。

この検算が教えてくれるのは「合わなければ、どこかが誤り」ということだけです。合わなかったら、両方を疑ってください。

2 A graph has \(9\) edges. Every vertex has degree \(3\). Find the number of vertices.

\[ \sum \deg(v) = 2 \times 9 = 18 \] \[ 3n = 18 \quad \Rightarrow \quad n = 6 \]

図がなくても解けます。式 1 から、degree の合計は \(18\) と決まります。

そのうえで「\(3\) が \(n\) 個で \(18\)」と考えれば、\(n = 6\) です。

graph をかく必要はありません。 この形の問題は、\(2\) 行で終わります。

3 Consider the complete graph \(K_{7}\).

(a) Write down the degree of each vertex.

(b) Find the number of edges.

(a) \(\deg = 7 - 1 = 6\)

(b) \[ \frac{7 \times 6}{2} = 21 \]

(a) complete graph では、\(1\) つの vertex が自分以外の \(6\) つ全部と結ばれています。

(b) 式 2 に \(n = 7\) を入れます。電卓なら nCr(7, 2) でも \(21\) が出ます（GDC 第1節）。

検算。 \(7 \times 6 = 42 = 2 \times 21\) ✓

4 Explain why there is no graph with exactly five vertices, each of degree \(3\).

\[ \sum \deg(v) = 5 \times 3 = 15 \]

The sum of the degrees must equal twice the number of edges, so it must be even. \(15\) is odd, so no such graph exists.

degree の合計は、edge の数の \(2\) 倍でした。ですから、必ず偶数になります。

試験ではこう書く

The sum of the degrees equals twice the number of edges, so it is always even.

Here the sum would be \(5 \times 3 = 15\), which is odd, so no such graph exists.

\(5 \times 3 = 15\) は奇数なので、そんな graph は作れません。

図をかいて試す必要はありません。 合計が奇数だと分かった時点で、答えが出ています。この形の問題は、式 1 だけで片付きます。

5 The directed graph below has vertices \(A\), \(B\), \(C\) and \(D\).

(a) Write down the in degree and the out degree of each vertex.

(b) Verify that both totals equal the number of directed edges.

(a)

vertex \(A\) \(B\) \(C\) \(D\)
in \(1\) \(2\) \(1\) \(1\)
out \(1\) \(1\) \(2\) \(1\)

(b) \[ 1+2+1+1 = 5, \qquad 1+1+2+1 = 5 \]

There are \(5\) directed edges, so both totals are correct.

矢印は \(A \to B\)、\(B \to C\)、\(C \to A\)、\(C \to D\)、\(D \to B\) の \(5\) 本です。

入る矢印と出る矢印を、別々に数えてください。 混ぜてしまうのが一番多い誤りです。

(b) \(1\) 本の矢印は「どこかから出て、どこかへ入る」ので、in の合計も out の合計も矢印の本数と同じになります（第8節）。

6 Two directed graphs are shown below.

For each graph, determine whether it is strongly connected. Justify your answers.

Graph 1 is strongly connected. The directed cycle \(A \to B \to C \to A\) joins those three vertices, \(D\) is reached by \(C \to D\), and \(D \to B\) returns to the cycle. So every vertex can be reached from every other vertex; for example \(D \to B \to C \to A\).

Graph 2 is not strongly connected: no directed edge leaves \(S\), so it is impossible to travel from \(S\) to any other vertex.

graph 1 は、\(C \to A\) という「もどる矢印」があるのが効いています。\(D\) から \(A\) へも \(D \to B \to C \to A\) で行けます。

graph 2 は、\(S\) から出る矢印が \(1\) 本もありません。入ってくるだけで、出られません。 ですから strongly connected ではありません。

justify が付いているので、行けない具体例を \(1\) つ挙げるところまで書いてください。「いいえ」だけでは点になりません。

試験ではこう書く

Graph 1 is strongly connected: \(A \to B \to C \to A\) is a directed cycle, \(C \to D\) reaches \(D\), and \(D \to B\) returns to the cycle, so every vertex is reachable from every other — for example \(D \to B \to C \to A\).

Graph 2 is not strongly connected: no directed edge leaves \(S\), so \(S\) cannot reach any other vertex.

なお graph 2 も、矢印を無視すれば connected です。connected と strongly connected を混同しないでください（第10節）。

7 A connected graph has \(12\) vertices and no cycles.

(a) State the name given to such a graph.

(b) Write down the number of edges.

(c) Another graph also has \(12\) vertices and \(11\) edges. Explain why this is not enough to conclude that it is a tree.

(a) A tree.

(b) \[ 12 - 1 = 11 \]

(c) The condition works only one way: a tree with \(12\) vertices must have \(11\) edges, but a graph with \(12\) vertices and \(11\) edges need not be a tree. For example, a triangle together with a separate tree on the other nine vertices has \(12\) vertices and \(11\) edges, but it contains a cycle and is not connected.

(a) connected で cycle がない——これが tree の定義そのものです（第12節）。

(b) 式 3 より \(12 - 1 = 11\) 本です。

検算。 degree の合計は \(2 \times 11 = 22\) になるはずです。

(c) Explain why なので、言葉で理由を書きます。 要点は「逆が言えない」ことです。

反例を \(1\) つ挙げると、答案が強くなります。図 14 の左は、\(4\) 個と \(3\) 本で tree ではありませんでした。同じ作り方を \(12\) 個に広げれば、三角形 \(1\) つ（\(3\) 個・\(3\) 本）＋ 残り \(9\) 個をつないだ tree（\(9\) 個・\(8\) 本）で、合計 \(12\) 個・\(11\) 本になります。

検算。 \(3 + 8 = 11\) ✓ この graph には cycle があり、しかも \(2\) つに分かれています。

試験ではこう書く

The implication only works one way.

A tree with \(12\) vertices must have \(11\) edges, but a graph with \(12\) vertices and \(11\) edges need not be a tree: for example, a triangle together with a tree on the other nine vertices has \(12\) vertices and \(3 + 8 = 11\) edges, yet it contains a cycle and is not connected.

8 Consider the graph in question 1.

(a) Write down the edges of the subgraph on the vertices \(A\), \(B\), \(C\) and \(D\) that contains every edge of the original graph joining two of them.

(b) Write down the edges of a different subgraph on the same four vertices, and explain why it is also a subgraph.

(a) \[ AB,\quad AC,\quad AD,\quad BC,\quad CD \]

(b) For example \(AB\), \(AC\), \(CD\).

A subgraph only has to use vertices and edges of the original graph; it does not have to include every edge between the chosen vertices. Each of \(AB\), \(AC\), \(CD\) is an edge of the original graph, and both of its endpoints are among \(A\), \(B\), \(C\), \(D\).

(a) 「そのうちの \(2\) つを結ぶ辺をすべて」と指定されているので、両端がそろっている edge を全部残します。

\(DE\)、\(EF\)、\(CF\) は、\(E\) や \(F\) が選ばれていないので入りません。

このように選んだ vertex のあいだの edge を全部残した subgraph を induced subgraph（誘導部分グラフ）といいます（第11節）。

(b) ここが、subgraph でいちばん取りちがえやすいところです。edge を全部残す必要はありません。 \(AB\)、\(AC\)、\(CD\) の \(3\) 本だけを選んでも、立派な subgraph です。

ただし、もとの graph にない edge は足せません。 \(B\) と \(D\) を結びたくなりますが、問題 1 の graph に \(BD\) がないので、subgraph にも入りません。

試験ではこう書く

A subgraph only has to use vertices and edges of the original graph; it does not have to include every edge between the chosen vertices.

Each of \(AB\), \(AC\), \(CD\) is an edge of the original graph and both of its endpoints are among \(A\), \(B\), \(C\), \(D\), so this is a subgraph.

（\(AB\) だけ、あるいは edge を \(1\) 本も選ばない形も subgraph です。答えは \(1\) つに決まりません。）

9 The graph below shows five areas of a house. Two areas are joined by an edge if there is a door between them.

(a) Write down the degree of the vertex Hall, and interpret this number in context.

(b) Explain why the graph is connected, and say what this means for the house.

(a) \(\deg(\text{Hall}) = 3\)

The hall has three doors leading directly to other areas.

(b) Every area can be reached from every other area, for example Study \(\to\) Hall \(\to\) Kitchen \(\to\) Garden. So you can walk from any area of the house to any other without going outside.

(a) Hall に付いている edge は Kitchen、Lounge、Study の \(3\) 本です。

interpret this number in context と言われたら、\(3\) という数字が現実で何なのかを書きます。ここでは「ドアが \(3\) つある」です。数字だけでは点になりません。

試験ではこう書く

\(\deg(\text{Hall}) = 3\), which means the hall has three doors leading directly to other areas of the house.

(b) connected は「乗りついで、どの \(2\) 点のあいだも行き来できる」でした（第9節）。ここでは「どの部屋からどの部屋へも行ける」という意味になります。

理由として具体的な道を \(1\) つ書いておくと、答案が強くなります。Study と Garden は adjacent ではありませんが、Hall と Kitchen を乗りつげば行けます。

試験ではこう書く

The graph is connected because every area can be reached from every other area, for example Study \(\to\) Hall \(\to\) Kitchen \(\to\) Garden.

This means you can walk from any area of the house to any other without going outside.

10 The weighted graph below shows the times, in minutes, to walk between four buildings.

(a) Write down the degree of vertex \(D\).

(b) Find the total time for the route \(A \to B \to D \to C\).

(c) Find a quicker route from \(A\) to \(C\), and state its total time.

(a) \(\deg(D) = 3\)

(b) \[ 5 + 6 + 4 = 15 \ \text{minutes} \]

(c) The route \(A \to D \to C\) takes \[ 9 + 4 = 13 \ \text{minutes} \]

(a) \(D\) に付いている edge は \(DA\)、\(DB\)、\(DC\) の \(3\) 本です。

(b) 通った edge の weight を足すだけです。\(AB = 5\)、\(BD = 6\)、\(DC = 4\) で \(15\) 分。

(c) 同じ場所を \(2\) 度通らない道は、\(4\) つあります。

経路 時間
\(A \to B \to C\) \(5 + 8 = 13\)
\(A \to D \to C\) \(9 + 4 = 13\)
\(A \to B \to D \to C\) \(5 + 6 + 4 = 15\)
\(A \to D \to B \to C\) \(9 + 6 + 8 = 23\)

\(13\) 分の道が \(2\) つあるので、どちらを書いても正解です。a quicker route は「(b) より速い道を \(1\) つ」という意味なので、\(1\) つ書けば足ります。

weight の大きい edge を通る道が、いつも遅いとはかぎりません。 \(AD\) は \(9\) と大きいのに、\(A \to D \to C\) は速いほうに入ります（第7節）。必ず足して比べてください。

11 A small flat has a Hall, a Kitchen, a Bedroom, a Bathroom and a Balcony. There is a door between the Hall and each of the Kitchen, the Bedroom and the Bathroom. There is also a door between the Kitchen and the Balcony, and a door between the Bedroom and the Bathroom. There are no other doors.

(a) Draw a graph to represent the flat, stating what the vertices and the edges represent.

(b) Write down the degree of each vertex, and verify your graph using the sum of the degrees.

(c) Determine whether the graph is a tree. Justify your answer.

(a) Each vertex represents a room, and each edge represents a door between two rooms.

Vertices: Hall, Kitchen, Bedroom, Bathroom, Balcony.

Edges: Hall–Kitchen, Hall–Bedroom, Hall–Bathroom, Kitchen–Balcony, Bedroom–Bathroom.

(b) \[ \deg(\text{Hall}) = 3, \quad \deg(\text{Kitchen}) = 2, \quad \deg(\text{Bedroom}) = 2 \] \[ \deg(\text{Bathroom}) = 2, \quad \deg(\text{Balcony}) = 1 \] \[ 3+2+2+2+1 = 10 = 2 \times 5 \quad ✓ \]

(c) It is not a tree. The graph is connected, but Hall \(\to\) Bedroom \(\to\) Bathroom \(\to\) Hall is a cycle, so the second condition fails.

(a) 第1節の作業です。つながれる側が vertex なので、部屋が vertex、ドアが edge です（表 1）。

ドアを vertex にしてはいけません。

stating what the vertices and the edges represent と書かれているので、その一文を必ず添えてください。 図だけでは点になりません。

なお、Draw は本来「定規と目盛りで正確にかく」という指示ですが、graph には位置にも線の長さにも意味がありません（第1節）。ここでは、どの vertex とどの vertex が結ばれているかが読み取れれば十分です。

(b) ドアは \(5\) つなので edge は \(5\) 本。degree の合計は \(10 = 2 \times 5\) です（式 1）。合わなければ、ドアを読み落としています。

Balcony は Kitchen としかつながっていないので、\(\deg = 1\) です。

(c) tree の判定は \(2\) つでした（第12節）。

  • connected か。 どの部屋からも、Hall を通ってどこへでも行けます ✓
  • cycle がないか。 Hall \(\to\) Bedroom \(\to\) Bathroom \(\to\) Hall で、もとの場所にもどってきます ✗

\(1\) つ目は成り立ちますが、\(2\) つ目が成り立たないので tree ではありません。

試験ではこう書く

The graph is connected, but Hall \(\to\) Bedroom \(\to\) Bathroom \(\to\) Hall is a cycle.

A tree must be connected and have no cycle, so this graph is not a tree.

本数で先に確かめることもできます。 vertex が \(5\) 個なら tree の edge は \(4\) 本のはずですが、ここは \(5\) 本です。ただしこれは「合わないから tree ではない」という使い方に限られます（第12節）。合っていても tree とはかぎらないので、答案には cycle を書いてください。