7.1 图的概念/Introduction of Graph 7.2 图的术语/Graph Terminology 7.3 图的表示与同构/ Representing Graph and Graph Isomorphism 7.4 连通性/Connectivity 7.5 欧拉道路与哈密尔顿道路/ Euler and Hamilton Paths 7.6 最短道路问题/Shortest Path Problem 7.7 平面图/Planar Graphs 7.8 图的着色/Graph Coloring

图 论 图/Graph： 可直观地表示离散对象之间的相 互关系，研究它们的共性和特性，以 便解决具体问题

021年2月24日 Deren Chen, Zhejiang Univ. 2 [定义1]相关/relative:按照某种规则，确定二个对象或 多个对象之间有关系，称这二个对象或多个对象是相关的。 注意:相关性与指定的规则有关。 (1)扑克牌中的方块ｋ与梅花ｋ 同花关系：不相关 同点关系：相关 (2)父子二人 同辈关系：不相关

[定义1]相关/relative:按照某种规则，确定二个对象或多个对象之间有关系，称这二个对象或多个对象是相关的。注意:相关性与指定的规则有关

在实际应用中，往往不仅需要计数，而且要把各种情况都枚举出来。 一、 字 典序排 列/lexicographic ordering for permutation 定义:

定义1：n个元素的集合A中任意选择r个（r  n）进行排列称为A的一个r-排列/r-Permutation定理1： n个元素的集合A的r-排列数为n(n-1)(n-2)…(n-r+1)

4.1 基本计数原理 The Basic of Counting 4.2 包含与排斥原理 The Inclusion-Exclusion Principle 4.3 鸽洞原理 The Pigeonhole Principle

[定义]相关:按照某种规则，确定二个对象或多个对象之 间有关系，称这二个对象或多个对象是相关的。 注意:相关性与指定的规则有关。 (1)扑克牌中的方块ｋ与梅花ｋ 同花关系：不相关 同点关系：相关 (2)父子二人 同辈关系：不相关

数学归纳法的公式表示： [P(1) ∧ m(m  1 ∧ P(m) → P(m+1))] →  n P(n) 1、归纳基础：P(1) 2、归纳步骤： m (m  1 ∧ P(m) → P(m+1))

证明的构造/形式：由两个部分组成 1、公理、假定或前提/axiom、postulate、hypotheses 2、推理规则/rule of inference 其它：引理/lemma、推论/corollary、猜想/conjecture一些基本概念