离散数学王元元习题解答 (9)

1第三篇图论第八章图8.1图的基本知识内容提要8.1.1图的定义及有关术语定义8.1图（graph）G由三个部分所组成：（1）非空集合V(G)，称为图G的结点集，其成员称为结点或顶点（nodesorvertices）。（2）集合E(G)，称为图G的边集，其成员称为边(edges)。I（3）函数ΨG：E(G)→(V(G)，V(G))，称为边与顶点的关联映射（associatvemapping）。这里（V(G)，V(G)）称为VG的偶对集，其成员偶对（pair）形如（u，v），u，v为结点，它们未必不同。ΨG(e)=(u,v)时称边e关联端点u，v。当(u,v)用作序偶时(V(G)，V(G))=V(G)V(G)，e称为有向边，e以u为起点,以v为终点,图G称为有向图（directedgraph）；当(u,v)用作无序偶对时，(u,v)=(v,u)，称e为无向边（或边），图G称为无向图（或图）。图G常用三元序组V(G)，E(G)，ΨG,或V，E，Ψ来表示。显然，图是一种数学结构，由两个集合及其间的一个映射所组成。定义8.2设图G为V，E，Ψ。（l）当V和E为有限集时，称G为有限图，否则称G为无限图。本书只讨论有限图。（2）当ΨG为单射时，称G为单图；当ΨG为非单射时，称G为重图，又称满足Ψ(e1)=Ψ(e2)的不同边e1,e2,为重边,或平行边。（3）当Ψ(e)＝(v,v)（或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）时，也用(u,v)(或u,v)表示边e，这时称u，v邻接e,u,v是e的端点（或称u为e的起点，v为e的终点）;也称e关联结点u,v。不是任何边的端点的结点都称为孤立结点，仅由孤立结点构成的图（E=）称为零图。（6）当给G赋予映射f：V→W，或g：E→W，W为任意集合，常用实数集及其子集,此时称G为赋权图，常用V,E,Ψ,f或V,E,Ψ,g或V,E,Ψ,f,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}，那么niimvd12)(定理8.2图的奇数度顶点必为偶数个。2定理8.3自然数序列（a1,a2,…,an）称为一个度序列，如果它是一个图的顶点的度的序列。（a1,a2,…,an）为一度序列，当且仅当niia1为一偶数。定义8.4一度的顶点称为悬挂点（pendantnodes）。定义8.6各顶点的度均相同的图称为正则图（regulargraph）。各顶点度均为k的正则图称为k-正则图。8.1.3图运算及图同构由于图由结点集、边集及关联映射组成，因此对图可作种种与集合运算相类似的运算。定义8.6设图G1＝V1，E1，Ψ1，G2＝V2，E2，Ψ2，称G1为G2的子图（subgraph），如果V1V2，E1E2，Ψ1Ψ2。称G1为G2的真子图，如果G1是G2的子图，且G1G2。称G1为G2的生成子图（spanningsubgraph），如果G1是G2的子图，且V1=V2。定义8.7设图G1＝V1，E1，Ψ1，G2＝V2，E2，Ψ2，且Ψ1与Ψ2是相容的，即对任一x，若Ψ1(x)=y1,Ψ2(x)=y2，则y1=y2，从而Ψ1Ψ2为一函数。（1）G1与G2的并，记为G1G2＝G3＝V3，E3，Ψ3，其中V3=V1V2，E3=E1E2，Ψ3=Ψ1Ψ2。（2）G1与G2的交,记为G1G2=G3=V3，E3，Ψ3，其中V3=V1V2，E3=E1E2，Ψ3=Ψ1Ψ2。（3）若G1为G2的子图，则可定义G2对G1的差，记为G2－G1＝G3＝V3，E3，Ψ3，其中E3=E2–E1，V3＝V2，Ψ3=Ψ2E3。（4）G1与G2的环和，记为G1G2，G1G2＝(G1G2)－(G1G2)（5）若G为简单图，则可定义G的补，记为G¯，若V(G)=n，则G¯=Kn－G定义8.8设图G＝V，E，Ψ（1）G－e表示对G作删除边e的运算，G－e=V，E’，Ψ’，其中E’＝E－{e}，Ψ’=ΨE’。（2）G－v表示对G作删除顶点v的运算，G－v=V’，E’，Ψ’，其中V’=V－{v}，E’＝E－{ee以v为端点}，Ψ’＝ΨE’。（3）边e切割运算。设G中Ψ(e)=(u,v),对G作边e切割得G’＝V’，E’，Ψ’，其中，V’＝V{v’}，E’=(E－{e}){e1,e2},Ψ’=(Ψ－{e,(u,v)}){e1,(u,v’)，e2,(v’,v)}（4）顶点v贯通运算。设G中顶点v恰为边e1,e2的端点，且Ψ(e1)=(u,v)，Ψ(e2)=(w,v)。对G作顶点v贯通得G’＝V’，E’，Ψ’，其中V’=V－{v},E’=(E－{e1,e2}){e},Ψ’=(Ψ－{e1,(u,v),e2,(w,v)}){e,(u,w)}。切割与贯通是互逆的，两者常被称为同胚运算。定义8.9设G1＝V1，E1，Ψ1，G2＝V2，E2，Ψ2为两个图，称G1与G2同构（isomorphic），如果存在双射f：V1→V2，双射g：E1→E2，使得对每一边eE1，Ψ1(e)＝(u,v)（或u,v）当且仅当Ψ2(g(e))=(f(u),f(v))（或f(u),f(v)）当限于讨论简单图时，可以用顶点的偶对表示边，即当Ψ(e)＝(u,v)时，边e用(u,v)来表示。这时两图同构的条件可以简化为(u,v)E1当且仅当(f(u),f(v))E2习题解答3练习8.11、想一想，一只昆虫是否可能从立方体的一个顶点出发，沿着棱爬行、它爬行过每条梭一次且仅一次，并且最终回到原地？为什么？解不可能。可将立方体的一个顶点看作图的一个顶点，把立方体的棱看作图的边，那么该图的四个顶点都是三度的，因此不可能从一个顶点出发，遍历所有的边一次且仅一次，并且最终回到原顶点。2、请设想一张图，它的64个顶点表示国际象棋棋盘的64个方格，顶点间的边表示:在这两个顶点表示的方格之间可以进行“马步”的行走。试指出其顶点有哪几类（依其度分类），每类各有多少个顶点。解其顶点有5类：二度顶点合计4个,三度顶点合计8个,四度顶点,合计20个,六度顶点,合计16个顶点,八度顶点,合计16个顶点。23444432346666434688886446888864468888644688886434666643234444323、（l）证明：n个顶点的简单图中不会有多于2)1(nn条边。（2）n个顶点的有向完全图中恰有2n条边。证（l）n个顶点的简单完全图的边数总和为2)1(12)2()1(nnnn（2）n个顶点的有向完全图的边数总和为2nnnnnnn4、证明:在任何n(n≥2)个顶点的简单图G中，至少有两个顶点具有相同的度。证如果G有两个孤立顶点，那么它们便是具有相同的度的两个顶点。如果G恰有一个孤立顶点，那么我们可对有n–1个顶点但没有孤立顶点的G’（它由G删除孤立顶点后得到）作下列讨论。不妨设G没有孤立顶点，那么G的n个顶点的度数应是：1，2，3，…，n–1这n–1种可能之一，因此必定有两个顶点具有相同的度。5、图8.10是一个迷宫,其中数字表示通道、和死胡同(包括目标)。请用一个图来表示这个迷宫(用结点表示通道、和死胡同(包括目标)),用边表示它们之间的可直接到达关系。4图8.10解6、在晚会上有n个人，他们各自与自己相识的人握一次手。已知每人与别人握手的次数都是奇数，问n是奇数还是偶数。为什么？解n是偶数。用n个顶点表示n个人，顶点间的一条边表示一次握手，可构成一个无向图。若n是奇数，那么该图的顶点度数之和为奇数（奇数个奇数的和），这是不可能的，因此n是偶数。7、n个城市间有m条相互连接的直达公路。证明：当2)2)(1(nnm时，人们便能通过这些公路在任何两个城市间旅行。证用n个顶点表示n个城市，顶点间的边表示直达公路，据题意需证这n个城市的公路网络所构成的图G是连通的。反设G不连通，那么可设G由两个不相关的子图（没有任何边关联分别在两个子图中的顶点）G1，G2组成，分别有n1，n2个顶点，从而，n=n1+n2，n1≥1，n2≥1。由于各子图的边数不超过2)1(iinn(见练习8.l之3)，因此G的边数m满足：))1()1((21)1(2122111nnnnnnmkiii211831745202116156192214713891011125))1)(1()1)(1((2121nnnn)2)(1(21)2)(1(2121nnnnn与已知2)2)(1(nnm矛盾，故图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）满足d1d2…dn，那么当它为一简单图的度序列时必有（a）niid1为偶数；（b）对任一k，1≤k≤n,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）也不是简单图的度序列。证（2）niid1为偶数是显然的。考虑图中的k个顶点（k=1,2,…,n）,这k个顶点的生成子图的度数总和≤k(k-1)，而其余n–k个顶点vk+1,vk+2,…,vn,可使v1,v2,…,vk增加的度数不会超过nkiidk1),min(因此我们有kiid1≤k(k-1)+nkiidk1),min(。9、画出图8.11中图的补图及它的一个生成子图。6图8.11解补图生成子图10、一个简单图，如果同构于它的补，则该图称为自补图。（1）给出一个4个顶点的自补图。（2）给出一个5个顶点的自补图。（3）是否有3个顶点或6个顶点的自补图？（4）证明一个自补图一定有4k或4k＋1个顶点（k为正整数）。解（1）4个顶点的自补图：（2）5个顶点的自补图：（3）没有。（4）证设G为自补图，有n个顶点。我们已知n个顶点的完全图有2)1(nn条边，因此G应恰有4)1(nn条边。故或者n是4的整数倍，或者n–1是4的整数倍，即图G一定有4k或4k＋1个顶点（k为正整数）。11、（l）证明图8.12中（a）与（b）同构。(a)(b)图8.12（2）给出所有不同构的4个结点的简单图的图示。（l）证在图（a）图（b）间建立双射hvABDIJCEGHFh(v)ADCBEFGHIJ7可逐一验证(不赘)(u,v)E(a)当且仅当(h(u),h(v))E(b)（2）所有不同构的4个结点的简单图的图示有如下11个：*12、Kn表示n个顶点的无向完