离散数学第八章一些特殊的图知识点总结.doc

图论部分第八章、:定义设无向图G=<V,E>,若能将V划分成V1和V2(V1V2=V,V1V2=),使得G中的每条边的两个端点都一个属于V1,另一个属于V2,则称G为二部图,记为<V1,V2,E>,:又若G是简单图,且V1中每个顶点都与V2中每个顶点相邻,则称G为完全二部图,记为Kr,s,其中r=|V1|,s=|V2|.注意::设G=<V,E>,匹配(边独立集):任2条边均不相邻的边子集极大匹配:添加任一条边后都不再是匹配的匹配最大匹配:边数最多的匹配匹配数:最大匹配中的边数,记为1例 下述3个图的匹配数依次为3,3,:(vi,vj)Mv为M饱和点:M中有边与v关联v为M非饱和点:M中没有边与v关联M为完美匹配:G的每个顶点都是M饱和点定理(Hall定理)设二部图G=<V1,V2,E>中,|V1||V2|.G中存在从V1到V2的完备匹配当且仅当V1中任意k个顶点至少与V2中的k个顶点相邻(k=1,2,…,|V1|).由Hall定理不难证明,上一页图(2)=<V1,V2,E>中,如果存在t1,使得V1中每个顶点至少关联t条边,而V2中每个顶点至多关联t条边,“相异性条件”,:图中行遍所有顶点且恰好经过每条边一次的通路. 欧拉回路::::,,其中一个入度比出度大1,另一个出度比入度大1,:::::,=<V,E>是哈密顿图,则对于任意V1V且V1,均有 p(GV1)|V1|.证 设C为G中一条哈密顿回路,有p(CV1)|V1|.又因为CG,故p(GV1)p(CV1)|V1|.  几点说明定理中的条件是哈密顿图的必要条件,. 由定理可知,Kr,s当sr+,Kr,r是哈密顿图,而Kr,r+ 设G为n阶无向连通简单图,若G中有割点或桥, (1)设v为割点,则p(Gv)2>|{v}|=,G不是哈密顿图.(2)若G是K2(K2有桥),,(1),,若任意两个不相邻的顶点的度数之和大于等于n1,,若任意两个不相邻的顶点的度数之和大于等于n,则G中存在哈密顿回路,(回路)的存在性(续)定理中的条件是存在哈密顿通路(回路)的充分条件,,设G为长度为n1(n4)的路径,它不满足定理中哈密顿通路的条件,,它不满足定理中哈密顿回路的条件,,当n3时,?观察出一条哈密顿回路例如右图(周游世界问题)中红边给出一条哈密顿回路,,此图不满足定理的条件.?满足充分条件例如当n3时,Kn中任何两个不同的顶点u,v,均有d(u)+d(v)=2(n1)n,,已知每人至少与其余7人中的4人有共同语言,问服务员能否将他们安排在同一张圆桌就座,使得每个人都能与两边的人交谈?=<V,E>,其中V={v|v为与会者},E={(u,v)|u,vV,u与v有共同语言,且uv}.,vV,d(v),u,vV,有d