离散数学高分笔记

高分笔记（离散数学）主要介绍集合论的基本概念和结论，集合的运算及其性质，以及利用运算性质进行集合表达式的化简和集合恒等式的证明等内容．考试经常涉及到的题型有以下4个：集合与集合之间的包含、元素与集合之间的属于关系幂集的计算集合之间的运算利用集合运算性质证明集合恒等式大家对于集合与集合、元素和集合之间的关系往往容易混淆，那让我们来仔细分析下二者的区别。1.集合与集合之间存在一种包含关系，用⊆、⊂、⊇、⊃等符号表示①对任意两个集合A和B，若B中的每个元素都是A中的元素，则称B为A的子集，用B⊆A（B为A的子集）或A⊇B（B被A包含）表示．若B不是A的子集，即B⊆A不成立时，则称A不包含B，记作BA．A也是自己的子集．③对任意两个集合A和B，若B⊆A且B≠A，则称B为A的真子集，用B⊂A或A⊃B表示．2.元素与集合之间存在一种从属关系，用∈、等符号表示当a是集合A中的元素，则称a属于A，记作a∈A；若a不是集合A中的元素，则称a不属于A，记作aA．那么在考试中是怎样考的呢？我们来看2道历年真题：[例1]若集合A＝{a，{a}，{1，2}}，则下列表述正确的是(C)．（2008年9月试卷第1题）A．{a，{a}}∈AB．{2}⊆AC．{a}⊆AD．∈A[分析]选项A，错了．因为{a，{a}}是集合A＝{a，{a}，{1，2}}的子集，集合之间应该用包含关系⊆表示，即{a，{a}}⊆A．选项B，错了．因为2不是集合A＝{a，{a}，{1，2}}的元素，当然{2}也不是A的子集．正确的表示方法是{2}A．选项C，正确．因为a是集合A＝{a，{a}，{1，2}}的元素，所以取元素a组成一个集合{a}就是A的子集，用包含关系⊆表示是正确的．注意：{a}也是集合A的元素，若属于关系∈也是正确的．选项D，错了．因为空集是任意一个集合的子集，所以也是A的子集，集合之间应该用包含关系⊆表示，即⊆A．[例2]若集合A={a，b}，B={a，b，{a，b}}，则（）．（2009年7月试卷第1题）A．A⊂B，且A∈BB．A∈B，但ABC．A⊂B，但ABD．AB，且AB[答案]A[分析]选项A，正确．因为集合A={a，b}既是取集合B={a，b，{a，b}}中元素a，b组成的一个集合，是B的一个真子集，用A⊂B表示是正确的；但它也是B的元素，所以用A∈B表示也是正确的．选项B，错了．选项中第一个式子A∈B是正确的，但第二个式子AB是错的．因为集合A={a，b}是取集合B={a，b，{a，b}}中元素a，b组成的一个集合，是B的一个真子集，应该用A⊂B表示，而不是用AB表示．选项C，错了．选项中第一个式子A⊂B是正确的，但第二个式子AB是错的．因为集合A={a，b}是集合B={a，b，{a，b}}中元素，应该用A∈B表示，而不是用AB表示．选项D，错了．因为集合A={a，b}是取集合B={a，b，{a，b}}中元素a，b组成的一个集合，是B的一个真子集，应该用A⊂B表示，而不是用AB表示．又因为集合A={a，b}是集合B={a，b，{a，b}}中元素，应该用A∈B表示，而不是用AB表示．幂集的计算比较简单，先来看什么是幂集呢？1由集合A的所有子集组成的集合，称为APA的幂集，记作()或2A．若集合An是由个元素所组成的集合，则A的幂集由2n元素组成．当=3时，的幂集由23=8个元素组成．举个例子来说，大家就会觉得比较简单了．设集合A={0,1,2}，则A的全部子集由以下子集组成：nA0元子集（即空集）：；1元子集：{0}，{1}，{2}；2元子集：{0,1}，{0,2}，{1,2}；A3元子集（即集合）：{0,1,2}．因此，计算集合A的幂集时，首先要按照上述方法写出集合A的全部子集，然后检验写出的子集个数是否等于2n个，其中是集合A的元素个数n那么在考试中是怎样考的呢？我们来看2道历年真题：A[例1]若集合的元素个数为10，则其幂集的元素个数为()．（2008年7月试卷第3题）A．1024B．10C．100D．1[答案]：A[分析]由集合A的所有子集组成的集合，称为A的幂集，记作P(A)或2A.AnAAAn若集合是由个元素所组成的集合，则的幂集由2元素组成．本题集合有10个元素，因此的幂集由210=1024个元素组成．所以选项A是正确，其他选项都不对．【易错点】当n比较大时，有些同学可能不会计算2的n次幂，即把2计算错了．【提示】10若集合A有n个元集，则其幂集P(A)有2n个元素．Aab[例2]设集合＝{，}，那么集合A的幂集是_________．（2008年7月试卷第6题）abab[答案]：{，{}，{}，{,}}[分析]按照幂集定义，集合＝{，}的所有子集就是A的幂集．AabA的全部子集由以下子集组成：0元子集（即空集）：；ab1元子集：{}，{}；Aab2元子集（即集合）：{，}．Aabab所以，集合的幂集是：{，{}，{}，{,}}集合之间的运算有并（∪）、交（∩）、差（-）、补（~）和对称差（）等五种运算，在做集合运算的题目时，一定要按照它们的定义进行计算。(1)集合A和B的并集A∪B＝{x|x∈AxB或∈}特点：所有属于A或属于B的元素组成的集合．见图1(2)集合A和B的交集A∩B＝{x|x∈AxB且∈}特点：既属于A又属于B的所有元素组成的集合．见图2(3)集合A和B的差集-＝{|∈ABxxA且xB}特点：由属于A，而不属于B的所有元素组成的集合．见图3(4)集合A的补集AxxE且xA}~={|∈特点：由属于全集E但不属于集合A的元素组成的集合．见图4补集总相对于一个全集而言，可以看作是全集E与集合A的差集．2(5)集合A与B的对称差ABBA＝(-)∪(-)ABAB＝(A∪B)-(A∩B)或特点：由分别属于集合A与B的元素但不属于它们公共元素组成的集合．见图5A，B合成集合A×B叫做笛卡儿积，规定xyxA且y∈B}(6)把集合AB×＝{<,>|∈xy注意：由于有序对<,>中x,y的位置是确定的，因此A×B的记法也是确定的，不能写B×A.．成笛卡儿积的运算一般不能交换.．虽然笛卡儿积的内容是第2章2.1.1目的内容，是二元关系的预备知但我们认为把它作为集合的一种运算考虑更好些。识，那么在考试中是怎样考的呢？我们来看2道历年真题：AB[例1]设={{1},{2},1,2}，={1,2,{1,2}}，试计算（2008年9月试卷第[分析]17即题）AB（1）-；AB（2）∩；（3）A×BA与B的差集A而不属于B的所有元素组成的集合．（1）求集合A-B，就是求属于A-B={{1},{2},1,2}-{1,2,{1,2}}={{1},{2}}．A与B的交集A∩B，就是求由A∩B={{1},{2},1,2}∩{1,2,{1,2}}={1,2}．A和B的公共元素组成的集合（2）求集合集合．即A×B，就是求一个元素是（3）求集合A与B的笛卡儿积有序对的集合，而这些有序对的第一个元素取自集合A，第二个元素取自集合A×B={{1},{2},1,2}×{1,2,{1,2}}={<{1},1>，<{1},2>，<{1},{1,2}>，<{2},1>，B．即<{2},2>，<{2},{1,2}>，<1,1>，<1,2>，<1,{1,2}>，<2,1>，<2,2>，<2,{1,2}>}【易错点】我们对集合中有的元素用集合形式表示的情形容易混淆，既不把{1},{2}看作集合元素，不把{1,2}看作集合B的元素，或者把{1}，{2}，{1,2}看作是相同的。【提示】A的笛卡儿积A×B是由集合A的每一个元素与集合B的各个元素合成有序对<x,y>（其中x意∈A且y∈B）作为元素的集合．所谓有序对就是指一个有顺序的数组，如<x,y>，x,y的位置是确定的，不能随放置。AabBab[例2]设={{,},1,2}，={,,{1},1}，试计算（2009年1月试卷第17题）AB（1）-；AB（2）∪；ABAB（3）（∪）-（∩）B的所有元素组成的集合．即A和B的所有元素组成的集合．即[分析]（1）求集合A与B的差集abA-B，就是求ab-={{,},1,2}-{,,{1},1}={{,},2}．A而不属于属于ABabA与B的并集A∪BabA∪B，就是求ab={{,},1,2}∪{,,{1},1}={{,},1,2,,,{1}}．（2）求集合由集合ababA∪Babab={{,},1,2,,,{1}}ab（3）因为ABab∩={{,},1,2}∩{,,{1},1}={1}ABABabababab∪）-（∩）={{,},1,2,,,{1}}-{1}={{,},2,,,{1}}．所以（如同实数运算有交换律、面以恒等式的形式给出集合运算满足的主要运算律结合律和分配率等。集合的运算也有许多运算律。,其中下A,B,C为任意集合这些恒等式是证明其它集合恒等式、化简集合表达式的主要依据,正确运用这些恒等式是做好集合证明或化简题的关键．因此,大家要通过练习逐步掌握这些集合运算性质.,E为全集。3A∪B=B∪AA∩B=B∩A1、交换律2、结合律3、分配律4、同一律5、幂等律6、零律(A∪B)∪C=A∪(B∪C)(A∩B)∩C=A∩(B∩C)A∪(B∩C)=(A∪B)∩(A∪C)A∩(B∪C)=(A∩B)∪(A∩C)A∪=AA∩E=AA∪A=AA∩A=AA∪E=EA∩=A∪~A=EA∩~A=7、补余律8、吸收率A∪(A∩B)=AA∩(A∪B)=AA-(B∪C)=(A-B)∩(A-C)A-(B∩C)=(A-B)∪(A-C)～(B∪C)=~B∩~C9、摩根律～(B∩C)=~B∪~C~=E~E=10、双补律~（~A）=A[例1]试证明集合等式8题）A∪(B∩C)=(A∪B)∩(A∪C)．（2008年9月试卷第19题、2009年10月试卷第[证明过程]若对A∪(B∩C)中的任一元素则有x∈A或x∈B∩C，x，即x∈A∪(B∩C),即x∈A或x∈B且x∈A或x∈C,也即x∈A∪B且x∈A∪C，得x∈(A∪B)∩(A∪C)．所以A∪(B∩C)⊆(A∪B)∩(A∪C)．①反之，若对(A∪B)∩(A∪C)中的任一元素x，即x∈(A∪B)∩(A∪C),则有x∈A∪B且x∈A∪C,即x∈A或x∈B且x∈A或x∈C,也即x∈A或x∈B∩C，得x∈A∪(B∩C)．所以(A∪B)∩(A∪C)⊆A∪(B∩C)．②由①和②得A∪(B∩C)=(A∪B)∩(A∪C)．【提示】集合恒等式的证明方法通常有二：(1)要证明A=B，只需要证明A⊆B，又A⊇B；(2)通过运算律进行等式推导.[例2]设A，B是任意集合，试证明：若A×A=B×B，则A=B．（2010年1月试卷第18题）A×A的元素，即<x,x>∈A×A．[证明过程]设对A中的任一元素x，即x∈A，那么有序对<x,x>∈B×B，则有<x,x>是笛卡儿积因为A×A=B×B，故有所以A⊆B．①x∈B．又设对B中的任一元素x，即x∈B，那么有序对<x,x>∈A×A，则有x∈A．<x,x>是B×B的元素，即<x,x>∈B×B．因为A×A=B×B，故有4所以B⊆A．②由①和②得A=B．第2章主要介绍关系的概念及运算、关系的性质与闭包运算、等价关系、相容关系和偏序关系三个重要关系、函数以及函数相关知识等内容．考试经常涉及到的题型有以下5个：关系的概念理解以及关系的并、交、补、差以及复合和逆关系等运算关系自反和反自反、对称和反对称等性质的概念理解与判定；自反、对称和传递闭包运算等价关系偏序关系和哈斯图函数的概念和性质所谓“关系”，就是指客体之间的相互联系，是一种普遍存在的现象．任何一个有序对集合，称为一RR个“二元关系”，简称“关系”，记作．对于二元关系，abR若<，>∈，可记作aRb；abR若<，>，则记作ab．RAaAbAR[例1]如果是非空集合上的等价关系，∈，∈，则可推知中至少包含等元素．aabb[答案]<，>，<，>[分析]由等价关系的概念，知道R具备了自反性、对称性和传递性．根据已知A上的元素a和b，根据自反的概念，知道R中必须包含和，由对称和传递概念，得知{，}也具备对称性和传递性，因此对应A上的关系R至少应该包含元素，【易错点】本题目中要求的是最小等价关系，同学们容易将答案写为{<a，a>，<a，b>，<b，a>，<b，b>}．【提示】先加入自反关系，然后再根据等价关系加入必要的对称和传递所需的元素．ARxyxyxyAR[例2]集合={1，2，3，4，5，6，7，8}上的关系={<，>|+=10且，∈}，则的性质为（）．A．自反的B．对称的C．传递且对称的D．反自反且传递的[答案]B分析]首先，可以写出关系R的有限集合表示，即{<2，8>，<8，2>，<3，7>，<7，3>，<4，6>，<6，4>，<5，5>}RRRR容易看出，<1，1>，因此不是自反的．<5，5>∈因此，不是反自反的．RRRR又因为<2，8>∈，且<8，2>∈，而<2，2>，因此，不具备传递性．因此，答案选择BARxyxAyAxyR[例3]若={1，2}，={<，>|∈，∈，+=10}，则的自反闭包为答案]{<1，1>，<2，2>}[分析]本题考核的是关系闭包的计算．计算关系闭包有集合法、矩阵法和关系图法．本题目可以直接使用集合法计算公式r(R)=R∪I．A首先容易计算出R=Φ，I={<，1>，<2，2>}．Ar(R)=RII∪=={<，1>，<2，2>}AA（1）函数的概念5f是集合A到B的二元关系，若任意a∈A，存在bBab∈，且<，>∈f，Dom(f)=A，设则f是一个函数（映射）．函数是一种特殊的关系．A×BA中每一个注意：集合的任何子集都是关系，但不一定是函数．函数要求对于定义域a，B中有且仅有一个元素与a对应，而一般的关系没有这个限制．元素（2）单射、满射和双射的判断a≠a⇒f(a)≠f(a)；单射：若1212y满射：f(A)=B，即对任意双射：单射且满射．（3）函数的复合B∈，存在xA∈，使得y=f(x)；fABgBCfgACgf(x)=g(f(x))．：→，：→，则·：→，即(·)复合成立的条件是：Ran(f)⊆Dom(g)．若AabcB[例1]设={，，}，={1，2}，作fAB：→，则不同的函数个数为__________[答案]：8[分析]本题目考核的是学生对函数概念的理解．函数可以有下面映射规则：abc（1）,,全映射到2；（2）a映射到1，b和c映射到2；2；（3）b映射到（4）c映射到（5）a映射到（6）b映射到（7）c映射到1，a和c映射到1，a和b映射到2，b和c映射到2，a和c映射到2，a和b映射到1；2；1；1；1；abc（8）,,全映射到A到B映射个数可以描述为：因此，函数个数为C8．另外，此类题目也可以作以下分析．CCC0+++3=8238133正确答案：3【提示】函数概念中，有两点尤其要注意．第一，是函数的单值性，即对于A中任何元素，必须有B中元素映射唯一对应；第二，是函数的定义域，即A是函数f定义域fN、R分别为自然数集与实数集，f：N→R，f(x)=x+6，则f是单射．[例2]判断说明：设[答案]：正确[分析]xx≠x，则有12f(x)x1=+6≠+6=f(x)，故x2f为单射．x，为自然数且1设212【提示】“单射”概念中，强调的是对于不同定义域中的值，通过函数映射得到的对应值不同，这种“一对一”是从前到后的一对一，并不要求从后到前一对一．[例3]设={，}，={1，2}，R，R，R是A到B的二元关系，且AabB3RabRaa={<，2>,<，2>}，={<，1>,<，212>,<，1>}，R={<，1>,<，2>}，则（21abA到B的函数．b）不是从3RB．RA．R和122D．R和1RC．R33[答案]：B[分析]函数的概念中，强调两点：第一，函数的单值性，即对于每一个定义域中的值，只能有一个对应函数值；A．本题中的R不符合函数概念强调的第一点．2第二，函数的定义域必须为集合（1）偏序关系设R是非空集合A上的二元关系，如果R是自反的、反对称的和传递的，则称R是A上的ab偏序关系或者简称序关系．偏序关系记作≤．<，>∈≤，则称a小于等于b，记作a≤b．（2）哈斯图6作图规则：i．去掉每个结点的自回路，用空心点表示集合的元素；a和b，若a≤b，则将a画在b的下方；ii．对于集合任意元素iii．对于集合任意元素a和b，若a<b，且不存在c使a<c<b，则在a和b之间划一条弧．（3）最小元、极小元、最大元和极大元，上界和下界一个子集的极大(小)元可以有多个，而最大(小)元若有，只能惟一；且极元、最元只在该子集内；而上界与下界可在子集之外确定，最小上界是所有上界中最小者，最小上界再小也不会小于子集中的任一元素；可以与某一元素相等，最大下界也是同样．AR<,>的哈斯图如所示，则集合A的最大元为a，最小元不存在．[例1]若偏序集[答案]错误A的最大元不存在，a是极大元．若a为最大元，则对于任意x∈A，集合xaR必有<,>∈，但从图中可以得知，ga<,>R，因此a不是最大元．同时，不存在xA∈，满足xaR<,>∈，因此，a为极大元．【易错点】哈斯图不是简单的层次关系图，不要用层次关系判断最大元、最小元、极大元、极小元等．【提示】最小元应小于等于其它各元素；最大元应该大于等于其它各元素；极小元应该小于等于一些元素，而与剩下的元素没有关系；极大元应该大于等于一些元素，而与剩下的元素没有关系．最大元和最小元不一定存在，如果存在则必定唯一.A={1，2，3，4，5}，偏序关系≤是A上的整除关系，则偏序集A<,≤>上的元素5是集合A的（）.[例2]设集合A．最大元C．最小元B．极大元D．极小元[答案]B由于元素4和5没有整除关系，显然5不是最大元．同理，【提示】5和2没有整除关系，5也不是最小元．整除关系是常考的一类偏序关系．两个元素是否具备整除关系可以不直接表达，所以题型描述简单，但是同学们需要将序关系的概念应用到此类题目中才能正确辨别．第3章是图论的基础部分，主要介绍图论的基本概念与结论，包括图的基本概念、图的连通性与连通度、图的矩阵表示等.经常涉及到的题型有：已知点集和边集画图，求结点的度数，画补图握手定理计算题强分图（连通）、单向分图（连通）、弱分图（连通）的判断求点割集，割点，边割集，割边无向简单图，已知点集和边集求邻接矩阵我们将反映对象及其相互关系的图分为无向图和有向图，那我们就仔细了解一下它们，以及它们的区别、联系：1.无向图是一个有序的二元组<V，E>，记作G＝<V，E>，其中V≠称为顶点集，其元素称为顶点或结点；其中E称为边集，其元素称为无向边，简称为边.2.有向图是一个有序的二元组<V，E>，记作G＝<V，E>，其中V≠称为顶点集，其元素称为顶点或结点；其中E称为边集，其元素称为有向边，简称为边.小提示：①用图形表示无向图和有向图时，用小圆圈表示顶点，用顶点之间的连线表示无向边，用有方向的连线表示有向边.②在无向图中，与结点相关联的边的条数，称为该结点的度数，记作deg(V)，用Δ(G)表示最大度，用δ(G)表示最小度.③在有向图中，对于任何结点，出度就是以其为始点的边的条数，入度就是以其为终点的边的条数，出度与入度之和称为该结点的度数.7④如果图G与图H互为补图，则它们的顶点集相同，且它们的边集的并集等于其完全图的边集.[例1]设图G＝<V，E>，V＝{v，v，v，v，v}，E＝{(v,v)，(v,v)，(v,v)，(v,v)，(v,v)，(v,3123451213224343v)，(v,v)}，试554（1）画出G的图形表示；（2）求出每个结点的度数；（3）画出图[解题过程G的补图的图形．]（1）关系图先根据G的结点集画出图中的5个结点，这里的结点按逆时针排列，也可以按顺时针排列.再根据边集，在邻接的结点间将边画出.（2）在图示中观察每个结点连接的边数，计算出各结点的度数.deg(v)=21deg(v)=32deg(v)=43deg(v)=34deg(v)=25（3）补图补图的结点集与原图的结点集相等，补图的边集是那些由结点集确定的完全图中去掉原图中的边所留下的边组成的.补图的边数＝完全图的边数－原图的边数3条.又因为5个结点的完全图的边数为条.所以10－7＝[例2]设G是一个补图)．n阶无向简单图，n是大于等于2的奇数．证明G与中的奇数度顶点个数相等(是G的[证明过程]分析]因为握手定理：结点度数之和等于边数的2倍，所以图G的结点度数总和一定是偶数.又因为n是奇数，图G有奇数个结点，所以n阶完全图每个顶点度数为偶数.因此，奇数＋奇数＝偶数，若G中顶点v的度数为奇数，则在补图中v的度数一定也是奇数，所以G与中的奇数度顶点个数相等．【提示】补图与原图的结点集相等，补图与原图的边数之和等于其结点的完全图的边数.那么在考试中是怎样考的呢？我们来看2道历年真题：[例1]设图G＝<V,E>，vV，则下列结论成立的是()．（2008年9月试卷第2题）A．B．C．D．8[答案]：Ｃ[分析]选项A，不对..因为没有连加符号∑，不能表示所有度数之和.选项B，不对不但没有连加符号∑，而且边数也没有乘以2.选项C，正确选项D，不对.有连加符.∑，还有边数乘以2.表示所有的度数之和等于边数的2倍.没有将边数也没有乘以2.【提示】【易错点】不论图中有奇数个结点或者偶数个结点，图的度数之和都是偶数.同学们容易忘记将边数乘以2倍，容易忘记表示所有度数之和的连加符号.[例2]设G是一个图，结点集合为V，边集合为E，则G的结点度数之和为_________．[答案]2（或“边数的两倍”）[分析]根据握手定理，在图中所有结点的度数之和等于边数的【提示】2倍.不论图中有奇数个结点或者偶数个结点，图的度数之和都是偶数那么在考试中是怎样考的呢？我们来看2道历年真题：[例1]设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是()．（2009年1月试卷第2题）A．（a）是强连通的B．（b）是强连通的D．（d）是强连通的C．（c）是强连通的[答案]Ｄ[分析]选项A，不对.（a）图存在一点（左下角点）不可达其它点，所以不是强连通图.但图存在一点（左上角点）可达其它各点，所以是单向连通图，也是弱连通图.选项B，不对.b）图存在一点（右上角点）不可达其它点，所以不是强连通图.但图存在一点（右下角点）可达其它各点，所以是单向连通图，也是弱连通图选项C，不对..（c）图存在两点（右上和左下角点）不可达其它点，所以不是强连通图.但图略边去的方向后，是连通图，所以是弱连通图.选项D，正确（d）图中任何两结点互相可达，所以是强连通图，当然也是单向连通图和弱连通图易错点】同学们要完全理解弱连通图、意向连通图、强连通图的概念，不能将它们混淆.【提示】..强连通图一定是单向连通图和弱连通图；单向连通图一定是弱连通图.反之，不成立.[例2]判断下图是哪类连通图.9⑴⑵（3）[解题过程]（1）存在.V点，可达其它各点1V、V、V，所以是单向连通图3.但图中V3点不可达其它点，所以不是24强连通图（2）略去边的方向后，不是连通图，所以不是任何连通图（3）存在V点，可达其它各点1.V、V、V.324存在V点，可达其它各点2V、V、V.134存在V点，可达其它各点3V、V、V.124存在V点，可达其它各点V、V、V.4123因此，任何两结点都可达，所以是强连通图【提示】强连通图一定是单向连通图和弱连通图；单向连通图一定是弱连通图.反之，不成立.那么在考试中是怎样考的呢？我们来看[例1]如图一所示，以下说法正确的是A．e是割点2道历年真题：()．（2008年9月试卷第4题）B．{a,e}是点割集D．{d}是点割集C．{b,e}是点割集[答案]Ａ[分析]去掉点选项A，正确.e和其连接的边后，图就不连通了.选项B，不对．虽然去掉点ａ、点a．e和其连接的边后，图就不国通了.但是单单去掉点.但是单单去掉点e和其连接的边后也可以不连通，所以不应该包括点e和其连接的边后也可以不连通，所以不应该包括点选项C，不对.虽然去掉点b.b、点e和其连接的边后，图就不连通了选项D，正确.去掉点d和其连接的边后，图依然连通【提示】.点割集里只有一个结点时，这个结点才是割点.【易错点】同学们要准确地确定点割集里的结点，不能含多余的结点.[例2]如图一所示，以下说法正确的是A．｛（a，e）｝是割边C．{（a，e）,（b，ｃ）}是边割集(）．（2010年7月试卷第B．｛(a,e)｝是边割集D．｛(ｄ,e)｝是边割集4题）[解题过程][分析]选项A，不对.去掉边（a，e）后，图依然连通.而且{（a，e）}是集合a，e）后，图依然连通.选项B，不对选项C，不对.去掉边（..去掉边（a，e），（选项D，正确b，c）后，图依然连通..去掉边（d，e）后，图就不连通了.【提示】边割集里只有一条边时，这条边才是割边．【易错点】10同学们要准确地确定边割集里的边，不能含有多余的边．[例1]已知图G的邻接矩阵为则则G有（）.（2008年7月试卷第5题）A．5点，8边B．6点，7边D．5点，7边C．6点，8边[解题过程]选项A，不对。因为无向图的邻接矩阵的上三角矩阵数字之和为选项B，不对。7，所以边数为7。因为邻接矩阵是5×5方阵，所以图的结点数为5个。选项C，不对。因为邻接矩阵是5×5方阵，所以图的结点数为5个。因为无向图的邻接矩阵的上三角矩阵数字之和为选项D，正确。7，所以边数为7。【提示】n个结点的邻接矩阵为n×n矩阵，即n行n列矩阵.【易错点】有向图的邻接矩阵里所有的数字之和等于边数.而因为无向图忽略了方向，所以无向图的邻接矩阵的上三角矩阵数字之和或者下三角矩阵数字之和才是边数.不要混淆．[例2]设G＝<V，E>，V＝{v，v，v，v}，E＝{(v,v)，(v,v)，(v,v)，(v,v)}，试写出其邻接矩阵2.12341323434[解题过程]图G有4个结点，则G的邻接矩阵为4×4矩阵，按结点的序号排序，根据结点间的邻接关系，确定邻接矩阵中的对应v，v）对应的位置为v，v）对应的位置为数值。边（v，v）对应的位置为11，边（1，边（1，边（v，v）对应的位343置为1.又因为是无向图，所以边没有方向，因此在（2324v，v）（v，v），（v，v），（v，v）的位置也是1.其余的位31324243置由于没有边，因此为0.邻接矩阵：【提示】n个结点的邻接矩阵为n×n矩阵，即n行n列矩阵。无向图的邻接矩阵是对称矩阵.第1章主要介绍集合论的基本概念和结论，集合的运算及其性质，以及利用运算性质进行集合表达式的化简和集合恒等式的证明等内容．考试经常涉及到的题型有以下欧拉通路、欧拉图的判别方法汉密尔顿图的判断方法平面图的判断方法（1）定义的要点：图Ｇ满足无向，连通，经过每条边一次且仅一次，经过每个结点（注意：点可重复经过，边不能重复经过），这四点缺一不可．4个：如果同时满足这四点，当始点与终点不重合时，就是欧拉通路．如果同时满足这四点，当始点与终点重合时，就是欧拉图．（2）欧拉图判定定理的要点：无向、连通图Ｇ是欧拉图的若无向、连通图Ｇ是欧拉图，那么Ｇ一定不含奇数度结点．反之，若无向、连通图Ｇ不含奇数度结点，那么Ｇ一定是欧拉图．（3）欧拉通路判定定理的要点：无向、连通图Ｇ是欧拉通路的点．当Ｇ不含奇数度结点时，Ｇ是欧拉图（充要条件是）Ｇ不含奇数度结点．（充要条件是）Ｇ不含奇数度结点或只含2个奇数度结．若无向、连通图是欧拉通路，那么不含奇数度结点或只含2个奇数度结点．11反之，若无向、连通图Ｇ不含奇数度结点或只含2个奇数度结点，那么Ｇ一定是欧拉通路．当Ｇ不含奇数度结点时，Ｇ是欧拉图．那么在考试中是怎样考的呢？我们来看5道历年真题：10，则其幂集的元素个数为[例1]若集合A的元素个数为A．ｍ为奇数C．ｎ为奇数[答案]：C[分析]()．B．ｎ为偶数D．ｍ为偶数关键：无向完全图为偶数，于是ｎ为奇数．知识点：根据欧拉图定义，每个结点的度数都是偶数，不含奇数度结点，完全图是连通图．的总度数为，平均每个结点的度数为，如果中存在欧拉图，则每个结点的度数均[例2]无向图Ｇ存在欧拉回路，当且仅当[答案]：所有结点的度数全为偶数[分析]Ｇ连通且_________关键：欧拉图判定定理的要点：连通、不含奇数度结点．知识点：欧拉图判定定理[例3]判断下列各题正误，并说明理由．1所示的图G存在一条欧拉回路：无向连通图Ｇ是欧拉图的（充要条件是）Ｇ不含奇数度结点．（2008年9月试卷第15题）如图.[答案]：正确．[分析]关键：欧拉图判定定理的要点：欧拉图判定定理：连通、不含奇数度结点．知识点：无向连通图G是欧拉图的（充要条件是）的度数分别为G不含奇数度结点．因为图Ｇ为连通的，且结点2,4,4,4,4，均为偶数，不含奇数度结点，所以Ｇ存在一条欧拉回路．（2008年7月试卷第6题）[例4]判断下列各题正误，并说明理由．如图所示的图Ｇ存在一条欧拉回路．[答案]：错误.因为图[分析]关键：欧拉图判定定理的要点：欧拉图判定定理[例5]]判断下列各题正误，并说明理由．G是无向图，且其结点度数均为偶数，则图[答案]：错误.因为题中的图G缺少连通的条件[分析]关键：根据欧拉图定义，缺少连通的条件．当图不连通时，图G为中包含度数为奇数的结点.：连通、不含奇数度结点．知识点：无向连通图是欧拉图的（充要条件是）G是欧拉图G不含奇数度结点．．如果图.Ｇ不是欧拉图．知识点：欧拉图的要点是：连通、无向图、不含奇数度结点．本题缺少连通条件．【易错点】容易漏掉欧拉图的部分要点．（1）定义的要点：图Ｇ存在一条路，经过每个结点一次且仅一次．在满足定义的条件下，若这条路是回路，则图Ｇ是汉密尔顿图．．在满足定义的条件下，若这条路不是回路，则图Ｇ是汉密尔顿通路．（2）定理4.2.1：如果图中具有一条汉密尔顿回路（即汉密尔顿图），则对于Ｖ的每个非空子集S，均有其中是的连通分支12也就是说，从图G中去掉若干个结点（至少一个结点），得到的连通分支数（即连通图数）不大于去掉的点数.。[例1]若图中有一条汉密尔顿回路，则对于的G每个非空子集S，在G中删除非空子集中的所有结点得到的连通分支数为W，则S中的结点数与W满足关系式__________．[答案]：[分析]关键：记住定理4.2.1的条件和结论．知识点：定理4.2.1：如果图中具有一条汉密尔顿回路（即汉密尔顿图），则对于Ｖ的每个非空子集Ｓ，均有的连通分支．，其中是【易错点】容易机械记忆定理，用表示分支数．【提示】本题叙述与定理叙述不同，这里是用Ｗ表示．[例2]若Ｇ是一个汉密尔顿图，则Ｇ一定是()A．平面图B．对偶图C．欧拉图D．连通图[答案]：D[分析]（1）汉密尔顿图定义：Ｇ存在一条回路，经过每个点一次且仅一次．（2）连通图定义：对任意两点，存在路径，使得一点达到另一点【提示】汉密尔顿图定义要点：G存在一条回路，经过每个点一次且仅一次（1）定义的要点：任意两条边，除结点外没有任何交点．（2）欧拉定理：连通平面图G的结点数为v，边数为e，面数为，则．（3）定理4.3.3：设G是一个有v个结点e条边的连通、简单、平面图，若那么在考试中是怎样考的呢？我们来看2道历年真题：，则．[例1]设连通平面图G的结点数为5，边数为6，则面数为______________．关键：利用欧拉定理：连通平面图G的结点数为v，边数为e，面数为，则．解应填．[例2]设G是连通平面图，v，e，分别表示G的结点数，边数和面数，则v，e和满足的关系式______________．关键：利用欧拉定理：连通平面图G的结点数为v，边数为e，面数为，则．解应填．[例3]设G是具有n个结点m条边k个面的连通平面图，则m等于______________关键：利用欧拉定理：连通平面图G的结点数为n，边数为m，面数为k，则解应填．（2010年1月试卷第9题）．．一、题型分析树是图论中的重要部分之一，其在计算机科学与技术领域有着广泛的应用，二叉树更是程序设计中的一种基本的数据结构.本章主要介绍树、生成树、二叉树、树根、最优树等概念及相关的结论与算法，包括求最小生成树的Kruskal算法、构造最优树的Huffman算法以及前缀码的求法.经常涉及到的题型有：1.树叶与结点间的计算2.画最小生成树并求其权133.构造最优树（Huffman算法）并求其权4.求前缀码因此，在本章学习过程中希望大家要清楚地知道一些概念：树连通无简单回路的无向图G.树中次数为1的顶点称为树叶．次数大于1的顶点称为分支点或内部顶点．森林一个无向图称为森林，如果它的每个连通分图都是树．树的判别给定图T，则以下命题关于图T为树的定义等价．(1)T是无回路的连通图；(2)图T无回路且e＝v－1，其中e是边数，v是顶点数；(3)图T连通且e＝v－1；(4)图T无回路，若增加一条新边，得到且仅得到一个回路；(5)图T连通，但删去任一边后图便不连通（v≥0）；(6)图T的每一对顶点之间有且仅有一条路（v≥0）．生成树给定一个无向图G，若G的一个生成子图T是树，则称T为G的生成树或支撑树．T的边称为树枝．生成树的结论任何连通图至少有一棵生成树．权与带权图n个结点的连通图G，每边指定一正数，称为权，每边带权的图称为带权图．G的生成树T中树枝的权之和称为T的权，记作W(T)．有向树如果一个有向图在不考虑边的方向时是一棵树，那么该有向图就是有向树．根树与树根一棵有向树T，若恰有一个顶点的入度为0，其余顶点的入度都为1，则称T为根树；入度为0的顶点称为树根；出度为0的顶点称为树叶；入度为1出度不为0的顶点称为内点；根与内点统称为分支点；从树根到T的任一顶点v的通路（顶点不同的路）的长度称为v顶点的层数；层数最大的顶点的层数称为树高．[例1]设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去条边后使之变成树．【答案】4【分析】运用教材中的定理5.1.1，可以作出正确选择．因为定理G变为树，则边数e＝6-1＝5。由于题中结点的总度数为9-5＝4条边才能使图G是树。【易错点】5.1.1中给出的图G为树的等价定义之一是图G连通且e＝v-1（e是边数，v是顶9条。所点数）．若图18，根据定理3.1.1，总度数应为边数2倍，可知此图中有边数以应该删去大家对集合中有的元素用集合形式表示的情形容易混淆，但这种类型考题中经常出现，大家一定要习惯．本题主要是检查大家对属于关系∈和包含关系⊆是否理解，能否正确运用。【提示】首先检查各选项给出的关系符号∈和⊆左边的式子是集合A的元素还是子集，然后判断选项中使用的关系符号是否正确，确定选项。[例2]已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为．[答案]5[分析]设无向树那么，由T的树叶数为x，因为树叶是度数为1的结点．定理3.1.1（握手定理）设G是一个图，其结点集＝－合为V，边集合为E，则得：4+3+2+x=2（8-1），即x=5．应填5．【易错点】题中没有直接给出图Ｇ的边数，而是给出了结点的总度数，这里大家要清楚总度数和边数之间的关系。【提示】设G是有ｎ个结点，ｍ条边的连通图，必须删去Ｇ的(m-n+1)条边，才能确定G的一棵生成树求最小生成树的方法主要有避圈法与破圈法．那到底什么是避圈法和破圈法？我们一起来看一看：避圈法：图G有n个顶点，以下算法产生的是最小生成树（避圈法由kfuskal给出.（1）选择最小的边e1，置边数i←1；（2）i=n-1结束，否则转3）；（3）设定已选定e1，e2,，…，ei，，在G中选取不同于e1，e2,，…，ei的边ei+1，使{e1，e2,，…，ei，ei+1}无回路，且ei+1是满足此条件的带权最小的边；（4）i←i+1，转2）．?破圈法：（1）初始令G0,=G,i←0；（2）若Gi中不含圈，则转（3）；否则，设C为Gi中的一个圈，ei为C上带权最大的边，令Gi+1=Gi-