課程名稱︰離散數學 課程性質︰電機系複選必修 課程教師︰陳和麟 開課學院：電機資訊學院 開課系所︰電機工程學系 考試日期（年月日）︰2018/06/29 考試時限（分鐘）：110 試題 : Please answer the following questions on the answer sheets provided. Be sure to write your name and student ID on all answer sheets you use. You may bring one A4-sized, hand-written, double-sided "cheat sheet". No other nooks, notes, or calculators may be used during the exam. If you want ti use any result or theorem that has been taught in class ( including homeworks), you may do so but you must state the result or theorem clearly before using it. Please read all problems first. No questions allowed after 13:50. Problem 1 1. (13%) Solve T(n) = 4T(n-1) - 3T(n-1) - 10, T(0) = 2, T(1) = 9 2. (12%) Solve nT(n) = (2n-2)T(n-1) + log2[n/(n-1)^2], T(1) = 2 Problem 2 Let R1 and R2 be two relations defined on set A = {1,2,3,4,5}. ┌ ┐ ┌ ┐ 1│1 0 0 0 0│ 1│1 1 0 0 0│ 2│0 1 0 0 0│ 2│1 1 0 0 0│ M_R1 = 3│0 1 1 0 0│ M_R2 = 3│0 0 1 1 1│ 4│0 1 0 1 0│ 4│0 0 1 1 1│ 5│0 1 1 1 1│ 5│0 0 1 1 1│ └ ┘ └ ┘ 1. Draw the Hasse diagram of R1. 2. Identify all maximal and minimal elements of R1. 3. Split A into equivalence classes of R2. 4. Compute R1。R2. (No explaination needed for problem 2.) Problem 3 1. (6%) Let R be an antisymmetric relation on A and R1 ⊆ R. Is R1 always antisymmetric? Prove your answer. 2. (8%) Let R be an relation on A such that R^3 ⊆ R. Is R^5 ⊆ R always true? Prove your answer. Problem 4 given two undirected graphs G1 = (V1, E1) and G2 = (V2, E2) such that ‧V1 = {v1,v2,v3,v4,v5,v6,v7,v8,v9} ‧E1 = {{vi,vj} | i - j ≡ 1 or -1 or 2 or -2 (mod 9)} ‧The adjacency matrix of G2 is ┌ ┐ u1│0 0 0 1 1 1 0 0 0│ u2│0 0 0 1 1 1 0 0 0│ u3│0 0 0 1 1 1 0 0 0│ u4│1 1 1 0 0 0 1 1 1│ M_G2 = u5│1 1 1 0 0 0 1 1 1│ u6│1 1 1 0 0 0 1 1 1│ u7│0 0 0 1 1 1 0 0 0│ u8│0 0 0 1 1 1 0 0 0│ u9│0 0 0 1 1 1 0 0 0│ └ ┘ 1. (3%) Is G1 isomorphic to G2? Prove your answer. You must either find the mapping function for an isomorphism or prove that a specific invariant is not preserved. 2. (3%) Does G2 have a Hamilton path? Prove your answer. 3. (9%) Suppose that we remove 4 edges from G1 and draw it on the plane without edge crossings. How many regions does the drawing have? List all the possible answers. Prove your answer. Problem 5 Prove the following stements or find counter examples (and explain your counter example breifly). 1. (18%) Let G be a simple undirected graph. κ(G) < n/2. If G is connected, then G must contain a simple path of length at least 2κ(G). (Hint: consider the longest simple path of G.) 2. (12%) Let G be a simple undirected simple graph. If G does not contain any subdivision of K3,3 as a subgraph, then G must be planar. --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.162.118.10 (臺灣) ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1562403693.A.083.html ※ 編輯: misomochi (1.162.118.10 臺灣), 07/06/2019 17:05:15