課程名稱︰ 離散數學
課程性質︰ 系必修
課程教師︰ 陳健輝
開課學院： 電資學院
開課系所︰ 資訊工程學系
考試日期（年月日）︰ 96/11/14
考試時限（分鐘）： 120 mins
是否需發放獎勵金：是
試題 :
Your solutions 1 to 5 are required to be concise as possible. No
further explanation is needed.
1. Refer to the graphs. Which of G1, G2, and G3 are (a) complete graphs,
(b) bipartite graphs, and (c) planner graphs? (2% each)
Which of G4, G5 and G6 have (d) an Euler circuit and (e) a Hamiltionian
path? (6% each)
○
│
│
○───○ ○ G2 K(3,3) G3
／＼
G1 ╱ ╲
○————○
○——○ ○——○ ○——○——○ ○——○
｜ ｜╲／｜ ｜ ｜╲／ ／｜ ｜╲／｜
｜ ｜╱╲｜ ｜ ｜╱╲ ╱ ｜ ｜╱╲｜
○——○ ○——○ ○——○ ○——○——○
G4 G5
2. Refer to the graph G below.
○a
／｜╲
／ ｜ ╲
○e ○r ○b
╲ ／╲ ／
d○——○c
(a) Determine the vetex connectivity of G. (2%)
(b) Find a maximum matching of G. (2%)
(c) Find a maximum clique of G. (2%)
(d) Deter the chromatic number of G. (2%)
(e) Give a vertex sequence of G when G is traversed by a breadth
first search, starting with r. (2%)
3. Refer to the grachs G below.
○——○ ○h
｜ ｜╲ ╱
｜ ｜╱○——○
a○——○ ╲
○
(a) Determine the cost of a minimum spaning tree of G. (6%)
(b) Determine the length of a shortest a-to-h path in G.(6%)
(c) Find all articulation points of G. (2%)
4. Find an isomorphism between the following two isomorphic graphs. (8%)
○a ○
／｜╲ ／｜╲
／ ｜ ╲ ／ ｜ ╲
○e ○r ○b ／ ○ ╲
╲ ／╲ ／ ／ ／ ╲ ╲
d○——○c ／ ○ ○ ╲
／ ／ ╲ ╲
○———————————— ○
5. For the following transport network, determine the maximum total flow a
to z and find a correspond minimum cut. (10%)
○g→ 3→○h→12→○z
↑ ↗↑↖ ↑
5 2 6 3 6
↑ ↗ ↑ ↖ ↑
○d← 6←○e← 4←○f
↑ ↘ ↑ ↗↑
14 13 5 4 3
↑ ↘↑ ↗ ↑
○a→ 5→○b→ 4→○c
--
╖ ╔ ╭═╮ ╔═╮ ╔═╕
╠╦╯ ║ ║ ╠═╣ ╠═
╜╚╛ ╰═╯ ╚═╯ ╚═╛
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 61.230.148.137