101年 - 101 國立嘉義大學_碩士班(甲組)招生考試試題_資訊工程工程學系：離散數學#146266

(a) Pre-order (5%)

(b) In-order (5%)

(c) Post-order (5%)

(d) Depth-first traversal (5%)

(e) Breadth-first traversal (5%)

2 . Find the number of spanning trees in the graph G of Figure 2. (25 %)

3. Show that there are at least six different ways to choose three numbers from 1 to 10 so that all choices have the same sum. (10%)

(1) Find the probability (given reason for formula you use) of what a number is selected at random from 1000 to 9999, and the sum of the digits of the number is exactly 9. (10%)

(2) Given that the number has no zero digit, repeat (1). (10%)

(a) Is RA a reflexive relation? (2%)

(b) Is RA an irreflexive relation? (2%)

(a) How many different binary relations on A are there? (4%)

(b) How many binary relations on A are reflexive? (4%)

(c) How many binary relations on A are antisymmetric? (4%)

(d) How many binary relations on A are both reflexive and anti-symmetric? (4%)