《离散数学王元元习题解答21639.pdf》由会员分享，可在线阅读，更多相关《离散数学王元元习题解答21639.pdf（34页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第三篇 图论 第八章 图 图的基本知识 内容提要 8.1.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)用作序
2、偶时(V(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、边。（3）当(e)(v,v)（或）时，称 e 为环（loops）。无环和重边的无向单图称为简单图。当 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。不是任何边的端点的结点都称为孤立结点，仅由孤立结点构成的图
4、（E=?）称为零图。（6）当给 G 赋予映射 f：VW，或 g：EW，W 为任意集合，常用实数集及其子集,此时称 G 为赋权图，常用或或表示之。f(v)称为结点 v 的 权，g(e)称为边 e 的权。8.1.2 结点的度 定义 在无向图中，结点 v 的度（degree）d(v)是 v 作为边的端点的数目。在有向图中，结点的度 d(v)是 v 的出度 d+(v)（out-degree）与入度d-(v)（in-degree）的和；v 的出度是 v 作为有向边起点的数目，v 的入度是 v 作为有向边终点的数目。定理 对任意图 G，设其边数为 m,顶点集为v1，v2，vn，那么 niimvd12)(定
5、理 图的奇数度顶点必为偶数个。定理 自然数序列（a1,a2,an）称为一个度序列，如果它是一个图的顶点的度的序列。（a1,a2,an）为一度序列，当且仅当niia1为一偶数。定义 一度的顶点称为悬挂点（pendant nodes）。定义 各顶点的度均相同的图称为正则图（regular graph）。各顶点度均为 k 的正则图称为 k-正则图。8.1.3 图运算及图同构 由于图由结点集、边集及关联映射组成，因此对图可作种种与集合运算相类似的运算。定义 设图 G1，G2，称 G1 为 G2 的子图（subgraph），如果 V1?V2，E1?E2，1?2。称 G1 为 G2 的真子图，如果 G1
6、是 G2 的子图，且 G1?G2。称 G1 为 G2 的生成子图（spanning subgraph），如果 G1 是 G2 的子图，且 V1=V2。定义 设图 G1，G2，且 1 与 2是相容的，即对任一 x，若 1(x)=y1,2(x)=y2，则 y1=y2，从而1?2 为一函数。（1）G1 与 G2 的并，记为 G1?G2G3，其中 V3=V1?V2，E3=E1?E2，3=1?2。（2）G1 与 G2 的交,记为 G1?G2=G3=，其中 V3=V1?V2，E3=E1?E2，3=1?2。（3）若 G1 为 G2 的子图，则可定义 G2 对 G1 的差，记为 G2G1G3，其中 E3=E2
7、 E1，V3V2，3=2?E3。（4）G1 与 G2 的环和，记为 G1?G2，G1?G2(G1?G2)(G1?G2)（5）若 G 为简单图，则可定义 G 的补，记为 G，若?V(G)?=n，则 G=KnG 定义 设图 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，其中，VV?v，E=(Ee)?e1,e2,=()?，（4）顶点 v 贯通运算。设 G 中顶点 v 恰为边 e
8、1,e2 的端点，且 (e1)=(u,v)，(e2)=(w,v)。对 G 作顶点 v 贯通得 G，其 中V=V v,E=(E e1,e2)?e,=(,)?。切割与贯通是互逆的，两者常被称为同胚运算。定义 设 G1，G2为两个图，称 G1与 G2 同构（isomorphic），如果存在双射 f：V1V2，双射 g：E1E2，使得对每一边 e?E1，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
9、 习题解答 练习 1、想一想，一只昆虫是否可能从立方体的一个顶点出发，沿着棱爬行、它爬行过每条梭一次且仅一次，并且最终回到原地为什么 解 不可能。可将立方体的一个顶点看作图的一个顶点，把立方体的棱看作图的边，那么该图的四个顶点都是三度的，因此不可能从一个顶点出发，遍历所有的边一次且仅一次，并且最终回到原顶点。2、请设想一张图，它的 64 个顶点表示国际象棋棋盘的 64 个方格，顶点间的边表示:在这两个顶点表示的方格之间可以进行“马步”的行走。试指出其顶点有哪几类（依其度分类），每类各有多少个顶点。解 其顶点有 5 类：二度顶点合计 4 个,三度顶点合计 8 个,四度顶点,合计 20 个,六度顶
10、点,合计 16 个顶点,八度顶点,合计 16 个顶点。2 3 4 4 4 4 3 2 3 4 6 6 6 6 4 3 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 4 6 8 8 8 8 6 4 3 4 6 6 6 6 4 3 2 3 4 4 4 4 3 2 3、（l）证明：n 个顶点的简单图中不会有多于2)1(nn条边。（2）n 个顶点的有向完全图中恰有2n条边。证（l）n 个顶点的简单完全图的边数总和为 2)1(12)2()1(nnnn（2）n 个顶点的有向完全图的边数总和为 2nnnnnnn 4、证明:在任何 n(n2)个顶点的简单图 G
11、 中，至少有两个顶点具有相同的度。证 如果 G 有两个孤立顶点，那么它们便是具有相同的度的两个顶点。如果 G 恰有一个孤立顶点，那么我们可对有 n 1 个顶点但没有孤立顶点的 G（它由 G 删除孤立顶点后得到）作下列讨论。不妨设 G 没有孤立顶点，那么 G 的 n 个顶点的度数应是：1，2，3，n1 这 n1 种 可能之一，因此必定有两个顶点具有相同的度。5、图是一个迷宫,其中数字表示通道、和死胡同(包括目标)。请用一个图来表示这个迷宫(用结点表示通道、和死胡同(包括目标),用边表示它们之间的可直接到达关系。图 解 6、在晚会上有 n 个人，他们各自与自己相识的人握一次手。已知每人与别人握手的
12、次数都是奇数，问 n 是奇数还是偶数。为什么 解 n 是偶数。用 n 个顶点表示 n 个人，顶点间的一条边表示一次握手，可构成一个无向图。若 n 是奇数，那么该图的顶点度数之和为奇数（奇数个奇数的和），这是不可能的，因此 n 是偶数。7、n 个城市间有m条相互连接的直达公路。证明：当2)2)(1(nnm时，人们便能通过这些公路在任何两个城市间旅行。2 1 18 3 17 4 5 20 21 16 15 证 用 n 个顶点表示 n 个城市，顶点间的边表示直达公路，据题意需证这 n 个城市的公路网络所构成的图 G 是连通的。反设 G 不连通，那么可设 G由两个不相关的子图（没有任何边关联分别在两个
13、子图中的顶点）G1，G2组成，分别有 n1，n2个顶点，从而，n=n1+n2，n1 1，n2 1。由于各子图的边数不超过2)1(iinn (见练习之 3)，因此 G 的边数 m 满足：)1()1(21)1(2122111nnnnnnmkiii )1)(1()1)(1(2121nnnn )2)(1(21)2)(1(2121nnnnn 与已知2)2)(1(nnm矛盾，故图 G 是连通的。（本题是定理的特例，当然也可以应用这一定理和它的证明方法来解题。）*8、（1）证明：序列（7，6，5，4，3，3,2），（6，5，5，4，3，2，2）以及（6，6，5，4，3，3，1）都不是简单图的度序列。（2）若
14、自然数序列（d1,d2,dn）满足 d1d2dn，那么当它为一简单图的度序列时必有 （a）niid1为偶数；（b）对任一 k，1kn,kiid1 k(k-1)+nkiidk1),min(。证（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）也不是
15、简单图的度序列。证（2）niid1为偶数是显然的。考虑图中的 k 个顶点（k=1,2,n）,这 k 个顶点的生成子图的度数总和 k(k-1)，而其余 nk 个顶点 vk+1,vk+2,vn,可使 v1,v2,vk增加的度数不会超过 nkiidk1),min(因此我们有kiid1 k(k-1)+nkiidk1),min(。9、画出图中图的补图及它的一个生成子图。图 解 补图 生成子图 10、一个简单图，如果同构于它的补，则该图称为自补图。（1）给出一个 4 个顶点的自补图。（2）给出一个 5 个顶点的自补图。（3）是否有 3 个顶点或 6 个顶点的自补图（4）证明一个自补图一定有 4k 或 4k
16、1 个顶点（k 为正整数）。解（1）4 个顶点的自补图：（2）5 个顶点的自补图：（3）没有。（4）证 设 G 为自补图，有 n 个顶点。我们已知 n 个顶点的完全图有 2)1(nn条边，因此 G 应恰有4)1(nn条边。故或者 n 是 4 的整数倍，或者 n1是 4 的整数倍，即图 G 一定有 4k 或 4k1 个顶点（k 为正整数）。11、（l）证明图 中（a）与（b）同构。(a)(b)图（2）给出所有不同构的 4 个结点的简单图的图示。A?D C B?E F?G H?（l）证 在图（a）图（b）间建立双射 h v A B D I J C E G H F h(v)?可逐一验证(不赘)(u,
17、v)?E(a)当且仅当(h(u),h(v)?E(b)（2）所有不同构的 4 个结点的简单图的图示有如下 11 个：*12、Kn表示 n 个顶点的无向完全图。（l）对 K6的各边用红、蓝两色着色，每边仅着一种颜色，红、蓝任选。证明：无论怎样着色，图上总有一个红色边组成的 K3或一个蓝色边组成的K3。（2）用（l）证明下列事实：任意 6 个人之间或者有三个人相互认识，或者有 3 个人相互都不认识。证（l）考虑 K6的顶点 V，与之关联的边有 5 条，其中至少有 3 条着同一颜色。不妨设均着红色，这三边的另一个端点分别是 u1,u2,u3(如图所示)。再考虑关联 u1,u2,u3 的三条边。如果它们
18、中有一条着红色的边，那么我们就已经得到一个红色边组成的 K3，如果它们中没有着红色的边，那么我们就能够得到一个蓝色边组成的 K3。v u2 u1 证（2）用六个顶点表示 6 个人，顶点间红色边表示人员间相互认识，顶点间蓝色边表示人员间相互不认识，便产生一个边着红、蓝两色的完全图 K6。利用（1）的结论，可以断定 6 个人之间或者有三个人相互认识，或者有 3 个人相互都不认识。路径、回路及连通性 内容提要 8.2.1 路径与回路 定义 图 G 的顶点 v1到顶点 vl的拟路径（pseudo path）是指如下顶点与边的序列：v1,e1,v2,e2,v3,v l-1,el-1,vl 其中 v1,v
19、2,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 称为该拟路径的长度。当 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
20、 l-1,vl）代替式v1,e1,v2,e2,v3,v l-1,el-1,vl。定理 在有 n 个顶点的图 G 中，如果有从顶点 u 到 v（u?v）的拟路径，那么从 u 到 v 必有路径，并且必有长度不大于 n 1 的通路。定理 8.5 在具有 n 个顶点的图 G 中，如果有从 v 到 v 的闭路径，那么必定有一条从 v 到 v 的长度不大于 n 的回路。8.2.2 连通性 定义 称图中顶点 u 到 v 是可达的（accesible），如果 u=v，或者有一条 u 到 v 的路径。定义 称无向图 G 是连通的（connected），如果 G 的任何两个顶点都是相互可达的。称有向图 G 是强连
21、通的，如果 G 的任何两个顶点都是相互可达的;称有向图 G 是单向连通的，如果 G 的任何两个顶点中，至少从一个顶点到另一个顶点是可达的；称有向图 G 是弱连通的，如果 G 的有向边被看作无向边时是连通的。定义 图 G称为图 G 的连通分支（connected components），如果 G是 G 的子图，G是连通的，并且不存在 G 的真子图 G，使 G是连通的，且 G以 G为真子图。定义 设 G为有向图 G 的子图，若 G是强连通的（单向连通的、弱连通的），且 G 没有真子图 G使 G为其真子图，而 G强连通（单向连通、弱连通），那么称 G为 G 的一个强分图（单向分图、弱分图）。定理 8
22、.6 一个图 G 是不连通的，当且仅当 G 的顶点集 V 可以分成两个不交的非空子集 V1 和 V2，使得任何边都不以 V1 的一个顶点和 V2 一个顶点为其两端点。定理 如果图 G 恰有两个不同的奇数度的顶点 u，v，那么 u 到 v 必定是可达的。定理 若图 G 为具有 n 个顶点、k 个连通分支的简单图，那么 G 至多有2)1)(knkn条边。8.2.3 连通度 定义 设S为连通图G的顶点集V的子集，称S为G的点割集（cut-set of nodes）,如果从 G 中删除 S 中的所有顶点后得到的图不连通，但 S 的任何真子集均无这一特性。当点割集为单元素集合v时，v 称为割点（cut-
23、nodes）。定义 (G)称为 G 的点连通度（node-connectivity），定义如下：nnKGGSSKGnGG连通，若为点割集为若非连通图若:min10)(定义 设 S 为连通图 G 边集 E 的子集，称 S 为 G 的边割集（cut-set of edges），或割集，如果从 G 中删除 S 的所有边后所得的图是不连通的，但 S的任何真子集均无这一特性。当割集为单元素集e时，称 e 为割边（cut-edges）。定义 (G)称为图 G 的边连通度（edge-connectivity），定义如下：否则的割集为为一孤立结点时当非连通图时当:min00)(GSSGGG 定理 对任何简单无
24、向图 G，(G)(G)(G)定理 设 G 为 n 个顶点、m 条边的简单连通图，那么(G)nm2。习题解答 练习 1、证明定理。证 设 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,vi,vj+1,vk,v）仍然为从 v 到 v 的闭路径。如此不断删除闭路径内相同顶点构成的闭路径，最终必
25、可得到一条从 v到 v 的长度不大 于 n 的回路。2、证明：在简单无向图 G 中，从结点 u 到结点 v,如果既有奇数长度的通路又有偶数长 度的通路，那么 G 中必有一奇数长度的回路。证 设 G 中，从结点 u 到结点 v 的奇数长度的通路为 O，偶数长度的通路为 E。对 O 和 E 的除结点 u 和 v 的相交结点的数目归纳 k。k=0,那么 O 和 E 恰好构成 G 的奇数长度的回路。设奇数长度的通路与偶数长度的通路的相交结点的数目少于 k 时，命题成立。设图 G 中，从结点 u 到结点 v 的奇数长度的通路与偶数长度的通路有 k个相交结点，如图所示：考虑结点 u 到结点 k,如果从结点
26、 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）因此（
27、ui,vj）全部在 G中，从而 G是连通的。4、有向图可用于表示关系，图表示的二元关系是传递的吗说说如何由有向图判定关系的传递性。求图表示的二元关系的传递闭包，说说构作有向图传递闭包的方法。u 1 2 k v a a 图 解 图表示的二元关系不是传递的。有向图表示的关系是传递的，当且仅当对图中任意两个结点 u,v，如果有从 u 到 v 的路径，则必有从 u 到 v的边。图表示的二元关系的传递闭包如图（b）所示。构作有向图传递闭包的方法是：对图中任意两个结点 u,v，如果有从 u 到 v 的路径，则添加从 u到 v 的边。5、给出图中有向图的强分图，单向分图和弱分图，作出它的凝聚图。图 解 图中
28、有向图的强分图有：v1,v2,v3,v4,v5,v6,v7,v8,v9,v1 v2 v7 v10 v4 v3 v8 v9 图中有向图的单向分图有：v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,图的凝聚图：6、有 7 人 a，b，c，d，e，f，g 分别精通下列语言，问他们 7 人是否可以自由交谈（必要时借助他人作翻译）。a 精通英语。b 精通汉语和英语。c 精通英语、俄语和意大利语。d 精通日语和英语。e 精通德语和意大利语。f 精通法语、日语和俄语。g 精通法语和德语。解 下图中 7 个顶点表示 7 个人，关联两个顶点的边表示两个人同时精通某一种语言：v1,v2 v3,v4,
29、v5 v7,v8,v9 v10 a b d c 由于该图是连通的，因此他们 7 人是可以自由交谈（必要时借助他人作翻译）。7、证明：一个有向图是单向连通的，当且仅当它有一条经过每一结点的路径。证 充分性是显然的。必要性：设有向图 G 是单向连通的，P 是 G 中的一条路径，起点为 u1,终点为 uk。如下延长这一路径：考虑路径外的任意顶点 w,若（1）有顶点 w 到 u1的路径,则我们如愿。（2）有顶点 uk到 w 的路径,则我们如愿。否则，由于有向图是单向连通的，（3）有顶点 w 到 uk的路径,和顶点 uk-1到 w 的路径,则我们如愿。否则，由于有向图是单向连通的，（4）有顶点 w 到
30、uk的路径,和顶点 uk-2到 w 的路径,则我们如愿。否则，（5）如此等等，有顶点 w 到 uk的路径,和顶点 u1到 w 的路径,则我 uk-1 u u w w u1 uk-2 uk-1 uk 们如愿。如上不断延长这一路径，直至产生一条经过每一结点的路径。8、称 d(u,v)为图 G中结点 u，v 间的距离：否则间最短路径长度不可达到当当vuvuvuvud,0),(d 称为图 G 的直径，如果 dmaxd(u,v)?u,v?V。试求图中图的直径，(G),(G),(G)，并指出一个点割集和一个边割集。图 解 d3，(G)=3,(G)=3,(G)=3。9、顶点 v 是简单连通图 G 的割点，当
31、且仅当 G 中存在两个顶点 v1，v2，使 v1 到 v2 的通路都经过顶点 v。试证明之。证充分性是显然的。必要性：设顶点 v 是简单连通图 G 的割点，如果不存在两个顶点 v1，w u1 uk-2 uk-1 uk v2，使 v1 到 v2 的通路都经过顶点 v，那么对任意两个顶点 v1，v2，都有一条通路不经过顶点 v，因而删除顶点 v 不能使 G 不连通，与 v 是简单连通图 G 的割点矛盾。故 G 中必存在两个顶点 v1，v2，使 v1 到 v2 的通路都经过顶点 v。10、边 e 是简单连通图 G 的割边，当且仅当 e 不在 G 的任一回路上。试证明之。证 设 e 是简单连通图 G
32、的割边，其端点为 u,v。删除边 e 后，u,v 应在两个不同的连通分支中。若 e 在 G 的一条回路上，那么删除边 e 后，u,v应仍在一条通路上，矛盾。故 e 不在 G 的任一回路上。反之，设 e 不在 G 的任一回路上，而 e 不是简单连通图 G 的割边。那么G-e仍是连通的，故还有 u 到 v 的一条通路，从而这条通路连同边 e 构成G 中的一条回路，矛盾。因此边 e 是简单连通图 G 的割边 11、试用有向图描述下列问题的解：某人 m 带一条狗 d，一只猫 c 和一只兔子 r 过河。m 每次游过河时只能带一只动物，而没人管理时，狗与兔子不能共处，猫和兔子也不能共处。问 m 怎样把三个
33、动物带过河去（提示：用结点代表状态，状态用序偶来表示，这里 S1，S2分别是左岸和右岸的人及动物集合，例如初始状态为。解 描述上述问题的有向图如下：12、有向图可以刻划一个系统的状态转换，例如用图中的有向图可以描述识别 010?10 序列的状态转换系统。其中 S 为初始状态，在此读入序列，然后依序列中符号转入后续状态（读到 0 进入 S1，读到 1 进入 S2，如此等等）。S4 表示读完序列 010?10 应进入的最后状态，S5 表示读完一个非 010?10序列应进入的最后状态。试自行构作识别序列 01(10)?10 的有向图刻划的状态转换系统。（上文中 w?表示空字或重复任意多次 w 所得的
34、字。）图 解 识别序列 01(10)?10 的有向图刻划的状态转换系统如下：0 S 0 S1 1 S2 1 S3 0 S4 S3 0 1 S S1 S2 S4 S5 欧拉图与哈密顿图 内容提要 8.3.1 欧拉图与欧拉路径 定义 图 G 称为欧拉图（Euler graph），如果图 G 上有一条经过 G 的所有顶点、所有边的闭路径。图 G 称为欧拉路径（Euler walk），如果图 G上有一条经过 G 所有顶点、所有边的路径。定理 无向图 G 为欧拉图当且仅当 G 连通，并且所有顶点的度都是偶数。有向图 G 为欧拉图，当且仅当 G 是弱连通的，并且每个顶点的出度与入度相等。定理 如果 G 为
35、欧拉图，那么 G 可分成若干个（一个或几个）回路。定理 无向图 G 为欧拉路径(非欧拉图)，当且仅当 G 连通，并且恰有两个顶点的度是奇数。有向图 G 为欧拉路径(非欧拉图)，当且仅当 G 连通，并且恰有两个顶点的入度与出度不等，它们中一个的出度比入度多 1，另一个入度比出度多 l。8.3.2 哈密顿图及哈密顿通路 定义 无向图 G 称为哈密顿图（Hamilton graph），如果 G 上有一条经过所有顶点的回路（也称这一回路为哈密顿回路）。称无向图有哈密顿通路(非哈密顿图)，如果 G 上有一条经过所有顶点的通路(非回路)。定理 设图 G 为具有 n 个顶点的简单无向图，如果 G 的每一对顶
36、点的度数之和都不小于 n 1，那么 G 中有一条哈密顿通路；如果 G 的每一对顶点的度数之和不小于 n，且 n3，那么 G 为一哈密顿图。定理 当 n 为不小于 3 的奇数时，Kn上恰有21n条互相均无任何公共边的哈密顿回路。定义 图 G 称为可 2-着色（2-chromatic），如果可用两种颜色给 G 的所有顶点着色，使每个顶点着一种颜色，而同一边的两个不同端点必须着不同颜色。定理 设图 G 是可 2-着色的。如果 G 是哈密顿图，那么着两种颜色的顶点数目相等；如果 G 有哈密顿通路，那么着两种颜色的顶点数目之差至多为一。习题解答 练习 8.3 1、试作出四个图的图示，使第一个既为欧拉图又
37、为哈密顿图；第二个是欧拉图而非哈密顿图；第三个是哈密顿图却非欧拉图；第四个既非欧拉图也非哈密顿图。解（a）既为欧拉图又为哈密顿图；（b）是欧拉图而非哈密顿图；（c）是哈密顿图却非欧拉图；（d）既非欧拉图也非哈密顿图。2、像第一题要求的那样对欧拉路径和哈密顿通路作出四个图。解（a）既有欧拉路径又有哈密顿通路；（b）有欧拉路径而无哈密顿通路；（c）有哈密顿通路却无欧拉路径；（d）既无欧拉路径也无哈密顿通路。（a）(b)(c)（a）(b)(c)3、问 n 为何种数值时，Kn既是欧拉图又是哈密顿图。问 k 为何值时，k-正则图既是欧拉图又是哈密顿图。解 n 为奇数时，Kn既是欧拉图又是哈密顿图。k 为
38、大于或等于 n/2 的偶数时，k-正则图既是欧拉图又是哈密顿图。4、证明：恰有两个奇数度顶点 u,v 的无向图 G 是连通的,当且仅当在 G上添加边（u，v）后所得的图 G*是连通的。证 必要性是显然的。设 G*是恰有两个奇数度顶点 u,v 的无向图 G 添加边（u，v）后所得，且是连通的,那么图 G*是一个欧拉图（每一个顶点都是偶数度的连通图），因此 G*中删除边（u，v）后所得的图 G 仍是连通的。5、参阅练习第 2 题。问马可否从某处出发完成所有可能的跳步一次且仅一次后回到原地。解 练习第 2 题中的图不是欧拉图(它有三个 3 度的顶点)，因此马不可能从某处出发完成所有可能的跳步一次且仅
39、一次后回到原地。6、参阅练习第 2 题。问马可否从某处出发跳遍棋盘的所有方格一次且仅一次后回到原地。解 马可以从某处出发跳遍棋盘的所有方格一次且仅一次后回到原地。具体跳步如下图所示:幻方中数字 n 表示第 n 个跳步的起点。下图则表示跳步的图示。50 11 24 63 14 37 26 35 23 62 51 12 25 34 15 38 10 49 64 21 40 13 36 27 61 22 9 52 33 28 39 16 48 7 60 1 20 41 54 29 59 4 45 8 53 32 17 42 6 47 2 57 44 19 30 55 3 58 5 46 31 56
40、43 18 幻方 7、试计算 Kn（n3）中不同的哈密顿回路共有多少条。解 不同的哈密顿回路共有2)!1(n条。可以用依次选取每一条边来生成哈密顿回路。因为组成回路的第一条边的选择可能是 n 种,组成回路的第二条边的选择可能是 n 1 种,组成回路的第 n 1 条边的选择可能是 2 种，组成回路的第 n 条边的选择可能是 1 种，而每一哈密顿回路由此生成两次，因此不同的哈密顿回路共有2)!1(n条。8、十一个学生在一张圆桌旁共进晚餐，要求在每次晚餐上每个学生的邻座都与其它各次晚餐的邻座不同。问这样共进晚餐能安排多少次。解 每次晚餐上每个学生的邻座都与其它各次晚餐的邻座不同的安排方式有21n种（
41、根据定理。）9、判别图中各图是否为哈密顿图，若不是，请说明理由，并回答它是否有哈密顿通路。图 解（a），(b)是为哈密顿图。(c)不是哈密顿图，也没有哈密顿通路。在图(c)中增加顶点 k，并对其顶点做二着色，构成图(d)（如下）。图(d)不是哈密顿图，也没有哈密顿通路。因为图中白色顶点比黑色顶点多两个。故(c)不是哈密顿图，也没有哈密顿通路。否则它的哈密顿回路或哈密顿通路必定经过顶点 k（k 在两个二度顶点之间的边上），从而图(d)也是哈密顿图，也有哈密顿通路，矛盾。（a）(b)(c)k 10、证明：对哈密顿图 G=删除 S（?V）中的所有顶点后，所得图 G的连通分支数不大于?S?。证 设 G
42、1 是 G 中的哈密顿回路，显然在 G1 中删除 S（?V）中的所有顶点后，所得图 G1的连通分支数 k1，不小于在 G 中删除 S（?V）中的所有顶点后，所得图 G的连通分支数 k，即 kk1。由于 G1 是一条回路，在 G1 中删除 S（?V）中的所有顶点后，所得图 G1的连通分支数 k1 不大于?S?是显然的，即 k1?S?。因此 kk1?S?11、设 G 为（n，m）图。证明：如果221nCm，那么 G 为哈密顿图（提示：运用定理）。证 设 G 中有两个顶点 v1 和 v2 的度数之和不大于 n 1 ，那么以 v1和 v2 为端点的边不多于 n 1 条。而其余顶点之间的边的数目不多于2
43、)3)(2(nn条。故G 的总边数 m 满足 11)2)(1(21)43(21)6522(21)3)(2(2112122nCnnnnnnnnnnm 与221nCm矛盾，故 G 中任意两个顶点的度数之和大于 n。根据定理，G为哈密顿图。12、设有 n 个围成一圈跳舞的孩子，每个孩子都至少与其中2n个是朋友。试证明，总 可安排得使每个孩子的两边都是他的朋友。证 设 n 个孩子为 n 个顶点，用边表示顶点间的朋友关系构成一个图 G。由于每个孩子都至少与其中2n个是朋友，因此 G 的每一顶点的度数至少是2n，从而 G 的任何两个顶点的度数之和至少是n。根据定理，G 为哈密顿图。即 G 有哈密顿回路，这
44、表明，总可安排 n 个孩子围成一圈跳舞，使每个孩子的两边都是他的朋 图的矩阵表示 内容提要 8.4.1 关联矩阵 定义 设 G 为（n，m）图，那么 n?m 矩阵 A=aij，否则为端点以顶点当边01ijijvea 称为 G 的关联矩阵（incidence matrix），记为 A(G)。定理 若 G 为（n，m）连通简单图。那么 A 的秩为 n l（即其最大非零行列式的阶数为 n l）。8.4.2 邻接矩阵 定义 设 G=为一无重边的有向图。其中 V=v1,v2,vn，那么 n?n 矩阵 A=aij，),(,0),(,1EvvEvvEvvEvvajijijijiij或当或当 称为图 G 的邻
45、接矩阵（adjacency matrix），记为 AG 用 Al表示l个矩阵 A 的乘积。（1）令 Al=)(lija，那么)(lija的意义是：G 中从顶点 vi到 vj的长度为l的拟路径恰为)(lija条。（2）令 AA=ijb，那么ijb的意义是：有ijb个顶点 v，使得 vi到 v，vj到 v 都有边（两边交于 v）。因而iib表示顶点 vi的出度。（3）令 A A=ijb，那么ijb的意义是：有ijb个顶点 v，使得 v 到vi,v 到 vj都有边；因而iib表示顶点 vi的入度。8.4.3 路径矩阵与可达性矩阵 设 n 个顶点的图 G 的邻接矩阵为 A，及表示如下定义的矩阵运算.若
46、 Aija，C=ijc，则 AC=ijd ijd=ijaijc AC=ije ije=)(1kjiknkca 这里nk 1为连续求运算的缩记符,以下nk 1同此.我们用 A(m)表示 AAA(m 个 A)。考虑矩阵 BAA(2)A(n)它的第 i，j 分量 bij=1 当且仅当图 G 中有 vi到 vj的路径。B 称为图 G 的路径矩阵（walk matrix）。令矩阵 PIB，其中 I 为（n?n）么矩阵，称 P 为图 G 的可达性矩阵。习题解答 练习 1、对图给出的无向图 G:（1）计算其关联矩阵 A(G)。（2）计算 A(G)的秩，验证定理。解（1）其关联矩阵 A(G)为10001000
47、011000110101543214321vvvvveeee（2）由于子行列式100011001非零，因此，A(G)的秩为 3=n k=5 2。2、对图给出的有向图 G:v1 e1 v4 e3 e4 v1 v2 v3 v v （1）计算它的邻接矩阵 A 及 A2，A3，A4，说出从 v1到 v4的长度为 l，2，3，4 的拟路径各有多少条。（2）计算 AA，A A，说出它们中第 2，3 分量及第 4，4 分量的意义。（3）计算它的路径矩阵 B 及可达性矩阵 P，并从 P 说出 G 的各强分图。解(1)它的邻接矩阵 A=0101010000000000110001010 v1到 v4的长度为 1
48、 的拟路径各有 1 条。A2=1110001010000001000011100 v1到 v4的长度为 2 的拟路径各有 1 条。A3=1101011100000000101011010 v1到 v4的长度为 3 的拟路径各有 1 条。A4=1211011010000001110012110 v1到 v4的长度为 4 的拟路径各有 2 条。(2)AA=01010100000000001100010100100010011000101000100000=2101201000000001002120012 A A=010001001100010100010000001010100000000001
49、10001010=1000003120011000202000000 AA中第 2，3 分量为 0，表明没有两条边以 v2，v3为起点而终止于同一终点；第 4，4 分量为 1,是 v4的出度。AA 中第 2，3 分量为 0，表明没有两条边起始于同一顶点而以 v2，v3为终点；第 4，4 分量为 3,是 v4的入度。（3）它的路径矩阵 B=1111011110000001111011110 可达性矩阵 P=1111011110001001111011111 由 P 看出各强分图的顶点集合分别是v1，v3，v2，v4，v5 3、如何利用邻接矩阵来识别它们对应的无向图是欧拉图 解 利用邻接矩阵判断各
50、顶点的度数是否为偶数。同时，利用邻接矩阵求出路径矩阵，用各矩阵分量是否均为 1 来判断无向图是否连通。4、n 个顶点的有向图 G 是强连通的，说出 G 的路径矩阵、可达性矩阵的特点。解 G 的路径矩阵与可达性矩阵相同，它们的所有分量均为 1。5、设 A 为不含环和平行边的有向图 G 的邻接矩阵。证明：A3的对角线元素)3(iia表示经过顶点 vi的“三角形”的个数，即以 vi为一个顶点的 G 的子图 K3的个数。证 因为 A3的对角线元素)3(iia，表示顶点 vi到顶点 vi长度为 3 的拟路径的条数，并且有向图 G 不含环和平行边，因此)3(iia也是经过顶点 vi的“三角形”的个数，即以