当前位置：文档之家 › 图论课件

图论课件

  • 格式：ppt
  • 大小：511.50 KB
  • 文档页数：46

下载文档原格式

  / 46

合集下载

图论-总结PPT课件

图论-总结PPT课件
degu + degv≥p-1，
则G是连通的。[这个定理是一个充分条件]
定理3 设G=(V,E)是至少有一个顶点不是弧立顶 点的图。若对任意v∈V，degv为偶数，则G中 有回路。
定理4 若图G中的两个不同顶点u与v间有两条不 同的路联结，则G中有回路。
.
6
例1 若G是一个恰有两个奇度顶点u和v的无向图，则 G连通G+uv连通。
(1) 若Δ(G)=δ(G)=3，则称3-度正则图,也叫做三次 图。
(2) 若Δ(G)=δ(G)=0，则称为零图，即0-度正则图。 (3) 若Δ(G)=δ(G)=p-1，则称为p-1度正则图，即
degv=p-1。 (4) p-1度正则图也称为p个顶点的完全图，记为Kp。
在Kp中，每个顶点与其余各顶点均邻接。 显然，Kp有p(p-1)/2条边。
则G是一个哈密顿图。 定理3 设G是一个有P个顶点的图，若对G的每 一对不邻接的顶点u和v，均有degu+degv≥p1，则G有哈密顿路。 (书上习题)
.
11
习题
例1(1) 证明具有奇数顶点的偶图不是哈密顿图；用
此结论证明如图所示的图不是哈密顿图。 (2) 完全偶图Km,n为哈密顿图的充要条件是什么？
例2 设G是一个(p,q)无向图,若q>(p-1)(p-2)/2，则G 是连通的。
例3 设G是一个(p,q)无向图,若δ(G)≥[p]/2,则G是连 通的。
例4 证明：若G不连通，则GC是连通图。 例5 设G是有个p顶点，q条边的无向图，各顶点的度数 均为3。则
(1)若q=3p-6,证明:G在同构意义下唯一，并求p,q。 (2)若p=6，证明:G在同构的意义下不唯一。
例2 试求Kp中不同的哈密顿圈的个数。 例3 给出一个10个顶点的非哈密顿图的例子，使得每 一对不邻接的顶点u和v，均有degu+degv≥9。 例4证明：彼德森图不是哈密顿图。 例5图G是哈密顿图。试证明：若图中的哈密顿回路中 含边e1，则它一定同时也含e2。 例9菱形12面体的表面上有无哈密顿回路？ 例10设G=(V,E)是连通图且顶点数为p,最小度数为δ， 若p>2δ,则G中有一长至少为2δ的路。

图论4-6-平面图ppt课件

图论4-6-平面图ppt课件
•图论4-6-平面图
证明 假设K3,3图是平面图。
在K3,3中任取三个结点，其中必有两个结点不 邻接，故每个面的次数都不小于4， 由4r≤2e，r≤e/2，即 v-e+e/2≥v-e+r=2， v-e/2≥2， 2v- e ≥ 4， 2v4≥e。
在K3,3中有6个结点9条边， 2v-4=2×6-4=8<9,与 2v-4≥e 矛盾， 故 K3,3不是平面图。
整理后得: e≤3v – 6
本定理的用途:判定某图是非平面图。
说明：这是简单 图是平面图的必 要条件。 •图论4-6-平面图
例如：K5中e=10，v=5，3v-6=9，从而e>3v-6， 所以K5不是平面图。
定理4.6.3的条件不是充分的。如K3,3图满 足定理4-6.3的条件（v=6，e=9，3v-6=12， e≤3v-6成立），但K3,3不是平面图。 证明K3,3图不是平面图。
例如图
deg(r1)=3 deg(r2)=3 deg(r3)=5 deg(r4)=4 deg(r5)=3
deg(r1)+deg(r2)+deg(r3)+deg(r4)+deg(r5)
=18
•图论4-6-平面图
3.定理4-6.1 设G为一有限平面图，面的次数之 和等于其边数的两倍。 证明思路：任一条边或者是两个面的共同边界 （贡献2次），或者是一个面的重复边（贡献2次）
•图论4-6-平面图
一、平面图 1、定义4-6.1 如果无向图G=<V,E>的所有结点和边 可以在一个平面上图示出来，而使各边仅在顶点处 相交。无向图G称为平面图，否则称G为非平面图。
有些图形从表面看有几条边是相交的，但是不 能就此肯定它不是平面图，例如，下面左图表面看 有几条边相交，但如把它画成右图，则可看出它是 一个平面图。

图论课件-PPT课件

图论课件-PPT课件

学习方法
目的明确
态度端正 理论和实践相结合
充分利用资源
逐步实现从知识到能力到素质的深化和
升华
课程考核
平时成绩 （30%-40%）
闭卷考试 （60%-70%）
图论模型
为了抽象和简化现实世界，常建立数学模型。图是关 系的数学表示，为了深刻理解事物之间的联系，图 是常用的数学模型。 (1) 化学中的图论模型 19世纪，化学家凯莱用图论研究简单烃——即碳氢 化合物 用点抽象分子式中的碳原子和氢原子，用边抽象原子间 的化学键。
E={w1r1, w1r2, w2r2, w2r3, w2r4, w3r3, w3r5}代表每个仓库和每个 零售店间的关联。则图模型图形为： w1 w2 w3
r1
r2
r3
r4
r5
29
(3) 最短航线问题 用点表示城市，两点连线当且仅当两城市有航线。为了 求出两城市间最短航线，需要在线的旁边注明距离值。 例如：令V={a, b, c, d, e}代表5个城市} E={a b, ad, b c , be, de}代表城市间的直达航线 则航线图的图形为： a 320 500 d 370 b 140 430 e c

图论学科简介 （2）
19世纪末期，图论应用于电网络方程组
和有机化学中的分子结构 20世纪中叶，由于计算机的发展，图论 用来求解生产管理、军事、交通运输、 计算机和网络通信等领域中的离散性问 题 物理学、化学、运筹学、计算机科学、 电子学、信息论、控制论、网络理论、 社会科学、管理科学等领域应用
七桥问题
近代图论的历史可追溯到18世纪的七桥问题:
穿过Kö nigsberg城的七座桥，要求每座桥通过 一次且仅通过一次。

图论第一章课件

图论第一章课件

返回 结束
• • • •
有限图：顶点集和边集都是有限集。 无限图：顶点集或边集是无限集。 平凡图：只有一个顶点的图。 空 图：边集为空集的图。 常将 G (V (G), E(G), G ) 简记为G (V (G), E (G)) 或 G (V , E )
或 G 。 特别对简单图 G , 将Ψ G(e)=uv 简记为 e = uv 。
如：例1中五个人的朋友关系所对应的图为 G (V (G), E(G), G ), 其中 点集合——人 边集合——朋友关系
G (e1 ) x1 x5 , G (e2 ) x1 x2 , G (e3 ) x2 x5 , G (e4 ) x3 x4 , G (e5 ) x1 x4
例2 G (V (G), E(G), G ) ，其中
e3 x1 e4
x3
e1
e2
x2
e5
返回 结束
在图 G (V (G), E(G), G ) 中，若 G (e) uv ，就称 e 连接顶 点 u , v ；称 u , v 是 e 的端点； 也称 u 和 v 相邻， 同时也称 u （ 或 v ）与 e 关联。 与同一个顶点关联的若干条边称为是相邻的（如例2中 的 e1 , e5 ）；两个端点重合为一个点的边称为环（如例2中的 e3）； 关联于同一对顶点的二条或二条以上的边称为多重边(如例2中 的 e1 , e2 ) 。 若图没有环和多重边，则称该图为简单图。
拉姆瑟（F.P.Ramsey）在1930年证明了这个数 r(k,t)是存 在的，人们称之为 Ramsey数。
1847年基尔霍夫运用图论解决了电路理论中求解联立方程 的问题，引进了“树”概念。 1857年Cayley非常自然在有机化学领域发现了一种重要的 图，称为“树”，解决了计算饱和氢化物同分异构体的数目。 1936年,哥尼格的第一本图论专著问世,才使得图论成为一 门独立的数学学科.

图论课件第三章图的连通性

图论课件第三章图的连通性

Bellman-Ford算法
总结词
Bellman-Ford算法是一种用于查找带权图中单源最短路径的算法。
详细描述
Bellman-Ford算法的基本思想是从源节点开始，通过不断更新节点之间的距离，逐步找到从源节点到 其他节点的最短路径。该算法可以处理带有负权重的边，并且在图中存在负权重环的情况下也能正确 处理。
THANKS
感谢观看
Floyd-Warshall算法
总结词
Floyd-Warshall算法是一种用于查找所有节点对之间最短路 径的动态规划算法。
详细描述
Floyd-Warshall算法的基本思想是通过动态规划的方式，逐 步构建最短路径矩阵。该算法首先初始化一个距离矩阵，然 后通过一系列的转移操作，逐步更新距离矩阵，直到找到所 有节点对之间的最短路径。
欧拉回路
总结词
欧拉回路是指一个路径的起点和终点是同一点，且经过图中的每条边且仅经过 一次的路径，并且该路径闭合。
详细描述
欧拉回路是欧拉路径的一种特殊情况，它不仅满足欧拉路径的所有条件，而且 起点和终点是同一点，形成一个闭合的路径。在图论中，欧拉回路具有重要的 应用价值。
欧拉回路的判定
总结词
判断一个图是否存在欧拉回路是一个NP 难问题，目前没有已知的多项式时间复 杂度的算法。
连通度
总结词
连通度是描述图中任意两点之间可达性的度量，表示图中节点之间的连接紧密程度。
详细描述
在图论中，连通度是衡量图连通性的一个重要参数。对于一个无向图，连通度通常用K表示，表 示图中任意两点之间是否存在路径。对于有向图，连通度分为入度和出度，分别表示从一个节 点到另一个节点是否存在路径和从另一个节点到这个节点是否存在路径。

图论课件

图论课件

例 图为k=4 (τ=24=16 ) 的德 · 布鲁因图及相应的欧拉有向 a 闭迹及相应的德 · 布鲁因序列。
000
弧
a = (0000) b = (0001) c = (0010) d = (0101) e = (1010) f = (0100) g = (1001) h = (0011) i = (0110) j = (1101) k = (1011) l = (0111) m= (1111) n = (1110) p = (1100) q = (1000)
例
例 某博物馆的一层布置如下图，其中边代表走廊，结点e是 入口，结点g是礼品店，通过g我们可以离开博物馆。请找出 从博物馆e进入，经过每个走廊恰好一次，最后从g处离开的 路线。 d
j i e h g b a
c
f
解 图中只有两个奇度顶点e和g，因此存在起点为e，终点 为g的欧拉迹。
d
为了在G中求出一条起点 为e，终点为g的欧拉迹， 在e和g间添加一条平行边 m，如图
反之，设G是恰有两个奇点u和v的连通图。 在u和v间添加新边e得图G+e，则 G+e没有奇点。 由已证结论， G+e有Euler闭迹， 从而G有Euler迹。 综上，结论成立。 注： (1) 图G有欧拉迹当且仅当G能“一笔画”。
(2) 若奇度点数为零， 则一笔画与起点无关； 若奇度
点数为2，则一笔画的起点与终点均为奇点。 例 在平面内，右图是 否可以在三笔之内 画成？
1 0 0 0
1
1
0
1
德· 布鲁因序பைடு நூலகம்的构造
步骤1 构造一个有向图H: 它的点是2k-1个不同的长度为 (k-1)的01序列。对点 v = (b1, b2,…,bk-1) ，用两条弧分别将v 连到点v1 = (b2, b3,…bk-1, 0) 和v2= (b2, b3,…,bk-1, 1)，得有向边 <v, v1>和<v, v2>。 步骤2 求H的欧拉有向闭迹， 由此得k部分序列 S1, S2,…, Sτ 和相应的德 · 布鲁因序列S。 注：(1) H 的每一点v，有d+(v) = d-(v) = 2且是连通的，从而 H是欧拉有向图，称为德 · 布鲁因图。 (2) H有2k条弧，若以每一条由点(b1,b2,…,bk-1)到点(b2,b3,…,bk) 的弧a代表一个k元组(b1, b2,…,bk)，便可得2k个不同的k元组。

图论课件第七章图的着色

总结词
平面图的着色问题是一个经典的图论问题，其目标是在满足相邻顶点颜色不同 的条件下，使用最少的颜色对平面图的顶点进行着色。
详细描述
平面图的着色问题可以使用欧拉公式和Kuratowski定理进行判断和求解。此外 ，也可以使用贪心算法、分治策略等算法进行求解。
树图的着色问题
总结词
树图的着色问题是一个经典的图论问 题，其目标是使用最少的颜色对树图 的顶点进行着色，使得任意两个相邻 的顶点颜色不同。
分支限界算法
总结词
分支限界算法是一种在搜索树中通过剪枝和 优先搜索来找到最优解的算法。
详细描述
在图的着色问题中，分支限界算法会构建一 个搜索树，每个节点代表一种可能的着色方 案。算法通过优先搜索那些更有可能产生最 优解的节点来加速搜索过程，同时通过剪枝 来排除那些不可能产生最优解的节点。分支 限界算法可以在较短的时间内找到最优解，
尤其适用于大规模图的着色问题。
03
图的着色问题的复 杂度
计算复杂度
确定图着色问题的计算复杂度为NP-完全，意味着该问题在多项式时间 内无法得到确定解，只能通过近似算法或启发式算法来寻找近似最优解 。
图着色问题具有指数时间复杂度，因为对于n个顶点的图，其可能的颜色 组合数量为n^k，其中k为每个顶点可用的颜色数。
02
图的着色算法
贪心算法
总结词
贪心算法是一种在每一步选择中都采取当前状态下最好或最优（即最有利）的选 择，从而希望导致结果是最好或最优的算法。
详细描述
贪心算法在图的着色问题中的应用是通过逐个对顶点进行着色，每次选择当前未 被着色的顶点中颜色数最少的颜色进行着色，直到所有顶点都被着色为止。这种 算法可以保证最小化使用的颜色数量，但并不保证得到最优解。

《图论的介绍》课件

添加副标题
图论的介绍
汇报人：
目录
PART One
添加目录标题
PART Three
图论的应用领域
PART Two
图论的基本概念
PART Four
图论的基本问题
PART Five
图论的算法和数据 结构
PART Six
图论的扩展知识
单击添加章节标题
图论的基本概念
图论的发展历程
18世纪末，欧拉提出“七桥问题”，开启了图论的先河
匹配问题
匹配问题定义：在图论中，匹配问 题是指在图中找到一组边，使得每 个顶点恰好有一条边。
最小匹配问题：在图中找到一组边， 使得边的数量最少。
添加标题
添加标题
添加标题
添加标题
最大匹配问题：在图中找到一组边， 使得边的数量最多。
完美匹配问题：在图中找到一组边， 使得每个顶点恰好有一条边，并且 边的数量最多。
图论的扩展知识
欧拉路径和欧拉回路
欧拉路径：通过图中所有边且仅通过一次的路径
欧拉回路：通过图中所有边且仅通过一次的回路
欧拉定理：一个无向图存在欧拉回路当且仅当每个顶点的度数都是偶数
应用：欧拉路径和欧拉回路在计算机科学、数学、物理等领域有广泛应用，如电路设计、网络 拓扑、图论算法等
哈密顿路径和哈密顿回路
应用
生物技术：图 论在生物工程、 生物制造和生 物能源等领域
的应用
图论的发展趋势和未来展望
应用领域：图 论在计算机科 学、物理学、 生物学等领域 的应用越来越
广泛
研究方向：图 论在算法设计、 网络优化、数 据挖掘等领域 的研究不断深
入
技术发展：图 论与机器学习、 深度学习等技 术的结合越来

运筹学--图论 ppt课件


4
5
4 9 8
v1
v3
2
v6
[8,v2]
v8
5 33
1
[2,v1]
v4
v7
[10,v4]
33
Dijkstra算法示例1
3）迭代计算(c)—更新与永久标号节点v2相连的节 (d2+w25=3+7=)10< ∞ (=d5) 点的临时标号。
[3,v1]
v2
[0,-]
7
v5
[10,v2]
2 [+∞,v1] 6
v4
v7
[+∞,v1]
22
Dijkstra算法示例1
2）迭代计算(a)—从临时标号中找到距离上界dk最 小的节点v4，d4=min{dk}，将其变换为永久编号。
[3,v1] [+∞,v1]
v2
[0,-]
7
v5
2 [+∞,v1] 6 1 2 [+∞,v1]
3
5 2 [5,v1]
4
5
4 9 8
v1
v3

最小树问题不一定有唯一解。
10
10
最小支撑树问题的解法

破圈法 算法


初始化 将图G的边按权值从大到小的次序排列，从 原图开始迭代； 迭代


第1步(删边) 从排列中顺序选择一条与图中剩余边构成圈 的边，则将此边从图中删除，进入第2步(结束判断)； 第2步(结束判断) 若图中剩下n-1条边，则已经得到最小支 撑树；否则，进入下一轮迭代，返回第1步(加边)；

柯尼斯堡七桥问题

柯尼斯堡市区横跨普雷格尔河两岸，在河中心有两 个小岛。小岛的两岸共有七座桥将岛与岛、岛与河 岸连接起来。一个人怎样才能一次走遍七座桥，每 座桥只走过一次，并最后回到出发点？

图论课件-图的因子分解

对于同一个图，可能存在多种不同的因子分解，如何找到最优的因 子分解是一个挑战。
因子分解的应用场景
虽然图的因子分解在理论计算机科学中有广泛的应用，但在实际应 用中，如何将理论应用于实际问题仍需进一步探索。
未来可能的研究方向和挑战
寻找高效算法
01
未来研究的一个重要方向是寻找更高效的算法来解决图的因子
分解问题。
04
图的因子分解的应用
在计算机科学中的应用
计算机网络
图的因子分解可以用于优化路由算法，通过将网络分解为 若干个连通子图，可以更有效地进行路由选择和流量控制 。
并行计算
在并行计算中，图的因子分解可以用于任务分配，将一个 大任务分解为若干个小任务，并分配给不同的处理器执行 ，从而提高计算效率。
数据挖掘和机器学习
一个图，其中任意两个不 同的顶点之间都恰有一条 边相连。
空图
一个图，其中任意两个不 同的顶点之间都无边相连 。
图的因子分解的重要性
理论意义
图的因子分解是图论中的重要概 念，它有助于深入理解图的性质 和结构。
应用价值
图的因子分解在计算机科学、运 筹学、电子工程等领域有广泛的 应用，如网络设计、电路优化等 。
资源配置和调度。
金融风险管理
在金融风险管理中，图的因子分 解可以用于识别和评估风险因素 之间的关联关系，从而更好地进
行风险管理和控制。
在网络设计中的应用
01
社交网络分析
在构和群体关系，
从而更好地理解社交行为的模式和规律。
02 03
推荐系统
在推荐系统中，图的因子分解可以用于用户兴趣分析和物品关联推荐， 通过将用户和物品之间的关系进行分解和分析，可以更有效地进行个性 化推荐。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

鸽巢原理（鸽舍原理、抽屉原理）
平均值总是介于最大值和最小值之间
如果对象多于kn的一个集合被划分为n个
类，则必有一个包含的对象多于k个
等价关系与同余 （1）
集合S上的一个等价关系是S上的一个关系
R,它对不同元素
满足 a) 自反性 ( x, x) R b) 对称性
x, y, z S
图论及其应用 Graph Theory and Its Applications
主要内容
图论前言
数学预备知识
前言
课程目标
学时和学分 教学大纲
教材和主要参考资料
课程考核
图论学科简介 （1）
图论是研究点与线组成的“图形”问题
的一门科学。图论是组合数学的一个分 支，它交叉运用了拓扑学、群论、数论 等学科，有时将其归为离散数学的一个 分支 属于应用数学分支 哥尼斯堡七桥问题 欧拉（1707~1782）：根据几何位置的 解题方法，这是图论领域的第一篇论文， 1736年， 被尊称为图论和拓扑之父
31
(5) 考试时间安排问题 一个教授需要对期末考试时间进行安排，使得学生们 不会有相互冲突的考试。如何解决？ 该问题可以建立一个图论模型来解决：待考的课程可 抽象为图的顶点，连接两个顶点的边表示至少有一个学生 同时选择了这两门课程。 问题归结于在模型图中求所谓的“顶点着色方案”问题， 该问题将在第六章讨论。 例如：有a, b, c ,d, e, f 六门课程。按照上面方法建立 的模型图如下：
学习方法
目的明确
态度端正 理论和实践相结合
充分利用资源
逐步实现从知识到能力到素质的深化和
升华
课程考核
平时成绩 （30%-40%）
闭卷考试 （60%-70%）
图论模型
为了抽象和简化现实世界，常建立数学模型。图是关 系的数学表示，为了深刻理解事物之间的联系，图 是常用的数学模型。 (1) 化学中的图论模型 19世纪，化学家凯莱用图论研究简单烃——即碳氢 化合物 用点抽象分子式中的碳原子和氢原子，用边抽象原子间 的化学键。
人员分派问题
最优匹配问题
第六章 着色问题
边色数
Vizing定理 点着色
色数
Brooks定理
围长和色数
第七章 平面图
平图和平面图
对偶图 Euler公式
Kuratowski定理
五色定理和四色猜想
平面性算法
第八章 有向图
有向图
有向路 有向圈

图论学科简介 （2）
19世纪末期，图论应用于电网络方程组
和有机化学中的分子结构 20世纪中叶，由于计算机的发展，图论 用来求解生产管理、军事、交通运输、 计算机和网络通信等领域中的离散性问 题 物理学、化学、运筹学、计算机科学、 电子学、信息论、控制论、网络理论、 社会科学、管理科学等领域应用
27
通过这样的建模，能很好研究简单烃的同分异构现象.
例如：C4H10的两种同分异构结构图模型为： h h h h h h h
h
h h h h
h
h
h hHale Waihona Puke h hhh28
(2) 商业中的图论模型
商业中，经常用图来对仓库和零售店进行建模
例如：令V={w1,w2,w3,r1,r2,r3,r4,r5}代表3个仓库和5个零售点
c) 传递性

(( x, y) R) (( y, x) R)
( x, y) R且( y, z) R ( x, z) R
等价关系与同余 （2）
x y mod n
对于“模n同余”是等价关系，其等
价类成为模n的余数类或者同余类， 所有的同余类构成的集合

n
/n
引理、定理、推论
引理（lemma) : 希腊语意为前提
定理 (theorem):希腊语意为待证的论题 推论 (corollary): 拉丁语，意为赠品，是
从定理或命题出发无需太多额外工作即 可得出的论断
归纳法原理一
对每个自然数，设P(n)是一个数学命题。
如果下面的性质a和b成立，则P(n)对每个 自然数n均为真 a) P(1)为真； b) 对于 k N ，如果P(k)为真，则 P(k+1)为 真；
32
a
c
b
d
e
f
一种可行的安排方案为：第一时间：a, d, e;第二时间： b, f ；最后：c. 另一种可行的安排方案为：第一时间：a, e;第二时间： c, d ；最后：b, f .
(6) 旅行售货员问题
一电脑代理商要从她所在城市出发，乘飞机去六个城市， 然后回到出发点，如果要求每个城市只经历一次，能否办 到？给出行走方案。
第九章 网络
流
割 最大流最小割定理
Menger定理

第十章 NP –完全问题
优化问题
P类和NP类 Cook定理
六个基本NPC问题
第十一章 图论的应用
图论在现代网络设计和流量分析中的应
用 图论在信息安全中的应用 图论在信号处理中的应用
教材和主要参考资料 （1）
请求出从d到c的最短路
30
(4) 任务分配问题 有一个旅行团要组织一批人去旅游，其中一些人是朋友 他们要乘坐公共汽车去，而车上的位子是成对的。因此 为了让大家旅途更愉快，旅行团负责人需要将成对的朋 友安排在一起。给出一种安排方案。
该问题可以建立一个图论模型来解决：旅行团的人抽象 为图的顶点，两个顶点连线，当且仅当两个顶点代表的 人是朋友。 问题归结于在模型图中求所谓的“匹配”，关于图的匹配 将在第五章介绍。
学时和学分
学时数 54
学分数 3
教学大纲 （共11章）
通过教学，使学生掌握该课程的基本理
论与方法，培养对离散对象的抽象思维 与解决实际问题的能力，并为学习相关 课程及将来从事科学研究创新和工程实 践奠定理论基础，及培养学生理论与实 践相结合的能力。
第一章 图的基本概念





归纳法原理二
对每个自然数，设P(n)是一个数学命题。如
果下面的性质a和b成立，则P(n)对每个自然 数n均为真 a) P(1)为真； b) 对于 ，如果对所有 t k P(t)为真，则 P(k+1)为真；
组合分析与计数
映射 双射
x
幂集、子集的个数计数
x
33
该问题可以建立一个图论模型来解决：城市抽象为 图的顶点，边代表城市间的直达航线。
问题归结为在模型图中寻求所谓的“哈密尔顿圈”问题。 将在第四章介绍。
例如：如果模型图如下： f e d c (2) h, d, e, c, a, b, h
34
a b
可行方案: (1) h, d, e, c, b, a, h
E={w1r1, w1r2, w2r2, w2r3, w2r4, w3r3, w3r5}代表每个仓库和每个 零售店间的关联。则图模型图形为： w1 w2 w3
r1
r2
r3
r4
r5
29
(3) 最短航线问题 用点表示城市，两点连线当且仅当两城市有航线。为了 求出两城市间最短航线，需要在线的旁边注明距离值。 例如：令V={a, b, c, d, e}代表5个城市} E={a b, ad, b c , be, de}代表城市间的直达航线 则航线图的图形为： a 320 500 d 370 b 140 430 e c
七桥问题
近代图论的历史可追溯到18世纪的七桥问题:
穿过Kö nigsberg城的七座桥，要求每座桥通过 一次且仅通过一次。
Euler1736年证明了不可能存在这样的路线。
四色问题
在日常生活中我们常常可以遇到组合数学的
问题。比如一个著名的世界难题“四色猜 想” ：一张地图，用一种颜色对一个地区着 色，那么一共只需要四种颜色就能保证每两 个相邻的地区颜色不同。
《图论及其应用》，孙惠泉，科学出版
社，2004年9月。 《图论导引》，Douglas B.West 著，李 建中、骆吉洲译，机械工业出版社， 2006年2月。 《图论及其应用习题解答》，张克民、 林国宁、张忠辅编，清华大学出版社， 1988年4月。
教材和主要参考资料 （2）
《图论及其应用》，J.A. 邦迪 及 U.S.R
0

数理逻辑 （1）
全称量词 存在量词 否定
(x S ) P( x)
(x S ) P( x)
合取
析取 条件命题
双条件命题
数理逻辑 （2）
条件命题 逆命题
QP
PQ
(P) Q
逆否命题：
Q P
数理逻辑 （3）
双条件命题
( P Q) (Q P)
默蒂，科学出版社。 （原书：Graph Theory with Applications, J.A. Bondy & U.S.R. Murty) 有最新扩容版，2008年 Springer出版的GTM丛书,GTM244 Graph Theory. Graph Theory, Reinhard Diestel，第四 版,Springer，有中文版，李学良等译.

图和简单图 同构 子图 顶点的度 路和连通性 圈 最短路问题
第二章 树
树
割边和键 割点
连线问题
第三章 连通度
连通度
块 可靠通信网建设问题
第四章 Euler环游和Hamilton圈
Euler环游
Hamilton圈 旅行售货员问题
第五章 匹配