课程名称︰离散数学 课程性质︰资工系大一选修 课程教师︰吕育道 开课学院： 开课系所︰ 考试日期（年月日）︰ 考试时限（分钟）： 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.) --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 114.37.182.241 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NTU-Exam/M.1655311877.A.F41.html ※ 编辑: sN0w374625cS (114.37.182.241 台湾), 06/16/2022 00:52:18