《离散数学》期末考试复习指导
期末考试仅限于期中考试以后的内容：Chapter 7 Trees; Chapter 8 Topics in
graph theory.
考试题型：计算题；简答题；证明题；构造图形（构造满足一定条件的图，如：
6个顶点，11条边且无Hamiltonian circuit）。题目共计6题，无选择题和填空题。
考试难度：基本与期中考试相同，有一定数量的题直接来自于习题，最后一题较
难（构造图形）。
复习要点：基本概念及定义：
rooted tree; binary tree; labeled tree; positional tree; tree
searching; undirected tree; weighted graph; minimal spanning tree;(undirected) graph; degree; Euler path and Euler circuit; Hamiltonian path and Hamiltonian circuit; matching function; coloring graph; chromatic number; chromatic polynomial; planar graph;
基本内容：
tree searching; the prefix (Polish form) and infix form of the
algebraic expreion; minimal spanning tree; the sufficient-neceary condition for a graph G to have Euler circuit (or path); coloring graph; chromatic number; chromatic polynomial; construct a graph (directed or undirected) subject to some given conditions.
不要求的内容：
Computer representation of binary positional tree; searching general tree; algorithms.
复习中如遇困难请联系：钱建国13178272231，jgqian@jingxian.xmu.edu.cn徐伟13599513903
陈美润13799279303
祝大家取得好成绩！
