去找 http://www.7zhao.net ｍ１ ｎ１ ｎ２ ｎｋ ｎｎ ｍ２ 当n≤2，m≥1时，同理是平面图 当m≥３同时n≥３时，Km,n是包含Ｋ３３的子图，因此不是平面图■ 9. 若一平面图与其对偶图同构，则称这个平面图为自对偶图。推导自对偶图必须满足的结点数n与边数m的关系，并找出一些自对偶图。 解：根据题意有，Ｇ与Ｇ同构，同时又是平面图，因此有如下关系式成立： ｎ－ｍ＋ｆ＝２ （１） 针对Ｇ图 ＊＊＊＊ ｎ－ｍ＋ｆ＝２ （２） 正对Ｇ图 ＊因为Ｇ与Ｇ同构，所以 ＊ ｎ＝ｎ＝ｆ，因此有：２ｎ－ｍ＝２，这就是自对偶平面图点和边需要满足的关系。下面是举例，请自己构造其对偶图并判别： ＊图例１ ■ 10.举例说明同构的平面图，其对偶图不一定同构。 解：举例如下： 图例２ 21
去找 http://www.7zhao.net 原图同构 ■ 对偶图不同构 11. 设某校某专业的学生在某学期共选修了n门选修课，期末考试前必须提前将这n门选修课程先考完，要求每天每人在下午考一门课，问至少需要几天考完这n门课？ 解：此类题可转化为求图的点色数的问题，可将课程集合作为图的点集合Ｖ＝｛ｖ１，ｖ２．．．ｖ．构造每门课程的学生选修集合Ｓ（ｖｉ），如果有同学同时选修了ｖｉ，和ｖｊ课程，ｎ｝则添加边（ｖｉ，ｖｊ）到图中。生成图Ｇ后，求Ｇ的点色数χ（Ｇ）即可■ 12. 在11题中，设n = 9，并且课程1和2，1和6，1和4，1和7，2和3，2和6，3和7，3和9，4和7，4和8，5和6，5和8，5和9都有人同时选，问至少几天能将9门课考完。 解：按１１题的要求，作出如下课程图： ｖ１ ｖ９ ｖ３ ｖ８ ｖ４ ｖ７ ｖ２ ｖ６ ｖ５ 所以至少需要３天才能考完■
完成题目［１，２，３，４，５，6，7，８，９，１０，１１，１２］
勘误：５题 － 简单平面（简单平面图）
22
去找 http://www.7zhao.net
习题十三
1. 构造(n, m)欧拉图使满足条件：(1) m和n奇偶性相同；(2) m和n奇偶性相反。 解：
m和n奇偶性相同 m和n奇偶性相反 ■ 2. 设G = (V,E)是一个具有2k（k>0)个奇数度结点的连通图。证明:G中必存在k条边不相重的简单道路P1,P2,…,Pk,使得E = E(P1)∪E(P2)∪ …∪E(Pk)。 证明：只要将这2k个奇度点分成两个集合V1 ={v1,v2…vk}，V2={u1,u2…uk},然后添加k条边（vi，ui），将G图变换成欧拉图G`。求出G` 的欧拉回路C，将C中的添加的k 条边删除，得到k条简单道路，这k 段简单道路包含了G中的全部边，结论得证■ 3. 设G = (V,E)是不含奇度结点的非平凡图。证明:G中必有k个边不相重的回路C1,C2,…,Ck,使得E = E ( C1) ∪ E ( C2 ) ∪ …∪E( Ck)。 证明：由题设可知，图G的每个分支是欧拉图，因此可求出每个分支欧拉回路Ci，且这些欧拉回路没有重复边，结论得证■
4. 设计一个由9个a,9个b,9个C组成的环形排列,使得由{a,b,c}组成的字长为3的27字中的每一个在排列中恰好出现一次。
解：由{a,b,c}组成的字长为3的串，一共有27个，分别为：
23
去找 http://www.7zhao.net {aaa,aab,aac,aba,abb,abc,aca,acb,acc,baa,bab,bac,bba,bbb,bbc,caa,cab,cac,cba,cbb,cbc,cca,ccb,cccc},题意为，将9个a,9个b,9个c组成环形排列，在这个环形排列中，任意不同的排列在一起的三个字母按相同的顺序写出来，都不相同。我们可以将{a,b,c}组成的字长为2的串{aa,ab,ac,ba,bb,bc,ca,cb,cc}作为有向图的节点，每个节点将有三条出边，出边分别表示在2字串上添加上{a,b,c}之母，并形成3字串。三条出边的汇入节点，分别是3字串的后两个字母所代表的2字节点，画出此图如下：
a aa c b a ab b a ba a a a a b ca c a b a cc c c c b bb b c b cb c b c b bc c ac 由图可知，这是一个欧拉图，因为每个节点有3条出边，3条入边。找出一条欧拉回路，并将边上的字母写出及得到合乎要求的环排列：aaababcccaacbcabbcbbacaccb ■ 5. 在图13.10中求中国邮递员问题的解。 解：略，请参考书中解法■ 6. 设G是有两个奇度点的连通图,设计一个构造G的欧拉道路的算法。
解：step1: 添加连接两个奇度点的边 Step2: 调用一般的欧拉回路的算法
Step3: 在回路中删除添加的边■
7. n为何值时，无向完全图Kn是欧拉图？n为何值时，无向完全图Kn仅存在欧拉道路而不存在欧拉回路？
24