离散数学王元元习题解答 (9)[题型借鉴].doc

《离散数学王元元习题解答 (9)[题型借鉴].doc》由会员分享，可在线阅读，更多相关《离散数学王元元习题解答 (9)[题型借鉴].doc（22页珍藏版）》请在三一文库上搜索。

1、第三篇 图论第八章 图8.1 图的基本知识 内容提要8.1.1 图的定义及有关术语 定义8.1 图（graph）G由三个部分所组成： （1）非空集合V(G)，称为图G的结点集，其成员称为结点或顶点（nodes or vertices）。 （2）集合 E(G)，称为图G的边集，其成员称为边(edges)。 I（3）函数G：E(G)(V(G)，V(G)，称为边与顶点的关联映射（associatve mapping）。这里（V(G)，V(G)）称为VG的偶对集，其成员偶对（pair）形如（u，v），u，v为结点，它们未必不同。G(e) = (u,v)时称边e关联端点u，v。当(u,v)用作序偶时(V

2、(G)，V(G) =V(G) V(G)，e称为有向边，e以u为起点,以v为终点, 图G称为有向图（directed graph）；当(u,v)用作无序偶对时，(u,v) = (v,u)，称e为无向边（或边），图G称为无向图（或图）。图G常用三元序组,或来表示。显然，图是一种数学结构，由两个集合及其间的一个映射所组成。 定义8. 2 设图G为。 （l）当V和E为有限集时，称G为有限图，否则称G为无限图。本书只讨论有限图。 （2）当G为单射时，称G为单图；当G为非单射时，称G为重图，又称满足(e1) = (e2)的不同边e1,e2,为重边,或平行边。 （3）当(e)(v,v)（或）时，称e为环（l

3、oops）。无环和重边的无向单图称为简单图。当G为有限简单图时，也常用（n，m）表示图G，其中n = |V |，m = |E | 。 （4）为双射的有向图称为有向完全图；对每一(u，v)，u v，均有e使(e)(u,v)的简单图称为无向完全图，简称完全图，n个顶点的完全图常记作Kn。 （5）在单图G中，(e)(u,v)（或）时，也用(u,v)(或)表示边e，这时称u，v邻接e, u,v是e的端点（或称u为e的起点，v为e的终点）;也称e关联结点u , v 。不是任何边的端点的结点都称为孤立结点，仅由孤立结点构成的图（E = ）称为零图。 （6）当给G赋予映射f：VW，或g：EW，W为任意集合，

4、常用实数集及其子集,此时称G为赋权图，常用或或表示之。f(v)称为结点v的权，g(e)称为边e的权。8.1.2 结点的度 定义8.3 在无向图中，结点v的度（degree）d(v)是v作为边的端点的数目。在有向图中，结点的度d(v)是v的出度d+(v)（out-degree）与入度d-(v)（in-degree）的和；v的出度是v作为有向边起点的数目，v的入度是v作为有向边终点的数目。 定理8.1 对任意图G，设其边数为m, 顶点集为v1，v2，vn，那么 定理8.2 图的奇数度顶点必为偶数个。 定理8.3 自然数序列（a1,a2,an）称为一个度序列，如果它是一个图的顶点的度的序列。（a1,

5、a2,an）为一度序列，当且仅当为一偶数。定义8.4 一度的顶点称为悬挂点（pendant nodes）。定义8.6 各顶点的度均相同的图称为正则图（regular graph）。各顶点度均为k的正则图称为k-正则图。8.1.3 图运算及图同构 由于图由结点集、边集及关联映射组成，因此对图可作种种与集合运算相类似的运算。 定义8.6 设图G1，G2，称G1为G2的子图（subgraph），如果V1V2，E1E2，1 2。称G1为G2的真子图，如果G1是G2的子图，且G1 G2。称G1为G2的生成子图（spanning subgraph），如果G1是G2的子图，且V1 = V2。 定义8.7 设

6、图G1，G2，且1与2是相容的，即对任一x，若1(x) = y1, 2(x) = y2，则y1= y2，从而12为一函数。 （1）G1与G2的并，记为G1G2G3，其中V3 = V1V2，E3 = E1E2，3 = 12。 （2）G1与G2的交,记为G1G2 = G3 = ，其中V3 = V1V2，E3 = E1E2，3 = 12。 （3）若G1为G2的子图，则可定义G2对G1的差，记为G2G1G3，其中E3 = E2 E1，V3V2，3 = 2E3。 （4）G1与G2的环和，记为G1G2， G1G2(G1G2)(G1G2) （5）若G为简单图，则可定义G的补，记为G，若 |V(G)| = n

7、，则 G= KnG 定义8.8 设图G （1）Ge表示对G作删除边e的运算，Ge = ，其中EEe，= E。 （2）Gv表示对G作删除顶点v的运算，Gv = ，其中V= Vv，EEe | e以v为端点，E。 （3）边e切割运算。设G中 (e) = (u,v),对G作边e切割得G，其中，VVv，E= (Ee)e1,e2, = ()，（4）顶点v贯通运算。设G中顶点v恰为边e1,e2的端点，且 (e1) = (u,v)， (e2) = (w,v)。对G作顶点v贯通得G，其中V= Vv, E= (Ee1,e2)e, =( ,)。 切割与贯通是互逆的，两者常被称为同胚运算。 定义8.9 设G1，G2为

8、两个图，称G1与G2同构（isomorphic），如果存在双射f：V1V2，双射g：E1E2，使得对每一边eE1， 1(e)(u,v)（或）当且仅当2(g(e) = (f(u),f(v)（或） 当限于讨论简单图时，可以用顶点的偶对表示边，即当(e) (u,v)时，边e用(u,v)来表示。这时两图同构的条件可以简化为 (u,v)E1当且仅当(f(u),f(v)E2 习题解答练习8.11、 想一想，一只昆虫是否可能从立方体的一个顶点出发，沿着棱爬行、它爬行过每条梭一次且仅一次，并且最终回到原地？为什么？解 不可能。可将立方体的一个顶点看作图的一个顶点，把立方体的棱看作图的边，那么该图的四个顶点都是

9、三度的，因此不可能从一个顶点出发，遍历所有的边一次且仅一次，并且最终回到原顶点。2、 请设想一张图，它的64个顶点表示国际象棋棋盘的64个方格，顶点间的边表示:在这两个顶点表示的方格之间可以进行“马步”的行走。试指出其顶点有哪几类（依其度分类），每类各有多少个顶点。解 其顶点有5类：二度顶点合计4个,三度顶点合计8个,四度顶点,合计20个,六度顶点, 合计16个顶点,八度顶点, 合计16个顶点。2344443234666643468888644688886446888864468888643466664323444432 3、（l）证明：n个顶点的简单图中不会有多于条边。（2）n个顶点的有向完

10、全图中恰有条边。证（l）n个顶点的简单完全图的边数总和为 （2）n个顶点的有向完全图的边数总和为4、证明: 在任何n (n2)个顶点的简单图G中，至少有两个顶点具有相同的度。证 如果G有两个孤立顶点，那么它们便是具有相同的度的两个顶点。如果G恰有一个孤立顶点，那么我们可对有n 1 个顶点但没有孤立顶点的G（它由G删除孤立顶点后得到）作下列讨论。不妨设G没有孤立顶点，那么G 的n个顶点的度数应是：1，2，3，n1 这n1种可能之一，因此必定有两个顶点具有相同的度。5、图8.10是一个迷宫,其中数字表示通道、和死胡同(包括目标) 。请用一个图来表示这个迷宫(用结点表示通道、和死胡同(包括目标),用

11、边表示它们之间的可直接到达关系。 图8.10解2 1 183 17 45 20 21 16 15 6 19 22 147 138 9 10 11 12 6、在晚会上有n个人，他们各自与自己相识的人握一次手。已知每人与别人握手的次数都是奇数，问n是奇数还是偶数。为什么？ 解 n是偶数。用n个顶点表示n个人，顶点间的一条边表示一次握手，可构成一个无向图。若n是奇数，那么该图的顶点度数之和为奇数（奇数个奇数的和），这是不可能的，因此n是偶数。7、n个城市间有m条相互连接的直达公路。证明：当时，人们便能通过这些公路在任何两个城市间旅行。证 用n个顶点表示n个城市，顶点间的边表示直达公路，据题意需证这n

12、个城市的公路网络所构成的图G是连通的。反设G不连通，那么可设G由两个不相关的子图（没有任何边关联分别在两个子图中的顶点）G1，G2组成，分别有n1，n2个顶点，从而，n = n1+n2，n1 1，n2 1。 由于各子图的边数不超过 (见练习8.l之3)，因此G的边数m满足： 与已知矛盾，故图G是连通的。（本题是定理8.8的特例，当然也可以应用这一定理和它的证明方法来解题。） *8、（1）证明：序列（7，6，5，4，3，3, 2），（6，5，5，4，3，2，2）以及（6，6，5，4，3，3，1）都不是简单图的度序列。 （2）若自然数序列（d1,d2,dn）满足d1d2dn，那么当它为一简单图的度

13、序列时必有 （a）为偶数；（b）对任一k，1kn , k(k-1)+。证（1）由于7个顶点的简单图中不可能有7度的顶点，因此序列（7，6，5，4，3，3, 2）不是简单图的度序列。序列（6，5，5，4，3，2，2）中有三个奇数，因此它不是简单图的度序列。序列（6，6，5，4，3，3，1）中有两个6，若它是简单图的度序列，那么应有两个顶点是6度顶点，于是它们都要与其它所有顶点邻接，该图就不会有一度的顶点，与序列中末尾的1冲突。故（6，6，5，4，3，3，1）也不是简单图的度序列。证（2）为偶数是显然的。考虑图中的k个顶点（k=1,2,n）,这k个顶点的生成子图的度数总和 k(k-1)，而其余nk

14、 个顶点vk+1,vk+2, ,vn, 可使 v1,v2, ,vk增加的度数不会超过 因此我们有 k(k-1)+。 9、画出图8.11中图的补图及它的一个生成子图。 图8.11 解 补图 生成子图10、一个简单图，如果同构于它的补，则该图称为自补图。（1）给出一个4个顶点的自补图。（2）给出一个5个顶点的自补图。（3）是否有3个顶点或6个顶点的自补图？（4）证明一个自补图一定有4k或4k1个顶点（k为正整数）。解 （1）4个顶点的自补图： （2）5个顶点的自补图：（3）没有。（4）证 设G为自补图，有n 个顶点。我们已知n 个顶点的完全图有 条边，因此G应恰有条边。故或者n是4的整数倍，或者n

15、1是4的整数倍，即图G 一定有4k或4k1个顶点（k为正整数）。 11、（l）证明图 8.12中（a）与（b）同构。 A a bD C B c E F d e k f g G H h I J i j (a) (b) 图8.12（2）给出所有不同构的4个结点的简单图的图示。（l）证 在图（a）图（b）间建立双射h vABDIJCEGHFh(v)abdihcfjkg可逐一验证 (不赘) (u,v)E(a)当且仅当 (h(u),h(v)E(b)（2）所有不同构的4个结点的简单图的图示有如下11个： *12、Kn表示n个顶点的无向完全图。 （l）对K6的各边用红、蓝两色着色，每边仅着一种颜色，红、蓝任

16、选。证明：无论怎样着色，图上总有一个红色边组成的K3或一个蓝色边组成的K3。（2）用（l）证明下列事实：任意6个人之间或者有三个人相互认识，或者有3个人相互都不认识。证（l）考虑K6的顶点V，与之关联的边有5条，其中至少有3条着同一颜色。不妨设均着红色，这三边的另一个端点分别是u1,u2,u3 (如图所示)。再考虑关联u1,u2,u3的三条边。如果它们中有一条着红色的边，那么我们就已经得到一个红色边组成的K3，如果它们中没有着红色的边，那么我们就能够得到一个蓝色边组成的K3。v u2u1 u3证（2）用六个顶点表示6个人，顶点间红色边表示人员间相互认识，顶点间蓝色边表示人员间相互不认识，便产生

17、一个边着红、蓝两色的完全图K6。利用（1）的结论，可以断定6个人之间或者有三个人相互认识，或者有3个人相互都不认识。8.2 路径、回路及连通性 内容提要8.2.1 路径与回路 定义8.10 图G的顶点v1到顶点vl的拟路径（pseudo path）是指如下顶点与边的序列： v1 ,e1 ,v2 ,e2 ,v3 , ,v l-1 ,el-1 ,vl 其中v1 ,v2 ,v3 , ,v l-1 ,vl为G的顶点e1 ,e2 , ,el-1 为G的边，且ei( i= 1,2, ,l-1 )以vi及vi+1为端点，（对有向图G，ei以vi为起点，以vi+1为终点），拟路径的边数l1称为该拟路径的长度。

18、当ei( i= 1,2, , l-1 )各不相同时，该拟路径称为路径（walk），又当vi(i = 1,2, ,l)各不相同时(除v1与vl)，则称此路径为通路（Path）。v1vl的路径称为闭路径（closed walk）；v1= vl的通路称为回路（circuit）。 当讨论限于简单图或无平行边的有向图时，上述拟路径、路径、通路等可用顶点序列来表示，例如用（v1 ,v2 ,v3 , ,v l-1 ,vl）代替式v1 ,e1 ,v2 ,e2 ,v3 , ,v l-1 ,el-1 ,vl 。 定理8.4 在有n个顶点的图G中，如果有从顶点u到v（u v）的拟路径，那么从u到v必有路径，并且必有

19、长度不大于n 1 的通路。 定理8. 5 在具有n个顶点的图G中，如果有从v到v的闭路径，那么必定有一条从v到v的长度不大于n的回路。8.2.2 连通性 定义8.11 称图中顶点u到v是可达的（accesible），如果u = v，或者有一条u到v的路径。 定义8.12 称无向图G是连通的（connected），如果G的任何两个顶点都是相互可达的。称有向图G是强连通的，如果G的任何两个顶点都是相互可达的;称有向图G是单向连通的，如果G的任何两个顶点中，至少从一个顶点到另一个顶点是可达的；称有向图G是弱连通的，如果G的有向边被看作无向边时是连通的。 定义8.13 图G称为图G的连通分支（conn

20、ected components），如果G是G的子图，G是连通的，并且不存在G的真子图G，使G是连通的，且G以G为真子图。 定义 8.14 设G为有向图G的子图，若 G是强连通的（单向连通的、弱连通的），且G没有真子图G使G为其真子图，而G强连通（单向连通、弱连通），那么称G为G的一个强分图（单向分图、弱分图）。 定理8. 6 一个图G是不连通的，当且仅当G的顶点集V可以分成两个不交的非空子集V1和V2，使得任何边都不以V1的一个顶点和V2一个顶点为其两端点。 定理8.7 如果图G恰有两个不同的奇数度的顶点u，v，那么u到v必定是可达的。定理8.8 若图G为具有n个顶点、k个连通分支的简单图，

21、那么G至多有条边。 8.2.3 连通度 定义 8.15 设S为连通图G的顶点集V的子集，称S为G的点割集（cut-set of nodes）,如果从G中删除S中的所有顶点后得到的图不连通，但S的任何真子集均无这一特性。当点割集为单元素集合v时，v称为割点（cut-nodes）。 定义8.16 (G)称为G的点连通度（node-connectivity），定义如下： 定义8.17 设S为连通图G边集E的子集，称S为G的边割集（cut-set of edges），或割集，如果从G中删除S的所有边后所得的图是不连通的，但S的任何真子集均无这一特性。当割集为单元素集e时，称e为割边（cut-edges

22、）。 定义8.18 (G)称为图G的边连通度（edge-connectivity），定义如下： 定理8.9 对任何简单无向图G， (G) (G) (G) 定理8.10 设G为n个顶点、m条边的简单连通图，那么(G) 。 习题解答练习8.21、 证明定理8.5。证 设n个顶点的图G中，有从v到v的闭路径，表示为 （v,v1,v2,vk,v）如果v,v1,v2, ,vk中没有相同顶点（因而不多于n个），那么它便是一条从v到v的长度不大于n的回路。如果v,v1,v2, ,vk中有相同顶点vi=vj，例如 （v,v1, vi, vj, vj+1,vk,v）那么删除vi到vj的闭路径，得到（v,v1,

23、vi, vj+1,vk,v）仍然为从v到v的闭路径。 如此不断删除闭路径内相同顶点构成的闭路径，最终必可得到一条从v到v的长度不大于n的回路。2、 证明：在简单无向图G中，从结点u到结点v,如果既有奇数长度的通路又有偶数长度的通路，那么G中必有一奇数长度的回路。证 设G中，从结点u到结点v的奇数长度的通路为O ，偶数长度的通路为E。对O和E的除结点u和v的相交结点的数目归纳k。k=0,那么O和E恰好构成G的奇数长度的回路。 设奇数长度的通路与偶数长度的通路的相交结点的数目少于k时，命题成立。 u 1 2 k v设图G中，从结点u到结点v的奇数长度的通路与偶数长度的通路有k个相交结点，如图所示：

24、考虑结点u到结点k,如果从结点u到结点k,既有奇数长度的通路又有偶数长度的通路，那么据归纳假设，其中有一奇数长度的回路，因而G中必有一奇数长度的回路。如果从结点u到结点k的两条通路均为偶数长度，或均为奇数长度，那么结点k到结点v必然既有奇数长度的通路又有偶数长度的通路，因而构成一奇数长度的回路。3、 证明：若简单无向图G是不连通的，那么G必定是连通的。证 设简单无向图G是不连通的，那么G由两个不相关的子图（没有任何边关联分别在两个子图中的顶点）G1，G2组成，分别有顶点，u1,u2,uk和v1,v2,vl。由于边（ui ,vj）均不在G中（i=1,2,k, j=1,2,l）因此（ui ,vj）

25、全部在G中，从而G是连通的。 4、有向图可用于表示关系，图8.18表示的二元关系是传递的吗？说说如何由有向图判定关系的传递性。求图8.18表示的二元关系的传递闭包，说说构作有向图传递闭包的方法。 a b c a b c 图8.18解 图8.18表示的二元关系不是传递的。有向图表示的关系是传递的，当且仅当对图中任意两个结点u,v，如果有从u到v的路径，则必有从u到v的边。 图8.18表示的二元关系的传递闭包如图8.18（b）所示。构作有向图传递闭包的方法是：对图中任意两个结点u,v，如果有从u到v的路径，则添加从u到v的边。 5、给出图8.19中有向图的强分图，单向分图和弱分图，作出它的凝聚图。

26、v1 v2 v7 v10 v4 v3 v8 v9 v5 v6 图8.19解 图8.19中有向图的强分图有：v1,v2, , v3,v4,v5,v6, ,v7,v8,v9,图8.19中有向图的单向分图有：v1,v2,v3,v4,v5,v6, ,v7,v8,v9,v10,v1,v2 v3,v4,v5 v7,v8,v9 v10 v6图8.19的凝聚图： 6、有7人a，b，c，d，e，f，g分别精通下列语言，问他们7人是否可以自由交谈（必要时借助他人作翻译）。 a 精通英语。 b 精通汉语和英语。 c 精通英语、俄语和意大利语。 d 精通日语和英语。 e 精通德语和意大利语。 f 精通法语、日语和俄语

27、。g 精通法语和德语。 ab d c e g f解 下图中7个顶点表示7个人，关联两个顶点的边表示两个人同时精通某一种语言：由于该图是连通的，因此他们7人是可以自由交谈（必要时借助他人作翻译）。7、证明：一个有向图是单向连通的，当且仅当它有一条经过每一结点的路径。证 充分性是显然的。必要性：设有向图G是单向连通的，P是G中的一条路径，起点为u1,终点为uk。如下延长这一路径：考虑路径外的任意顶点w,若（1）有顶点w到u1的路径,则我们如愿。（2）有顶点uk到w的路径,则我们如愿。否则，由于有向图是单向连通的，（3）有顶点w到uk的路径,和顶点uk-1到w的路径, 则我们如愿。否则，由于有向图是

28、单向连通的， uk-1u1 uk w（4）有顶点w到uk的路径,和顶点uk-2到w的路径, 则我们如愿。否则， wu1 uk-2 uk-1 uk （5）如此等等，有顶点w到uk的路径,和顶点u1到w的路径, 则我们如愿。 wu1 uk-2 uk-1 uk 如上不断延长这一路径，直至产生一条经过每一结点的路径。 8、称d(u,v)为图G中结点u，v间的距离： d称为图G的直径，如果dmaxd(u,v) | u,vV。试求图8.20中图的直径，(G) ,(G) ,(G)，并指出一个点割集和一个边割集。 图8.20 解 d3 ，(G)=3 ,(G)=3 ,(G)=3 。9、顶点v是简单连通图G的割点

29、，当且仅当G中存在两个顶点v1，v2，使v1到v2的通路都经过顶点v 。试证明之。证充分性是显然的。必要性：设顶点v是简单连通图G的割点，如果不存在两个顶点v1，v2，使v1到v2的通路都经过顶点v，那么对任意两个顶点v1，v2，都有一条通路不经过顶点v，因而删除顶点v不能使G不连通，与v是简单连通图G的割点矛盾。故G中必存在两个顶点v1，v2，使v1到v2的通路都经过顶点v 。10、边e是简单连通图G的割边，当且仅当e不在G的任一回路上。试证明之。证 设e是简单连通图G的割边，其端点为u,v 。删除边e后，u,v应在两个不同的连通分支中。若e在G的一条回路上，那么删除边e后，u,v应仍在一条

30、通路上，矛盾。故e不在G的任一回路上。反之，设e不在G的任一回路上，而e不是简单连通图G的割边。那么G-e仍是连通的，故还有u到v的一条通路，从而这条通路连同边e构成G中的一条回路，矛盾。因此边e是简单连通图G的割边 11、试用有向图描述下列问题的解： 某人m带一条狗d，一只猫c和一只兔子r过河。m每次游过河时只能带一只动物，而没人管理时，狗与兔子不能共处，猫和兔子也不能共处。问m怎样把三个动物带过河去？（提示：用结点代表状态，状态用序偶来表示，这里S1，S2分别是左岸和右岸的人及动物集合，例如初始状态为。解 描述上述问题的有向图如下： 12、有向图可以刻划一个系统的状态转换，例如用图8.21

31、中的有向图可以描述识别010*10序列的状态转换系统。其中S为初始状态，在此读入序列，然后依序列中符号转入后续状态（读到0进入S1，读到1进入S2，如此等等）。S4表示读完序列010*10应进入的最后状态，S5表示读完一个非010*10序列应进入的最后状态。 试自行构作识别序列01(10)*10的有向图刻划的状态转换系统。 0S 0 S1 1 S2 1 S3 0 S4 1 0 1 S5 （上文中w*表示空字或重复任意多次w所得的字。） 图8.21 S3 0 1S S1 S2 S4 S5 0 1 1 0 1 0 1 S6 解 识别序列01(10)*10的有向图刻划的状态转换系统如下：8.3欧拉图

32、与哈密顿图 内容提要8. 3. 1欧拉图与欧拉路径 定义8.19 图G称为欧拉图（Euler graph），如果图G上有一条经过G的所有顶点、所有边的闭路径。图G称为欧拉路径（Euler walk），如果图G上有一条经过G所有顶点、所有边的路径。 定理8.11 无向图G为欧拉图当且仅当G连通，并且所有顶点的度都是偶数。有向图G为欧拉图，当且仅当G是弱连通的，并且每个顶点的出度与入度相等。 定理8.12 如果G为欧拉图，那么G可分成若干个（一个或几个）回路。定理8.13 无向图G为欧拉路径(非欧拉图)，当且仅当G连通，并且恰有两个顶点的度是奇数。有向图G为欧拉路径(非欧拉图)，当且仅当G连通，并

33、且恰有两个顶点的入度与出度不等，它们中一个的出度比入度多1，另一个入度比出度多l。8.3.2 哈密顿图及哈密顿通路 定义8.20 无向图G称为哈密顿图（Hamilton graph），如果G上有一条经过所有顶点的回路（也称这一回路为哈密顿回路）。称无向图有哈密顿通路(非哈密顿图)，如果G上有一条经过所有顶点的通路(非回路)。 定理8.14 设图G为具有n个顶点的简单无向图，如果G的每一对顶点的度数之和都不小于n 1 ，那么G中有一条哈密顿通路；如果G的每一对顶点的度数之和不小于n，且n3，那么G为一哈密顿图。 定理8.15 当n为不小于3的奇数时，Kn上恰有条互相均无任何公共边的哈密顿回路。 定义8.21 图G称为可2-着色（2-chromatic），如果可用两种颜色给G的所有顶点着色，使每个顶点着一种颜色，而同一边的两个不同端点必须着不同颜色。 定理8.16 设图G是可2-着色的。如果G是哈密顿图，那么着两种颜色的顶点数目相等；如果G有哈密顿通路，那么着两种颜色的顶点数目之差至多为一。习题解答练习8. 31、试