課程名稱︰離散數學
課程性質︰資工系大一選修
課程教師︰呂育道
開課學院：
開課系所︰
考試日期（年月日）︰
考試時限（分鐘）： 180 mins
試題 :
1. Let G = (V,E) be a simple undirected graph. Show that |V | >= (1 +sqrt(1 +
8 * |E|) / 2
2. Let G=(V,E) be a connected graph with |E| = 17 and deg(v)>=3 for all
v ∈ V . Determine the maximum value for |V|.
3. Let G = (V,E) be a loop-free undirected graph with at least one edge. Prove
that G is bipartite if and only if χ(G) = 2.
4. A node v in a loop-free undirected graph G = (V,E) is called an articulatio
n
point if G v has more components than the given graph G. Let T = (V, E) be
a tree with | V | = n >= 3. Determine the largest number of articulation
points in T.
5. Prove that trees are planar.
6. Let (R, +, 뜩 be a ring with unity. Prove that the unity is unique.
7. Prove that a group G is abelian if and only if (ab)^{-1} = a^{-1}b^{-1} for
all a, b ∈ G.
8. In the group S_5, let α = (123)(4)(5) and β = (12)(354) be two permutatio
ns
Determine (βα)^{-1} and β^{-1}α^{-1} as cycle decompositions.
9. Let (G, 。), (G', 。'), and (G'', 。'') be groups. Suppose that f : G
→ G' and g : G' → G'' are homomorphisms. Prove that the function composition
g。f is a homomorphism. Recall that the composite function g。f is defined
as (g。f)(x) = g(f(x)) for x ∈ G.
10. Let f and h be permutations of S = {1,2,...n}. Then f and h are conjugate,
or f~h where ~ denotes the relation, if there exists a permutation g such
that g~f~g = h. Prove that conjugacy is an equivalence relation.
(You need to verify the property of reflexivity, symmetry, and transitivity.)