この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

グラフ理論の問題

難易度 3期末試験の応用レベル大学数学グラフ理論

頂点集合 $V = {s, a_{1}, a_{2}, a_{3}, a_{4}, b_{1}, b_{2}, b_{3}}$ と、次の $10$ 本の辺からなる単純無向グラフ $G$ を考える。
$E = {s a_{1}, a_{1} a_{2}, a_{2} a_{3}, a_{3} a_{4}, a_{4} s, a_{1} a_{3}, s b_{1}, b_{1} b_{2}, b_{2} b_{3}, b_{3} s}$
$G$ で隣接していない相異なる $2$ 頂点の組 ${u, v}$ に対し、 $G$ に辺 $uv$ を $1$ 本加えた単純グラフを $G + uv$ と書く。

ここで、オイラー路とはすべての辺をちょうど $1$ 回ずつ通る道（始点と終点は一致してもしなくてもよい）であり、ハミルトン閉路とはすべての頂点をちょうど $1$ 回ずつ通る閉路である。

隣接していない $2$ 頂点の組 ${u, v}$ のうち、
- $G + uv$ がオイラー路をもつものの個数を $p$ 、
- $G + uv$ がハミルトン閉路をもつものの個数を $q$ 、
- $G + uv$ がオイラー路とハミルトン閉路の両方をもつものの個数を $r$

とする。組 $(p, q, r)$ をこの順に求めよ。

この問題で使うもの

グラフの次数と握手補題（説明と入口の問題）
オイラー路・オイラー閉路の判定（説明と入口の問題）
ハミルトン閉路の有無（説明と入口の問題）
和の法則・積の法則と樹形図（説明と入口の問題）

この問題を解けるようになるまで（9 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

オイラー路の有無は奇数次の頂点の個数で決まります。ハミルトン閉路については、 $G$ の切断点 $s$ に注目しましょう。

ヒント 2

辺 $uv$ を加えると $u, v$ の次数の偶奇だけが変わります。また、切断点をもつグラフはハミルトン閉路をもちません。したがって、ハミルトン閉路の候補は $A = {a_{1}, \dots, a_{4}}$ と $B = {b_{1}, b_{2}, b_{3}}$ をまたぐ辺 $a_{i} b_{j}$ だけです。

ヒント 3

奇数次の頂点は $a_{1}, a_{3}$ なので、オイラー路をもつのは $a_{1}$ または $a_{3}$ のちょうど一方を端点にもつ組です。 $a_{i} b_{j}$ を加えたときのハミルトン閉路は、「 $s$ の隣接点から $a_{i}$ まで $A$ をすべて通る道」と「 $b_{j}$ から $s$ の隣接点まで $B$ をすべて通る道」の組に対応します。

答えと解説

答えを見る

(8, 6, 2)

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

次数と非隣接な組

各頂点の次数は
$de g s = 4, de g a_{1} = 3, de g a_{2} = 2, de g a_{3} = 3, de g a_{4} = 2, de g b_{1} = de g b_{2} = de g b_{3} = 2$
である（合計 $20 = 2 \times 10$ ）。奇数次の頂点は $a_{1}, a_{3}$ の $2$ 個である。

$A = {a_{1}, a_{2}, a_{3}, a_{4}}$ 、 $B = {b_{1}, b_{2}, b_{3}}$ とおく。隣接していない組は $(2 8) - 10 = 18$ 個あり、次のとおりである。
- $A \cup {s}$ の内部： $s a_{2}, s a_{3}, a_{1} a_{4}, a_{2} a_{4}$ の $4$ 個
- $B \cup {s}$ の内部： $s b_{2}, b_{1} b_{3}$ の $2$ 個
- $A$ と $B$ をまたぐもの： $a_{i} b_{j}$ の $4 \times 3 = 12$ 個

$p$ の計算

$G + uv$ は連結である。連結グラフがオイラー路をもつのは、奇数次の頂点が $0$ 個または $2$ 個のときに限る。辺 $uv$ を加えると、 $u, v$ の次数の偶奇だけが入れかわる。
- $u, v$ の両方が ${a_{1}, a_{3}}$ に属する場合： $a_{1} a_{3}$ はすでに辺なので起こらない。
- ちょうど一方が ${a_{1}, a_{3}}$ に属する場合：奇数次の頂点は $2$ 個になり、オイラー路をもつ。
- どちらも属さない場合：奇数次の頂点は $4$ 個になり、オイラー路をもたない。

$a_{1}$ と隣接しない頂点は $a_{4}, b_{1}, b_{2}, b_{3}$ 、 $a_{3}$ と隣接しない頂点は $s, b_{1}, b_{2}, b_{3}$ である。よって $p = 4 + 4 = 8$ である。

$q$ の計算

$G$ では $s$ が切断点である（ $s$ を除くと $A$ と $B$ に分かれる）。ハミルトン閉路から $1$ 頂点を除いたものは道であり連結なので、切断点をもつグラフはハミルトン閉路をもたない。

加える辺が $A \cup {s}$ や $B \cup {s}$ の内部にあるときは、 $s$ は切断点のままである。したがってハミルトン閉路はない。

加える辺が $a_{i} b_{j}$ のときを考える。ハミルトン閉路 $C$ は辺 $a_{i} b_{j}$ を必ず使う（使わなければ $C$ は $G$ のハミルトン閉路になり矛盾する）。 $C$ から $s$ を除いた道 $P$ は $A$ と $B$ のすべての頂点を通る。 $A$ と $B$ を結ぶ辺は $a_{i} b_{j}$ だけなので、 $P$ は次の $2$ つをつないだ形になる。
- $A$ の全頂点を通り、 $s$ の隣接点（ $a_{1}$ または $a_{4}$ ）から出発して $a_{i}$ で終わる道
- $B$ の全頂点を通り、 $b_{j}$ から出発して $s$ の隣接点（ $b_{1}$ または $b_{3}$ ）で終わる道

逆に、この $2$ つの道があれば、両端を $s$ と辺 $a_{i} b_{j}$ でつないでハミルトン閉路ができる。

$B$ 側： $G [B]$ は道 $b_{1} b_{2} b_{3}$ である。 $B$ の全頂点を通る道の端点は $b_{1}$ と $b_{3}$ だけで、もう一方の端も $s$ に隣接する。よって $b_{j} \in {b_{1}, b_{3}}$ のときに限り条件を満たす。

$A$ 側： $G [A]$ の辺は $a_{1} a_{2}, a_{2} a_{3}, a_{3} a_{4}, a_{1} a_{3}$ である。 $a_{4}$ は $G [A]$ で $a_{3}$ としか隣接しないので、 $A$ の全頂点を通る道では $a_{4}$ は必ず端点になる。
- $a_{i} = a_{1}$ ： $a_{4} a_{3} a_{2} a_{1}$ があるので条件を満たす。
- $a_{i} = a_{2}$ ： $a_{4} a_{3} a_{1} a_{2}$ があるので条件を満たす。
- $a_{i} = a_{4}$ ： $a_{1} a_{2} a_{3} a_{4}$ があるので条件を満たす。
- $a_{i} = a_{3}$ ：端点は $a_{3}$ と出発点なので、出発点は $a_{4}$ でなければならない。しかし $a_{4}$ の次は $a_{3}$ しかなく、 $a_{3}$ が $2$ 番目に来て終点になれない。よって条件を満たさない。

したがって $a_{i} \in {a_{1}, a_{2}, a_{4}}$ 、 $b_{j} \in {b_{1}, b_{3}}$ のときに限りハミルトン閉路をもち、 $q = 3 \times 2 = 6$ である。

例えば $G + a_{1} b_{1}$ では、 $s a_{4} a_{3} a_{2} a_{1} b_{1} b_{2} b_{3} s$ がハミルトン閉路になる。

$r$ の計算

オイラー路をもつ $8$ 組のうち、ハミルトン閉路の条件を満たすのは、 $a_{1}$ または $a_{3}$ と $b_{1}$ または $b_{3}$ を結ぶ組で、しかも $a_{3}$ を含まないものである。それは $a_{1} b_{1}, a_{1} b_{3}$ の $2$ 組なので、 $r = 2$ である。

以上より $(p, q, r) = (8, 6, 2)$ である。

別解

G の次数は s:4, a1:3, a2:2, a3:3, a4:2, b1,b2,b3:各2。G は連結で、奇数次数の頂点は a1, a3 の2つ。隣接していない組は C(8,2)−10=18 個。

【p】G+uv がオイラー路をもつ条件は、連結かつ奇数次数の頂点が 0 個または 2 個であること。辺を加えると u, v の次数の偶奇が入れ替わる。
- 両方が偶数次数の頂点だと、奇数次数の頂点は4個になり不可。
- 両方が奇数次数の頂点 {a1,a3} は隣接しているので、組として不適。
- 一方が {a1,a3}、他方が偶数次数の頂点なら、奇数次数の頂点は2個で可。

a1 と非隣接なのは a4,b1,b2,b3 の4個、a3 と非隣接なのは s,b1,b2,b3 の4個。よって p=8。

【q】s を除くと {a1,a2,a3,a4} と {b1,b2,b3} に分かれるので、s は切断点。ハミルトン閉路をもつには、加える辺 uv が a 側と b 側を結ぶ辺 x–b でなければならない（s を含む辺や同じ側どうしの辺では s が切断点のまま）。
閉路は s→b 側の経路→x→a 側の経路→s の形になる。b 側のハミルトン経路は b1b2b3 のみで、s に隣接する端は b1,b3 なので b∈{b1,b3}。
a 側の誘導グラフの辺は a1a2, a2a3, a3a4, a1a3。そのハミルトン経路は a4-a3-a1-a2 と a4-a3-a2-a1 のみ。経路の一端は x、他端は s に隣接する a1 か a4 でなければならない。これを満たす x は a2（他端 a4）、a1（他端 a4）、a4（他端 a1）の3通り。
これらの x と b1, b3 の組はすべて G で非隣接なので、3×2=6組。よって q=6。

【r】q の6組のうち、a1 または a3 を含むものは {a1,b1}, {a1,b3} の2組。よって r=2。

答え (p,q,r)=(8,6,2)。

グラフ理論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題