离散数学GRAPH-1课件.ppt

离散数学 第四部分 图论 概述 引言 知识结构 第十四章 图的基本概念 第1节 图 14.1.1 无向图与有向图 14.1.2 简单图与多重图 14.1.3 顶点的度数与握手定理 引言 图论是离散数学的重要组成部分，是近代应用数学的重要分支。  人们常称1736年是图论历史元年，因为在这一年瑞士数学家欧拉（Euler）发表了图论的首篇论文——《哥尼斯堡七桥问题无解》，所以人们普遍认为欧拉是图论的创始人。  1936年，匈牙利数学家寇尼格（Konig）出版了图论的第一部专著《有限图与无限图理论》，这是图论发展史上的重要的里程碑，它标志着图论将进入突飞猛进发展的新阶段。  近40年来，随着计算机科学的发展，图论更以惊人的速度向前发展，有人形容说：真是异军突起，活跃非凡。其主要原因有二：其一，计算机科学的发展为图论的发展提供了计算工具；其二，现代科学技术的发展需要借助图论来描述和解决各类课题中的各种关系，从而推动科学技术不断地攀登新的高峰。  作为描述事务之间关系的手段或称工具，目前，图论在许多领域，诸如，计算机科学、物理学、化学、运筹学、信息论、控制论、网络通讯、社会科学以及经济管理、军事、国防、工农业生产等方面都得到广泛的应用，也正是因为在众多方面的应用中，图论自身才得到了非常迅速的发展。 例1：Konisberg七桥问题 能不能一次走遍所有的七座桥，而每座桥只准经过一次？ 例2：聚会问题 任意6人聚会中，必有3人彼此相识，或有3人彼此不相识 例3：INSTANT INSANITY We conclude this section by looking at a puzzle which has been popular recently, and which has been marketed under the name of ‘Instant Insanity’. It concerns four cubes whose faces are colored red, blue, green and yellow in such a way that each cube contains at least one face of each color; the problem is to pile these cubes up on top of each other in such a way that each of the four 4×1 sides of the resulting square prism shows a face of each color. INSTANT INSANITY INSTANT INSANITY INSTANT INSANITY INSTANT INSANITY 例4：旋转鼓问题 一个编码盘分成16个相等的扇面，每个扇面由绝缘体或导体组成，表示0和1两种状态，其中a,b,c,d四个位置的扇面组成一组二进制输出，如图所示。试问这16个二进制的序列应如何排列，才能恰好组成0000到1111的16组四位二进制输出，同时旋转一周后又返回到0000状态。 旋转鼓问题图论解法 知识结构 本部分主要包括图的基本概念（第十四章）、欧拉图与哈密顿图（第十五章）、树（第十六章）、平面图及图的着色（第十七章）、支配集、覆盖集、独立集与匹配（第十八章）。本部分的先行知识及各部分的关系如下图所示： 第十四章 图的基本概念 第1节 图 第2节 通路与回路 第3节 图的连通性 第4节 图的矩阵表示 第5节 图的运算 第1节 图 学习要求 1. 熟练掌握握手定理及其推论的内容及其应用。? 2. 掌握图同构的概念。? 3. 加深对简单图、完全图、正则图、子图、补图等概念的理解。 14.1.1 无向图与有向图 14.1.2 简单图与多重图 14.1.3 顶点的度数与握手定理 14.1.4 图的同构 14.1.5 完全图与正则图 14.1.6 子图与补图 14.1.1 无向图与有向图 无序积与多重集 无向图与有向图的定义及表示法 相关概念和规定 无序积与多重集 设A，B为任意的两个集合，称 {{a,b}|a∈A∧b∈B} 为A与B的无序积，记作AB. 　　为方便起见，将无序积中的无序对{a,b}记为(a,b),并且允许a=b.需要指出的是，无论a,b是否相等，均有(a,b)=(b,a),因而AB=BA. 　　元素可以