《1第一章 图的基本概念.pptVIP

由以上三个特点可以看出, 图论与其它的数学分支不同,它不像群论、拓扑等学科那样有一套完整的理论体系和解决问题的系统方法.而且图论所研究的内容非常广泛, 例如图的连通性、遍历性、图的计数、图的着色、图的极值问题、图的可平面性等等. 欧拉简介 莱昂哈德·欧拉 (Leonhard Euler ，1707年4月5日～1783年9月18日)，瑞士数学家、力学家、天文学家、物理学家，变分法的奠基人，复变函数论的先驱者，理论流体力学的创始人. 他被一些数学史学者称为历史上最伟大的两位数学家之一（另一位是卡尔·弗里德里克·高斯） ??? 欧拉曾任彼得堡科学院教授，柏林科学院的创始人之一．他是刚体力学和流体力学的奠基者，弹性系统稳定性理论的开创人．他认为质点动力学微分方程可以应用于液体（1750）．他曾用两种方法来描述流体的运动，即分别根据空间固定点（1755）和根据确定的流体质点（1759）描述流体速度场．前者称为欧拉法，后者称为拉格朗日法．欧拉奠定了理想流体的理论基础，给出了反映质量守恒的连续方程（1752）和反映动量变化规律的流体动力学方程（1755）． ??? 欧拉在固体力学方面的著述也很多，诸如弹性压杆失稳后的形状，上端悬挂重链的振动问题，等等． ??? 欧拉的专著和论文多达800多种． 准备知识 一、集合 1. 集合的定义 集合没有精确的数学定义 直观理解：由离散个体构成的整体称为集合，称这些个体为集合的元素 常见的数集：N, Z, Q, R, C等分别表示自然数、整数、有理数、实数、复数集合 2. 集合的表示法 (1)．枚举法----通过列出全体元素来表示集合 (2)．描述法(特征法、谓词法)----通过概括集合元素的性质来表示集合 实例： 枚举法 自然数集合N={0,1,2,3,…} 描述法 S={x| x是实数，x2-1=0} 3. 元素与集合 (1) ．集合的元素具有的性质 无序性——元素列出的顺序无关 相异性——集合的每个元素只计数一次 确定性——对于任何元素和集合，都能确定这个元素是否为该集合的元素 任意性——集合的元素也可以是集合 (2)．元素与集合的关系——隶属关系：“属于”或者“不属于” ． 4 ．集合与集合之间的关系： 5 ．集合的运算 二、二元关系 1.有序积 定义1：由两个具体事物x和y,按照一定的顺序组成的二元组(二元偶对)称为有序对,记作x,y . 定义2：设A,B为集合,A与B的笛卡儿积记作A?B,且 A?B = {x,y| 任意x?A且任意y?B}. 定义3：设A,B为集合, A×B的一个子集叫做从A到B的二元关系. 当A=B时则叫做A上的二元关系. 注: 1.集合A到集合B上的一个二元关系是A中和B中有关系的元素的直观概念的形式化. 2.若R是A到B的一个二元关系,并且有序对 a,b是R中的元素,那么元素a和b有某种关系,记为aRb or a,b∈R. 2.无序积 定义4:设A,B是两个集合,由a∈A, b∈B所组成的无序对(a,b)构成的集合,称为A和B的无序积,记作:A?B ,即: A?B={(a,b)| 任意a∈A且任意b∈B} 无序积A?B的一个子集,称为A和B的一个二元关系.当A=B时,A和B的二元关系称为A上的二元关系. 3. 等价关系的定义 设R为非空集合A上的关系. 如果R是自反的、对称的和可传递的, 则称R为A上的等价关系. 设R是一个等价关系, 若x,y∈R, 称x等价于y, 记做x～y. 二、矩阵的定义 图中 d (v1) = 5 d (v2) = 4 d (v3) = 3 d (v4) = 0 d (v5) = 2 v1 v2 v3 v4 v5 例 注：该图中各点的度数之和等于14，恰好是边数7的两倍 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. （3）在图的图形表示中我们可以不给图的点和边标上符号，称这样的图为非标定（号）图，否则称为标定（号）图.非标定图实际上是代表一类相互同构的图. 不误解时我们也不严格区分标定图与非标定图. （4）判定图的同构是很困难的，属于NP完全问题.对于规模不大的两个图，判定其是否同构，可以采用观察加推证的方法. Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd.