《第二篇图论-习题.pptVIP

* 图论部分 第五章 图的基本概念 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 习题课1 例1 设d=(d1,d2,…,dn),其中di为非负整数，i=1,2,…,n。若存在n个顶点的(简单)无向图,使得顶点vi的度为di，则称d是可图解的。下面给出的各序列中哪些是可图解的？哪些不是，为什么？ （1）（1,1,1,2,3）； （6）（1,3,3,3）； （2）（0,1,1,2,3,3）；（7）（2,3,3,4,5,6）； （3）（3,3,3,3）； （8）（1,3,3,4,5,6,6）； （4）（2,3,3,4,4,5）；（9）（2,2,4）； （5）（2,3,4,4,5）； （10）(1,2,2,3,4,5）。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 例2 画出具有 6、8、10、…、2n个顶点的三次图； 是否有7个顶点的三次图？ 例3 无向图有21条边，12个3度数顶点，其余顶点的度数均为2，求的顶点数。 (p=15) 例4 下列各无向图中有几个顶点？ (1) 16条边，每个顶点的度为2； (2) 21条边，3个4度顶点，其余的都为3度数顶点； (3) 24条边，各顶点的度数相同。 (1. p=16; 2. p=13; 3. pk=48讨论) 例5 设图G中有9个顶点，每个顶点的度不是5就是6。证明:G中至少有5个6度顶点或至少有6个5度顶点。 例6 有n个药箱，若每两个药箱里有一种相同的药，而每种药恰好放在两个药箱中，问药箱里共有多少种药？ Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 例7 设G是有个p顶点，q条边的无向图，各顶点的度数均为3。则 (1)若q=3p-6,证明:G在同构意义下唯一，并求p,q。 (2)若p=6，证明:G在同构的意义下不唯一。 例8 已知p阶(简单)无向图中有q条边，各顶点的度数 均为3，又2p=q+3，试画出满足条件的所有不同 构的G。 例9 9个学生，每个学生向其他学生中的3个学生各送一张贺年卡。确定能否使每个学生收到的卡均来自其送过卡的相同人？为什么？ 解:否，不存在9（奇数）个顶点的3－正则图。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 习题课 2 例10 若G是一个恰有两个奇度顶点u和v的无向图，则 （1）顶点u与v连通；（2）G连通?G+uv连通。 例1 设G为p阶简单无向图，p＞2且p为奇数，G和G的补图GC 中度数为奇数的顶点的个数是否一定相等？试证明你的结论。 例2 设V={v1,v2,…,vp}，计算以V为顶点集的无向图的个数是多少？(KP有多少个生成子图) 例3 设V={v1,v2,…,vp},q≤p(p-1)/2，计算以V为顶点集具有q条边的无向图的个数是多少？ 例4 设G是（p,q）图，r≤q，则具有r条边的G的生成子图有多少？ 答案： 2p(p-1)/2 ，Cqp(p-1)/2 ，Crq。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. 例5 证明：若无向图G是不连通的，则G的补图GC是连通的。（逆命题不成立） 例6 将无向完全图K6的边随意地涂上红色或绿色,证明:无论何种涂法,总有红色的K3或绿色K3。 例7 给无向完全图Kp(p≥7)的各边随意地涂上红色或绿色，若已知从某点v0引出的p-1条边中至少有6条边涂红色，则Kp存在红色的K4或绿色的K3。 例8 有17位学者，每2位讨论3篇论文中的一篇且仅一篇，证明：至少有3位学者，他们相互讨论的是同一篇论文。 Evaluation only. Created with Aspose.Slides for .