課程名稱︰離散數學
課程性質︰選修
課程教師：陳健輝
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2015.06.25
考試時限（分鐘）：
試題 :
Examination # 3
(範圍: Graph Theory)
(All graphs mentioned below are simple, and unless mentioned particularly,
they are undirected.)
1. Let G = (V, E) be a connected graph and |V| = n. What are the minimum
values of |E| so that G can be constructed, respectively, as
(a) a complete bipartite graph and (5%)
(b) a regular graph? (5%)
Ans: (a) n-1
(b) n
2. Give two graphs that have the same number of vertices, the same number of
edges, the same nondecreasing degree sequence (for example, the graph shown
below has nondecreasing degree sequence 1, 2, 2, 2, 3), but are not
isomorphic. (10%).
●
╱ ╲
●──● ●
╲ ╱
●
Ans: ● ●
│ │
●─●─●─●─● ●─●─●─●─●
3. Consider the following graph.
b●───●c
∕ ╲ ╱ ﹨
∕ ●g ﹨
∕ ╱ ╲ ﹨
a● ∕ h●─●d
﹨∕ ﹨∕
f●─────●e
(a) Give a trail, which is not a path. (5%)
(b) How many extra edges are needed at least in order to have an Euler
trail? (5%)
Ans: (a) (b, g, h, e, f, g, c)
(b) 2
4. Let G = (V, E) be a connected graph and T be a depth-first spanning tree
of G. Give a sufficient and necessary condition, in terms of functions L
and DFN, for (i, j) ∈ E to be a bridge of G. (DFN(i) represents the
visiting sequence of vertex i by DFS and L(i) represents the least DFN
reachable from i through a path consisting of zero or more downward tree
edges followed by zero or one back edge.) (10%)
Ans: L(j) = DFN(j) (Please refer to page 62 of lecture notes.)
5. Given a graph G, how to find matrices C, C^2, …, C^(|V|-1) so that for
1 ≦ k ≦ |V| - 1 and i ≠ j, (C^k)(i, j) tells the number of different
i-to-j walks of length k in G? (10%)
Ans: Please refer to Problem 5 of Exercise #11.
本題寫的是"length k"，而該習題寫的是"length ≦ k"。
(甲) C是G的相鄰矩陣，
(乙) 如果G有(u, v)這條邊，C_(u,v) = 1；
如果G有(u, v)這條邊，C_(u,v) = 0。
(丙) (C^k)(i, j)就直接C的k次方。
6. How to modify a maximum clique algorithm (i.e., an algorithm that can find
a maximum clique of a graph) so that it can be used to find a minimum
vertex cover of a graph? (10%)
Ans: Please refer to Problem 6 of Exercise #12.
_ _
G是G的補圖（有邊變沒邊，沒邊變有邊），那麼C是G的clique <=> V-C是G的
_
vertex cover，C是G的maximum clique <=> V-C是G的minimum vertex cover，
_
同理，D是G的maximum clique <=> V-D是G的minimum vertex cover
（C和D都是點的集合）
7. Suppose that N = (V, E) is a transport network and F is the maximum flow
of N. Give a sufficient and necessary condition, in terms of f(e) and c(e),
for a cut of N induced by S (⊂V) to have c(S) = F. (10%)
Ans: Please refer to page 124 of lecture notes.
_ _
f(e) = c(e) for each e ∈ E(S;S); f(e) = 0 for each e ∈ E(S;S).
8. Find the maximum total flow of the following transport network. (10%)
ⓑ──６→ⓔ
↗ ↖ ↗↑╲
５ ３２ １ ╲
╱ ╱╲ │ 11
╱ ╱ ╲│ ↘
ⓐ──６→ⓒ ⓕ──２→ⓗ
╲ ↑╲ ↗ ↗
╲ ４ ╲６ ７
８ │ ╱５ ╱
↘│╱ ↘ ╱
ⓓ──５→ⓖ
Ans: 18
找步數最少的路徑，指派流量。
路徑 流量 流量加總 刪除邊
1. a → c → e → h 2 0 + 2 = 2 ce
2. a → d → f → h 2 2 + 2 = 4 fh
3. a → b → e → h 5 4 + 5 = 9 ab
4. a → d → g → h 5 9 + 5 = 14 dg
5. a → c → g → h 2 14 + 2 = 16 gh
6. a → d → f → e → h 1 16 + 1 = 17 ad, fe
7. a → c → d → f → b → e → h 1 17 + 1 = 18 be
9. Consider a graph G = (V, E), where V = {v_1, v_2, ..., v_n} and n ≧ 2. Let
d_i be the degree of v_i. Prove that if d_i + d_j ≧ n-1 for every
(v_i, v_j) 不屬於 E and v_i ≠ v_j, then G is connected. (10%)
Ans: Please refer to page 74 of lecture notes.
方法一：
如果 v_i 和 v_j 分別落在兩個不同的連通部分 C_1, C_2
（注意：G不連通 => G至少有兩個連通部分，不要寫成剛好有兩個）
那麼 d_i + d_j ≦ (|C_1| - 1) + (|C_2| - 1) ≦ n - 2，
與 d_i + d_j ≧ n + 1 矛盾
方法二：
沒(v_i, v_j)這條邊，我還是能想辦法走過去
╭──╮ ╭──╮
│v_i │ │v_j │
╰──╯ ╰──╯
╱│╲ ╱│╲ 至少 n-1 條邊
╱ │ ╲ ╱ │ ╲
╭───────────────────╮
│ │
│ n-2 個點 │
│ │
╰───────────────────╯
v_i 或 v_j 到「其他地方」（即 V-{v_i, v_j}）有至少 n-1 條邊，
但「其他地方」只有 n-2 個點，
根據抽屜原則，在「其他地方」中一定有一個點 v 有 (v_i, v) 和 (v, v_j)
這兩條邊，v_i 就經由 v 走到 v_j，所以圖連通。
G 有 Hamiltonian path 的性質不能直接用，因為本題是該性質證明的一部份。
10. Suppose that G is a regular graph of degree k ≧ 2. Show that there exists
a path of length k in G. (10%)
Ans: Clearly, there exists an edge in G. Let P = (v_1, v_2, …, v_m) be a
path of length m-1 in G, where 2 ≦ m ≦ k. There exists a vertex,
say v, in G so that v is not included in P and v is adjacent to v_m,
as a consequence that v_m has degree k ≧ m. In this way, we can
extend P until its length is k.
方法一：
如果最長的路徑 (v_1, v_2, …, v_x) x < k，
因為該路徑無法由端點 v_x 延伸，
因此 v_x 只能和 v_1, v_2, …, v_(x-1) 相鄰
=> degree(v_x) ≦ x-1，與 G is a regular graph of degree k 矛盾
方法二：
先選一個起點叫 v_0，然後隨便找一個鄰居叫 v_1。
v_1 除了連 v_0，還有 k-1 條邊，再走一步，假設叫 v_2。
v_2 除了連 v_1、有可能連 v_0，還有至少 k-2 條邊，再走一步，假設叫v_3。
v_3 除了連 v_2、有可能連 v_0, v_1，還有至少 k-3 條邊，再走一步，假設
叫 v_4。
…
v_i 除了連 v_(i-1)、有可能連 v_0, v_1, …, v_(i-2)，還有至少 k-i 條邊
，再走一步，假設叫 v_(i+1)。
…
v_(k-1) 除了連 v_(k-2)、有可能連 v_0, v_1, …, v_(k-3)，還有至少 1 條
邊，再走一步，假設叫 v_k。
v_0 → v_1 → … → v_k 就是長度為 k 的路徑。
11. For a graph G, its line graph, denoted by L(G), is defined as follows.
Each edge of G uniquely corresponds to a vertex of L(G), and two edges
of G are incident to the same vertex if and only if their corresponding
vertices in L(G) are adjacent. An illustrative example is shown below.
Prove that if G has an Euler circuit, then L(G) has an Euler circuit as
well. (10%)
● ● e1
e1│ ╱ ╲
│ ╱ ╲
● e2 ●─────● e3
e2╱ ╲e3 ╲ ╱
╱ e4 ╲ ╲ ╱
●─────● ● e4
G L(G)
Ans: Suppose that (v_1, v_2, ..., v_p) is an Euler circuit of G. Then, L(G)
has p-1 vertices, denoted by e_(1,2), e_(2,3), ..., e_(p-1,p), where
e_(1,2) corresponds to (v_1, v_2), e_(2,3) corresponds to (v_2, v_3),
and so on. Let d_i be the degree of v_i in G, where 1 ≦ i ≦ p.
Clearly, d_i is even, as a consequence of G having an Euler circuit.
Hence each e_(j-1,j) (2 ≦ j ≦ p) has even degree in L(G), and there
exists an Euler circuit in L(G)
邊變點，兩邊相鄰變兩點相鄰
G 有 Euler circuit => G 中每個點都有偶數條邊，而且 G 連通
(u, v) 是 G 的邊 => deg(u) 是偶數，deg(v) 也是偶數
(u, v) 和 deg(u)-1 + deg(v)-1 條邊相鄰（兩次 -1 都是去掉 (u, v) 本身）
在 L(G) 中，deg((u, v)) = deg(u)-1 + deg(v)-1 是偶數。 (１)
L(G) 連通也不是問題，
L(G) 中任兩「點」(v1, v2) 和 (v3, v4)，
因為 G 連通 => G 中任兩點都存在路徑 => v_2 到 v_3 存在路徑
所以 (v_1, v_2) 和 (v_3, v_4) 存在 (v_1, v_2) → v_2 到 v_3 的路徑
→ (v_3, v_4) 這條路徑。 (２)
由(１)和(２)，L(G) 有 Euler circuit。
12. There is a matching theorem for a bipartite graph G = (R∪S, E), where
|R| < |S| is assumed as follows. If |W| ≦ |ADJ(W)| for every W ⊆ R,
then G has a complete matching It is known that the theorem can be proved
by induction. Show the proof for the situation |W| < |ADJ(W)| holds for
every W ⊆ R. (hint: arbitrarily pick an edge of G.) (10%)
Ans: 當 R 只有一個點的時候，直接從 ADJ(W) 選一個點來匹配即可。
假設 |R| = k 的時候 G 有完全匹配，看 |R| = k+1 的情況。
先從 R 選 k 的點(假設叫 R-{x})，然後找出一個 (R-{x})∪ADJ(R-{x}) 的完
全匹配 M，
如果 ADJ(x) - (M的點) ≠ ψ，就從 ADJ(x) - ADJ(R-{x}) 挑一個點 y，
M 加上 (x, y) 即為 G 的完全匹配。
如果 ADJ(x) - (M的點) = ψ，那麼 ADJ(x) ⊆ (M的點)∩S !⊆ ADJ(R-{x})，
從 ADJ(x) 挑一個點 y，因為 |R-{x}| < |ADJ(R-{x})|，所以
|R-{x}| ≦ |ADJ(R-{x})-{y}|，
(R-{x})∪(ADJ(R-{x})-{y}) 有完全匹配（這個可以直接讓同學使用），
(R-{x})∪(ADJ(R-{x})-{y}) 的完全匹配加上 (x, y) 即為 G 的完全匹配。
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.228.146.201
※ 文章網址: https://www.ptt.cc/bbs/NTU-Exam/M.1440860585.A.058.html