哈工大 集合与图论 讲义.doc

第一篇 集合论 集合论是德国数学家康托（Contor）在1874年建立的，它是现代数学的基础，当今数学中的每个对象本质上都是集合。有时我们说：“数学能嵌套在集合论中”其含义就是指数学的一些对象如数、函数、线、面等都可以用集合来定义。换句话说，数学的各个分支在本质上都是研究这种或那种对象的集合。例如：几何学是研究点、线、面的集合；数学分析是研究函数的集合；代数学是研究数的集合以及在此集合上有关运算的集合等。因此，我们把集合论作为现代各种数学的基础是有道理的、合适的。集合论也是计算机科学的重要工具。集合论在程序设计、数据结构、形式语言、操作系统等计算机科学中，都有重要应用，成为计算机科学工作者必不可少的基础知识。计算机科学领域中的大多数基本概念和理论，几乎均采用集合论的术语来描述和论证。集合论主要有以下几个特点：第一、 第一、 它所研究的对象十分广泛。例如数、图形或其它任何客体作为对象。第二、 第二、 因为它研究的对象是如此广泛，为了便于研究，就必须寻找对象的共性。而要做到这一点，就必须进行抽象。第三、 第三、 在抽象化的基础上，可以用统一的方法来研究和处理集合论中的各种问题。总之，集合论的主要特点是研究对象的广泛性，分析思考问题的抽象性和处理问题的统一性。正是这些特点，使我们便于用它来描述和研究离散对象及其关系。第一章 集合及其运算基本要求1. 1. 掌握集合、子集、全集、空集和幂集等概念。熟悉常用的表示集合的方法以及用文氏图来表示集合的方法。能够判定元素与集合、集合与集合之间的关系；熟练掌握两个集合相等关系和包含关系的定义和性质，能够利用定义证明两个集合相等。2. 2. 熟练掌握集合之间的各种运算以及集合运算的基本等式，能够利用它们来证明更复杂的集合等式。3. 3. 掌握余集与集合笛卡儿乘积的概念以及De Morgan公式。4掌握求解与有穷集合计数相关的实际问题。1.1 必备知识和考试要点1.1.1基本定义 集合是一个不能精确定义的数学概念。一般地说，把一些确定的、可以区分的事物放在一起组成的一个整体称为集合，简称集。组成一个集合的每个事物称为该集合的元素，或简称一个元。 若a是集合A的一个元素，就称a属于A，或称a在A中，记为aA。若a不是集合A的一个元素，就称a不属于A，或称a不在A中，记为aA。集合的概念很简单，但准确理解其含义却非易事，特别应注意下列几点：第一、 第一、 集合的元素可以是任何的事物，既可以是具体的事物，也可以是抽象的事物；还可以是另外的集合，但构成这个集合的元素决不能是这个集合的自身。第二、一个集合的每个元素是可以互相区分的。这意味着在集合中不会重复出现相同的元素。第三、组成一个集合的各个元素在该集合中是无次序的。第四、任一事物是否属于一个集合，回答是确定的。也就是说，对一个集合来说，任一事物或者是它的元素或者不是它的元素，二者必居其一且不可兼而有之，而且结论是确定的。今后，我们常用不同的大写的字母表示不同的集合，而且不的小写字母表示集合中不同的元素。但是因为某个集合的 可能是令一个集合，所以这种约定不是绝对的。在本书规定用几种特定的字母表示几个常用的集合。约定：N表示全体自然数组成的集合；I表示全体整数组成的集合；I+表示全体正整数组成的集合；Q表示全体有理数组成的集合；Q+表示全体正有理数组成的集合；R表示全体实数组成的集合； R+表示全体正实数组成的集合；C表示全体复数组成的集合；通常用两种方法表示一个集合。一种方法是外延表示法，即把集合中的全部元素一一列举出来，元素之间用逗号隔开，并把它们用花括号括起来。例1 集合A中有五个元素1，2，3，4，5。则A=1，2，3，4，5一般说来，一个集合仅含有少数的几个元素时才可用这种方法给出。即使是有限个但数量较大，原则上这种方法也是可行的，然而实际上，很少能把全部的元素列出。不过当列出几个元素后就可以看出组成该集合的其他元素的规律时，也可采用此方法只列部分元素，其余用“”表示。例2 由26个小写英文字母组成的集合就可表示成a，b，c，x，y，z利用此方法可以表示含有无穷多个元素的集合。例3 自然数集合N=1，2，3，用上述方法表示集合并不是永远可能的。例如，区间0，1中的所有实数之集就不能用这种方法给出。另一种方法是内涵表示法，即用集合中的元素的共性来刻画集合。例4 上述集合A和N可以分别表示成A=xx是整数且1x5，N=xx是自然数。例5 所有的正偶数形成的集合可以表示成xx=2n，nI+例6 a，b上的所有连续函数形成的集合可以表示成f(x)f(x)在a,b上连续。集合还有其他的表示方法，但上述两种方法是常用的。原则上能简单、准确而且易于被大家所公认的方法都是可以使用的。例如0，1区间上的所有实数构成的集合就可简单地用0，1表示。定义1 不含任何元素的集合称为空集，记为。定义2 在给定的问题中，所考虑的所有事物的集合称为全集，记为S。 全集是一个相对的概念。由于所研究的问题不同，所取的全集也不同。定义3 设A，B是两个集合，若集合A中的每个元素都是B的元素，则称A是B的子集合，简称子集。这时我们说A包含在B里，或B包含A。 A是B的子集，记为AB或BA。定义4 设A，B是两个集合，若AB，xB使得xA，则称A是B的真子集，记为AB。定义5 设A，B是两个集合，若AB且BA。则称A与B相等。定义5 以集合为元素的集合称为集族。定义6 设A，B是两个集合，至少属于集合A与B之一的一切元素构成的集合A与B的并集，记为AB。定义7 设A，B是两个集合，由既属与A又属于B的一切元素构成的集合称为A与B的交集，记做AB。定义8 设A，B是两个集合，若AB=，则称A与B不相交，若集合A1，A2，An的任意两个集合Ai与Aj（ij）不相交，则称A1，A2，An，是两两不相交的集序列。定义9 设A，B是任意两个集合，由属于A但不属于B的一切元素构成的集合称为A与B的差集，并记为AB。定义10 设A，B是任意两个集合，AB与BA的并集称为A与B的对称差，记为AB定义11 设S是一个集合，AS，差集SA称为集A对S的余集。定义12 设A和B为任意两个集合，则集合（a，b）|aA且bB称为A与B的笛卡儿乘积，记为AB。定义13 设A1，A2，An，（n2）为n个集合，集合（ A1，A2，An）|AiAi，i=1，2，n称为A1，A2，An的笛卡儿乘积，并记为A1A2A3An，或者简记为。定义14 设A和B是两个集合，若有一个法则使xA，根据法则在B中有唯一的一个y与x对应，这个y常记为(x)；而且yB，在A中也有唯一的x 使x在下对应于y。这个法则称为从A到B的一个一一对应（一对一配对无余的方法）。定义15 一个从集合A到集合B的一一对应是AB的子集使之满足：（1）xA，存在yB使（x，y）；若（x，y），(x，z) ，则y=z。（2）yB，存在xA使（x，y）；若（x，y），(x1，y) ，则x= x1。若（x，y），则把 y记为(x)，即y=(x)。定义16 集合A称为有限集，若A=或者A且存在一个自然数n使得A与集合1，2，n间存在一个一一对应。数n称为A的基数，A的基数记成|A|。空集的基数定义为数0。若A不是有穷集，则称A为无穷集。定义17 若A 与B的一个真子集间有一个一一对应存在，但A与B之间不存在一一对应，则称|A|小于|B|，记为|A|n，则单射个数0， 若mn，从Y中任取m个元素有方法，此m个元素与X中m个元素有m!种不同的双射，所以共有单射m!种。（3）在Y上的定义n个性质，满足各性质的中映射之集，分别记为。若，则称f不具有性质，于是。在这里不以为函数值，则；不以与为函数值，则。例3 设，证明（1）（2）（3）（4）分析：本例题是书上的定理，但定理的结果和证明的方法很重要，因此在此处列出来。证明这样的问题主要利用“”的定义及映射的定义，采用按定义证明方法来证明。证：（1）设，则使得。于是，。因此，所以，故反之，设，则。于是或，使得。因此不论何种情况都，使得。因此，故因此，（2）设，则，使得。于是，且。从而，且，所以，故（3）设，则但。于是使得，且，从而，使得。故，即。 （4） 说明：（1）注意，两个集合的交的象不一定与它们的象的交相重合。（2）例设，。令。于是。但是。这表明。，于是。又，而。于是，。（3）定理1和定理2可以推广到有穷多个或无穷多个集合的并与交集的情况。第三章 关 系基本要求1 1 掌握二元关系的形式定义及其几个等价定义，掌握关系的各种表示方法：序对、矩阵、关系图等；能正确使用集合表达式、关系矩阵、关系图等给定的关系，并要求能够从一种形式写出另一种形式。2 2 掌握关系的各种运算，包括集合运算及关系合成和关系的逆运算。3 3 熟练掌握二元关系的各种特殊性质：自反、反自反、对称、反对称和传递等，并理解这些性质是如何反映在关系图上和关系矩阵上等。4 4 掌握二元关系的闭包的定义和简单性质，掌握各种闭包的构造形式及其证明，并能够求出有限集合上的二元关系的各种闭包。5 5 熟练掌握等价关系的概念，并掌握划分、等价类、商集的定义和基本性质，掌握等价关系与划分之间的关系。6 6 熟练掌握偏序关系、偏序集、全序、全序集等概念以及偏序集的极大元、极小元、最大元、最小元、上界、下界、上确界、下确界等概念；能画出有限偏序集的Hasse图，并根据图讨论偏序集的某些性质。3.1必备知识和考试要点3.1.1基本概念定义1 设A，B是两个集合，一个从AB到是，否的映射R，称为从A到 B的一个二元关系，或A与B间的一个二元关系。（a，b）AB，若（a，b）在R下的象为“是”，则称a与b符合关系R，记为aRb；若（a，b）在R下的象为“否”，则称a与b没有或不符合关系R，并高为（a，b）R。若A=B，则称R为A 上的二元关系。定义2 设A，B是两个集合，AB的任一子集R称为从A到B的一个二元关系。若（a，b）R，则称a与b符合关系R，并记为aRb；若（a，b）R，则称a与b不符合关系R，并记为（a，b）R。若A=B，则称R为A 上的一个二元关系。定义3设RAB，集合xxA且yB使得（x，y）R称为R的定义域，并记为dom(R)；而集合yyB且xA使得（x，y）R称为R的值域，并记为ran(R) 。定义4 设A，B是集合，一个从A到2B的映射R称为从A到B的一个多值部分映射。若aA，R(a)= ，则称R在a 无定义；而R(a)，则bR（a），b称为a在R下的一个象或值。定义5 一个从A到B的多值部分映射R称为A到B的一个二元关系。定义6 设A1，A2，An是n 个集合，A1A2An的子集R称为A1，A2，An间的一个n元关系，每个Ai称为R的一个域。定义7 设R为X上的二元关系，若xX，（x，x）R，则称R是X上的自反的二元关系，或自反的。定义8 设R为X上的二元关系，若xX，（x，x）R，则称R是X上的反自反的二元关系，或反自反的。定义9 设R为X上的二元关系，x，yX，若（x，y）R，有（y，x）R，则称R是X上的对称的二元关系，或对称的。定义10 设R为X上的二元关系，x，yX，若（x，y）R且（y，x）R，有x=y则称R是X上的反对称的二元关系，或反对称的。定义11 设R为X上的二元关系。x，y，zX，若（x，y）R且（y，z）R，有（x，z）R，则称R为X上的传递二元关系关系，或传递的。定义12 集合X上的二元关系R称为是相容关系，若R是自反的且又是对称的。定义13 设R为A到B的二元关系，则R的逆记为R-1，R-1是B到A的二元关系且R-1=（y，x）（x，y）R定义14 设R是A到B，S是B到C的二元关系。R与S的合成是A到C 的一个二元关系，记成RS ，且RS =（x，z）(x，z )AC且yB使得（x，y）R且（y，z）R 。定义15 设R是X上的一个二元关系，若存在一个关系R1满足下列性质：（1） （1） R1是自反的（对称、传递）。（2） （2） RR1（3） （3） 对于X上的一切包含R的自反关系R2，有R1R2。则称R1是自反（对称、传递）闭包。定义16 设R为X上的一个二元关系。X上包含R的所有自反且传递的二元关系的交称为R的自反传递闭包，记为。R定义17 设B为X上二元关系 R的矩阵，则（1） （1） R是自反的，当且仅当B的对角线上的全部元素都为1；（2） （2） R是反自反的当且仅当B的对角线上的全部元素都为0；（3） （3） R是对称的当且仅当B是对称矩阵；（4） （4） R是反对称的当且仅当bi j与 bj i不同时为1 ，ij ；（5） （5） R是传递的当且仅当若bi j=1且 bj k=1，则 bi k=1 ； （6） R-1的矩阵是BT定义19 设A，B，C为nn布尔矩阵，则（1） （1）AB=BA，AB=BA；（2） （2）（AB）C=A（BC）；（AB）C=A（BC）；（AB）C=A（BC）；（3） （3）A（BC）=（AB）（AC）；A（BC）=（AB）（AC）；A（BC）=（AB）（AC）；（BC）A=（BA）（CA）。定义20 集合X上的二元关系 R称为等价关系 ，若R同时具有以下三个性质：（1） （1） R是自反的，即xX，xRx ；（2） （2） R是对称的，即若xRy，则yRx ；（3） （3） R是传递的，即若xRy，且yRz，则xRz 。则称R是X上的等价关系，记为。定义21 设是X上的一个等价关系，xX，X的子集Ex=yyX且xy称为x关于的等价类，或简称为x的等价类。 定义22 设X为集合，X的一些非空子集形成的集族=AAX且A称为X的一个划分，若具有性质 （1）A，B，若AB，则AB=；（2）=X 。 定义23 设是X上的等价关系。由所确定的X的划分的所有等价关系类之集称为X对的商集，并记X。定义24 集合X上的二元关系 R称为偏序关系，若R同时满足以下三个性质：（1） （1） 是自反的，即IXR；（2） （2） R是反对称的，即若xRy且yRx，则x=y；（3） （3） R是传递的，即R2R 。则称R是X上的偏序关系，记为。定义25 设是X上的一个偏序关系 ，则称二元组（X，）为偏序集。定义26 集合X上的偏序关系“”称做全序关系，若x，yX，xy与yx至少有一个成立。全序关系也称为线性序关系。X与全序关系“”构成的二元组（X，）称为全序集。定义27 设（X，）是一个偏序集。称y盖住x，若xy且对每个zX，若xzy，则x=z或y=z。若y盖住x，则y被称为x的后继，而x称为y的前驱。定义28 设（X，）是一个偏序集，AX。若a，bA，ab与ba必有一个成立，则称A为X中的链。若对A中任两不同元素a与b，ab与ba均不成立，则称A为X的一个反链。A称为链（反链）的长度。定义29 设（X，）是一个偏序集，BX。若存在一个元素aX，使得对B中每个元素x有xa，则称a为B的一个上界。若存在一个元素b，使得对B的每一个元素x有bx，则称b为B的一个下界。定义30 设（X，）是一个偏序集，BX。若存在一个元素aB，使得xB有xa，则称a是B中的最大元素。若存在一个元素bB，使得xB有bx，则称b是B中最小元素。定义31 设（X，）是一个偏序集，BX。若B有上界且B的一切上界之集有最小元素，则这个最小上界称为B的上确界，记为supB。类似地，若B有下界且B的一切下界之集有最大元素，则这个最大下界称为B的下确界，记为infB。定义32 设（X，）是一个偏序集，AX。A中元素s称为A的极大元素，若A中没有元素l，使得ls且sl。若A中有元素d，使得xA，若xd，都有xd不成立，那么d被称为A的极小元素。定义33 集合X上的二元关系R称为拟序关系，若R是反自反的和传递的。拟序关系常记为。若xy，则读为“x小于y”。 3.1.2 基本定理定理1定义2与定义5等价。定理2 设R1， R2， R3分别是从A到B，B到C，C到D的二元关系，(R1R2)R3 = R1（R2R3 ）定理3 设R1是A到B的二元关系，R2和R3是从B到C的二元关系，R4 是从C到D的二元关系，则 （1）R1（R2 R3 ）=(R1R2) (R1R3) （2）R1（R2 R3 ）(R1R2) （R1R3） （3）（R2 R3 ）R4 = (R2R4) （R3R4） （4）（R2 R3 ）R4(R2R4) (R3R4) 定理4 设R，S 是集合X上的两个二元关系，则（1）(RS )-1 = S -1R-1 （2） RR-1 是对称的。定理5 设R是X上的二元关系，则R是传递的当且仅当RRR 。定理6 设R是X上的二元关系，则对任意的非负整数m，n，有RmRn = Rm+n，(Rm)n = Rm n。定理7 设X是一个有限集合且|X|=n，R为X上的任一二元关系，则存在非负整数s，t，使得0st且Rs= Rt 。定理8 设 R是X上的二元关系 ，若存在非负整数s，t，st，使得且Rs= Rt ，则（1）Rs+k= Rt+k ，k为非负整数；（2）Rs+kp+i= Rs+i ，其中p=t-s，而k，i为非负整数；（3）令S=R0，R，R2 ，Rt-1，则对任意的非负的整数q，有Rq S 。定理9 集合X上的二元关系R是对称且传递的，当且仅当R=RR-1 。定理11 设R是集合X上的二元关系，则r(R )=RIX 。定理12 设R是集合X上的二元关系，则s(R )=RR-1 。定理13设R是集合X上的二元关系，则关系R的传递闭包R+是传递关系。并且 R+= RR2 R3 。定理14 设|X|=n，R为X上的二元关系，则R+=定理15 设R，S是X上的二元关系，则 （1）+=，其中为空集，即空关系； （2）RR+ ；（3）（R+ ）+ =R+ ；（4）（RS）+ R+ S+ 。定理16 设R是X上的二元关系，则R=RR+定理17 设R是X上的二元关系，则（1） （1） r(s( R )=s(r( R ) ；（2） （2） r(R+ )=r（R）+= R ；（3） （3） s(R)+ s(R+) 。定理18 设R，S为X到Y的二元关系，其关系矩阵分别为BR和BS，RS与RS的关系矩阵分别记为BRS和BRS ，则BRS=BRBS ，BRS =BRBS 。定理19 设X，Y，Z是有限集，|X|=m ，|Y|=p ， |Z|=n 。R是X到Y 的二元关系，S是Y到Z的二元关系，R，S，RS的关系矩阵分别为BR ，BS ，BRS ，则BRS =BR BS 。定理20 设R是X上的二元关系，|X|=n ，B是R的矩阵，是R+的矩阵，简记为，则=。定理21 设是X上的一个等价关系，则的所有等价类的集合是X的一个划分。定理22 设是集X上的一个划分。令=，则是X上的一个等价关系且就是等价类之集。定理23 集合X上的二元关系是一个等价关系，当且仅当存在X的一个划分使得xy的充分必要条件是A，使得x，yA 。定理24 设R为X上的一个二元关系，则e(R)=( RR-1)* 。定理25 设R，S是X上的等价关系，则RS是等价关系的充分必要条件是 RS= SR 。推论 设R，S是X上的等价关系，则RS是等价关系的充分必要条件是 RSSR 。定理26 设R，S是X上的等价关系，若RS是等价关系，则RS = （RS）+ 。定理27 设（X，）是一个偏序集。若X中每个链的长至多为n ，则X的全部元素能被分成n个非空不相交反链之并。推论 设（X，）是一个偏序集，|X|=mn+1 ，则X中或存在一个长至少为n+1的链，或存在一个长至少为m+1的反链。第四节 无穷集合及其基数基本要求1掌握可数集，连续集和无穷集合基数的概念及其性质。2熟练掌握cantor“对角线解法”的证明方法。3掌握与无穷集合有关但与有穷集合不同的一些性质，从而深刻体会无穷的特征。4.1必备知识和考试要点4.1.1 基本概念定义 1 若从自然数集N到集合X存在 一个一一对应f：NX，则称集合X是无穷可数集合，简称可数集或可列集。定义 2 凡能与自身的一个真子集对等的集合称为无穷集合，或无限集合。定义 3 凡与集0，1对等的集称为具有“连续统的势”的集，或简称连续统。定义4 集合A的基数是一个符号，凡与A对等的集合都赋以同一个记号。集合A的基数记为A定义4（1）所有与集合A对等的集构成的集族称为A的基数。定义 5 集合A的基数与集合B的基数称为是相等的，当且仅当AB 。定义 6 ，是任个两基数，A，B是分别以，为其基数的集。若A与B的一个真子集对等，但A却不能与B对等，则称基数小于基数，记为。定义 7 设，是两个基数，A与B是两个不相交集合，A=，B=。集合AB的基数称为基数与之和，并记为+ 。定义 8 设，是任意两 个基数，A与B是两个集合，A=，B=。集合AB的基数称为与的积，记为 或简记为。定义9 设与为任意两个（不同时为0的）基数，A与 B为两个集合且A=，B=，则BA=ff：AB的基数称为的次幂，记为。对，定义 =1；而0=0。 4.1.2 基本定理定理 1 集合A为可数集的充分必要条件是A的全部元素可以排成无重复项的序列 a1， a2， a3， ，an， 因此，A可写成A=a1， a2， a3， 。定理2 无限集A必包含可数子集。定理3 可数集的任一无限子集也是可数集。推论 从可数集A中除去一个有限集M，则AM仍是可数集。定理4 设A 是可数集，M是有限集，则AM是可数集。定理5 设A1， A2， ，An（n1）都是可数集，则也是可数集。定理 6 可数个有限集之并至多是可数。即若A1， A2， ，An， 是有限集的无穷序列，则或为有限集或为可数集。定理 7 设A1， A2， ，An， 为可数集合的一个无穷序列，则是可数集。即可数多个可数集之并是可数集。定理8 全体有理数之集Q是可数集。推论 区间0，1中的一切有理数之集是可数集。定理 9 设M是一个无限集，A是有限或可数集，则MMA。定理10 设M是一个无穷不可数集，A为M的至多可数子集（即A有穷或可数），则MMA。定理11 设A1， A2， ，An（n2）都为可数集，则A1A2An是可数集。推论 整系数代数多项式的全体是一个可数集。定理12 区间0，1中的所有实数构成的集合是不可数无穷集合。定理13 设A1， A2， ，An是n个两两不相交的连续统，则是连续统，即0，1定理14 设A1，A2，An为两两互不相交的集序列，若Ak0，1，k=1，2，则0，1推论 全体实数之集是一个连续统。推论 无理数之集是一个连续统。定理14 令B为0、1的无穷序列所构成的集合，则B0，1。定理15 令S=ff：N0，1，则S0，1。于是，若A为可数集，则0，1。定理16 正整数的无穷序列之集，与区间0，1对等 。定理17 设A1，A2均为连续统，则A1A20，1。推论 平面上所有点的集合是一个连续统。定理18 若A1， A2， ，An均为连续统，则A1A2An0，1。定理19（康托）对任一集合M，M 。定理20（康托-伯恩斯坦）设A，B是两个集合。若存在单射f：AB与单射g：BA则A与B对等。推论 设，是任意两个基数，则下面三个式子 =， ，的任两个式子不能同时成立。推论 若A1 A2A且A1A，则A2A。推论 设，为任意三个基数。若且，则。这表明基数之间的小于或等于关系是传递的。定理21 设，为任意两个基数，则下三个式子 =， ，中恰好有一个式子成立。定理22 设a为可数集的基数，c为连续统的基数，则 (1) nN0，n+a=a 。(2) nN，na=a 。(3) niN，i=1，2，a 。(4) nN，nc=c 。(5) ac=c 。(6) cc=c 。(7) =c 。(8) =。定理23 设，为任意基数，则（1） （1） 基数的加法和乘法分别满足交换律，即 +=+，= （2） （2） 基数的加法和乘法分别满足结合律，即 (+)+=+(+)()= ()（3） （3） 基数的乘法对加法满足分配律，即 (+)=+第二篇 图 论图论是一门很有实用价值的学科。它在自然科学，社会科学等各个领域都有很大的应用。特别是在计算机科学领域中起着相当重要的作用。如在逻辑设计，计算机网络，数据结构，数据库系统，形式语言与自动化理论等等的研究过程中，图论是一种十分有用的工具。因此，它是从事计算机科学的研究和应用人员必备的基本知识。这些知识中的一些在本质上是相当初等的，希望通过本章的学习，掌握图论的初步知识并获得能把实际问题转化为图论的问题，并通过对图论问题的解决以达到对实际问题之解决的初步能力，为图论在计算机科学中的应用打下一个良好的基础。 图论部分主要包括图的基本概念、欧拉图与哈密顿图、平面图、图的着色问题、有向树及有序树等。图论是离散数学中的重点和难点。之所以是难点，是因为关于图论的题目往往是在具有某种性质的抽象的图中进行考查的。题目入手困难，推理抽象，而且一些经典的证明方法不是一般人能够想得到的。但是，我们为了提高应对考试的能力，完全可以在牢固掌握基础知识的前提下，理解、记忆、归纳、总结各类题型和解题方法，以获得意想不到的成绩。在图论的解题过程中常常使用两种解题方法：一是反证法，另一个是数学归纳法。反证法首先假定结论不成立，然后在此基础上推出与已知结论或题设条件相悖的结果。在很多情况下，反证法的效果是非常好的，但同时我们也必须看到，反证法不是万能的，在有些情况下它反而会增加证明的难度。具体的体会只有通过练习才能获得。由于图中的顶点，边和面都是可数的，所以图论的命题往往是关于自然数的命题，因此可以用数学归纳法来解决。使用数学归纳法的关键是选择恰当的归纳变元，通常是选取顶点个数或边的条数或面的个数作为归纳变元，但有时也可以选取其他的量为变元。选择归纳变元的具体方法也只能在练习中自己体会。第五章 图的基本概念基 本 要 求1熟练掌握图的基础知识中的概念和定理。2熟练掌握连通图的问题及其证明。3掌握欧拉图和哈密顿图的概念及其判断方法。4掌握最短路的算法及其邮路问题。5能够判断和证明图的有关结论5.1 必备知识和考试要点5.1.1 基本定义设是一个非空集合，的一切二元子集之集合记为，即； 定义1 设是一个非空有限集合， ，二元组称为一个（简单）无向图。为顶点集，中元素称为无向图的顶点；称为边集，的元素称为图的边。若，则称与邻接。 以为顶点集，为边集的无向图常用一个字母表示，即。若，则称为一个图，即是一个具有个顶点条边的图。（1，0）图称为平凡图。 以后常用小写字母（有时带下标），为图的顶点命名，而用，为边命名。于是，若是图的一条边，则为这条边的名字，和称为边的端点，这时还说顶点（同样地，）与边互相关联，还说是联结顶点和的边，且记为或。若与是图的两条边，并且仅有一个公共端点，即，则称边与邻接。 我们知道，有限关系可以用图示方法表示。正是有了这种图示法表示关系，使得图有一种直观的外形，富于启发而被广泛采用。由于作为边集被视为关系时是对称的，所以其图示画法也简化。一般地，将图的每个顶点在平面上用一个点或一个小圆圈表示，并在其旁写上顶点的名（若顶点已命名），若是图的一条边，则就在代表和的两点间联一条线，这样得到的图形就叫做一个图的图解。注意，在画图的图解时，线的交点不是图的顶点。以后，图和它的图解不分，图解也说成图。 定义2 设为无向图，若，则称为零图。零图是没有边的图。定义3 设为一个非空有限集， ，二元组称为一个有向图。中的元素称为的顶点， 中元素称为的从到的弧或有向边。如且均为的弧，则称与为一对对称弧。若是有向图的一条弧，则称弧起于顶点终于顶点的弧，或从到的弧，称为为起点，为终点。画的图解时，弧用矢线表示，从代表的点画一条带箭头的线指向代表的点。定义4 不含对称弧的有向图称为定向图。定义5 设是一个图，图称为的一个子图，其中是的非空子集且是的子集。定义6 设是一个图。若，则的子图为的生成子图。易见，的生成子图就是包含的所有顶点的子图。在图论中，“生成”这两个字具有特殊的用法，以后常涉及“图的生成”，这时常指“含有的所有顶点的”。定义7 设是图，非空子集，则的以为顶点集的极大子图称为由导出的子图，记为。形式地，。设，由导出的子图记成。类似地，设是的一条边，则的生成子图简记为。若和是的两个不邻接的顶点，则图简记成，它是在的图解中，把与间联一条线而得到的图。定义8 设，是两个无向图。若存在一个一一对应，使得当且仅当，则称与同构，记为。 图的子图包含有的信息。而下面的乌拉姆（S.M.Ulam，1909-）猜想表明，形如的子图的全体，能给出足够多的关于的信息。乌拉姆猜想 设，是两个图，。若对每个，则。乌拉姆猜想是图论中一个未解决的问题。要解决它是非常困难的。显然，同构的图，必有相同的顶点数和相同的边数。与此同时与有关的一个数称为的一个不变量，若与同构的任一图所对应的这种数均相同。于是，数和就是不变量。除同构不计外，足以确定一个图的那些不变量所形成的集，称为不变量的完全系。定义9 设为图的任一顶点，中与关联的边的数目称为顶点的度，记为显然，中每个顶点的度之和是的一个不变量，但这个不变量不是独立的。令，定义10 设是图，若，即的每个顶点的度都等于，则称为度正则图。3度正则图也叫做三次图。一个具有个顶点的度正则图称为个顶点的完全图，记为。在中，每个顶点与其余各顶点均邻