110年 - 110台灣聯合大學系統_碩士班招生考試_電機類:離散數學#104950

科目：研究所、轉學考(插大)◆離散數學 | 年份：110年 | 選擇題數：0 | 申論題數：17

試卷資訊

所屬科目：研究所、轉學考(插大)◆離散數學

選擇題 (0)

申論題 (17)

(a) [3 points! If ax61baddfc2d916.jpg ay (mod n), then x 61bade39829f7.jpgy (mod n).
(b) [3 points) If x 61bade39829f7.jpg y (mod n), then ax 61bade39829f7.jpg ay (mod n).
(c) [3 points) The set of integers and the set of prime nu umbers have the same cardinality.
(d) [3 points) If a relation is symmetric and transitive, then the relation is rellexive.

(e) [3 points] 61bade84b0578.jpg.
(f) [3 points] 5 dividesn5 - n whenever n is a positive integer.

(g) I points Given a,bent and gcdta, b61badece98083.jpgand gcd(a，b)≠ 1 , we cannot find an inverse of a modulo b in some cases.
(a) [6 points) Compute the expected number of vertices and edges that remain after the deletion process.
(b) I6 pointsI Based on Ca), ty to infer that for any graph with n vertices with nd/2 edges, there is an independent set with at least n/2d vertices.

3. A treed that never gave up on its dream to flourish. [10 points] Let T be a spanning tre

n edge cost function c. T is defined to have the cycle property if for any edge61bae08dc8373.jpg

the cycle generated by adding e' to T. Also, T is defined to have the cut property if for any edge 61bae0c97a43b.jpg

for all e' in the cut defined by e. Show that the following three statements are equiva

 1. T has the cycle property.
 2. T has the cut property.
 3. T is a minimun cost spanning tree.

4. Respect for the ancients. [8 points Find an integer x such that x61bae1337b257.jpg 1 (mod 3), x 61bae1337b257.jpg 3 (mod 7) and x61bae1337b257.jpg 9 (mod11).
5. Show time! (10 points] Prove that for every positive integer n, there are n consecutive composite integers. In other words, prove that we can find n consecutive composite integers for any n.
(a) [6 points] Prove that any Sprouts game consists of a finite number of moves before someone loses. In other words, the game will terminate eventually.
(b) [7 points] Show a tight upper bound on the worst -case number of moves in a Sprouts game that starts with n dots, and prove your answer.

7. Act together, we go far. [12 points) Suppose we have two isomorphic graphs G1 and H1, as well as two isomor- phic graphs G2 and H2. Prove or disprove tha61bae1b783c49.jpg are also isomorphic.

(a) [7 points] Use the recurrence tree method to solve the time complexity of recurrence T(n) = 3T(n/4]) + θ(n2) in theθ-notation.

(b)[7 points] Solve the time complexity of recurrence 61bae20fd06dd.jpg in the θ-notation without using Master method.