[試題] 100-2 呂育道 離散數學 期末考
課程名稱︰離散數學
課程性質︰
課程教師︰呂育道
開課學院：
開課系所︰資工系
考試日期（年月日）︰2012/06/21
考試時限（分鐘）：三節課
是否需發放獎勵金：否
（如未明確表示，則不予發放）
試題 :
Note: You may use any result proved in the class.
Problem 1(10 points)
Prove that any two consecutive Fibonacci numbers are relatively prime.
The Fibonacci recurrence equation is
Fn+2 = Fn+1 + Fn with F0 = 0 and F1 = 1
Problem 2(10 points)
Solve the recurrence relation (An+2)^2 -5(An+1)^2 +4(An)^2 = 0,
where n >= 0 and A0 = 4, A1 = 13.
Problem 3(10 points)
If A0 = 0, A1 = 1, A2 = 4, A3 = 37 satisfy the recurrence relation
An+2 + b(An+1) + c(An) = 0, where n >=0 and b,c are constants,
determine b,c and solve for An.
Problem 4(5 points)
Can a simple graph exist with 15 vertices each of degree five?
Problem 5(10 points) _
If the simple graph G has v vertices and e edges, how many edges does G have?
Problem 6(10 points)
Prove that an acyclic digraph has at least one node of out-degree zero.
(An acyclic digraph is a directed graph containing no directed cycles.)
Problem 7(10 points)
If G =(V,E) is a loop-free undirected graph, prove that G is a tree
if there is a unique path between any two vertices of G.
Problem 8(5 points)
Give an example of an undirected graph G = (V,E), where |V| = |E| + 1 but
G is not a tree.
Problem 9(10 points)
If G is a group, let H = {a屬於G |ag = ga for all g屬於G }.
Prove that H is a subgroup of G. (The subgroup H is called the center of G.)
Problem 10(10 points)
Verify that ( Z*p ,‧)is cyclic for the primes p = 7 and 11.
Problem 11(10 points)
Prove that every group of prime order is cyclic.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.244.224