Discrete mathematics and its application detailed explanation of exercises in the final exam of spring and summer semester of 2018-2019 academic year

One 、 Judgment questions

2. Be careful transitive The equivalent condition of is R To any n establish , Not equal .

【 review 】transitive Related conditional transformations

① seek transitive closure:Warshall's Algorithm

② prove transitive, Using equivalence conditions ：R To any n establish .

5. The expression of this question is quite special , Access vertex degree Equality is for every vertex . stay weakly connected Under the circumstances , There is no fixed point that can only enter or exit . Combined with mathematical induction , It is easy to prove that such a graph is strongly connected Of .

6. The definition of a tree ：connected simple graph, And e=n-1, non-existent cycle.

7. Such questions can be divided into sections for discussion . such as (2n,2n+1） This proposition can be denied .

Two 、 Completion

5. Be careful partial ordering and equivalence relation Are reflexive (reflexive) Characteristics , But the corresponding diagram sometimes omits it , Can't ignore it .

6. Follow the isomer method .

7. Compare first 、 Observe A The location of , Find out A Root node . according to inorder traversal Result , Find out D,B,E Form a left subtree ,C,F Form a right subtree , And then the results of two traversals , Judge the relative position of the vertices in the subtree .

8. Calculation equivalence relation, The classification criteria are equivalence classes . It can be 1 individual 、2 One and 3 Equivalent classes , Just discuss in turn .

Calculation partial ordering, In addition to reflexivity requirements , You can draw a diagram to discuss .

This topic has 3 Elements , It can be divided into the following categories ：（ The diagram only shows the case of different elements ,directed edge a->b Express a≤b, Draw... First 3 A little bit ）

① No, directed edge, That is, any two different elements are incomparable Of ：1 Kind of .

② One directed edge：6 Kind of （ Choose... First start point, Choose again endpoint,3×2＝6 Kind of ）.

All of the following are 2 strip directed edge:

③ Starting from a vertex , Send a... To each of the other two vertices directed edge：3 Kind of .

④ From the two vertices to the third vertex directed edge ：3 Kind of .

⑤ formation “ chain ”： Such as a->b->c（ notes ：a->c From transitivity we can get ）,6 Kind of .

9. Don't ignore empty sets and sets themselves .

10.Dijikstra Algorithm.

3、 ... and 、 Calculation questions

3.②③ Are the use of the principle of inclusion and exclusion （ understand ： Put the coins in the box , Can be seen as onto function Model of ）

④ Select box 、 Coin grouping 、 Sort , Applying the principle of multiplication .

⑤ The coins are identical , Belong to r-combination with repetition allowed（ It's actually the partition method ）

⑥ Be careful r-combination with repetition allowed The premise is that there is no limit on the number of boxes , and exactly six boxes are empty It is required that each of the three selected boxes has at least one coin .

so ： First step ： Select box

After selecting the box , Put a coin in each box , Reuse r-combination with repetition allowed In order to avoid repetition and leakage .

6.③ Notice that it's not Hamilton graph Why :Delete vertice V3 makes 2 components.

7.（1） prove e And v Inequality of relation , Generally, Euler formula and degree of region.

（2） Note that the latter question can take advantage of the conclusion of the former question ; Use the method of counter evidence to prove the contradiction .

（3）① A relatively unfamiliar problem of proof , It is common to use inductive method or counter evidence method . There is no obvious contradiction in the method of proof to the contrary , Consider trying induction , Sum up the number of vertices .

② The key to induction is to find out from n-1 To n The transition conditions of , Transition conditions should be known from the subject information 、 Let's start from the previous questions . Note that containing no triangles It can be concluded that .