离散数学王元元习题解答

第三篇图论第八章图图的基本知识内容提要图的定义及有关术语定义图(graph)G由三个部分所组成：非空集合V(G)，称为图G的结点集，其成员称为结点或顶点(nodesorvertices)。集合E(G)，称为图G的边集，其成员称为边(edges)。I函数屮:E(G)f(V(G),V(G)),称为边与顶点的关联映射(associatveGmapping)。这里(V(G),V(G))称为VG的偶对集，其成员偶对(pair)形如(u,v),u，v为结点，它们未必不同。屮(e)=(u,v)时称边e关联端点u，v。G当(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),W＞,或〈V,E,W＞来表示。显然，G图是一种数学结构，由两个集合及其间的一个映射所组成。定义8・2设图G%〈V,E,屮〉。当V和E为有限集时，称G为有限图，否则称G为无限图。本书只讨论有限图。当屮为单射时，称G为单图；当屮为非单射时，称G为重图，GG又称满足屮(el)=屮(e2)的不同边el,e2,为重边，或平行边。当屮(e)=(v,v)(或〈v,v>)时，称e为环(loops)。无环和重边的无向单图称为简单图。当G为有限简单图时，也常用(n,m)表示图G,其中n二??,m=?E?o屮为双射的有向图称为有向完全图；对每一(u,v),u?v,均有e使W(e)=(u,v)的简单图称为无向完全图，简称完全图，n个顶点的完全图常记作Kon在单图G中，屮(e)=(u,v)(或<u,v>)时，也用(u,v)(或〈u,v>)表示边e,这时称u,v邻接e,u,v是e的端点(或称u为e的起点，v为e的终点)；也称e关联结点u,vo不是任何边的端点的结点都称为孤立结点，仅由孤立结点构成的图(E=?)称为零图。当给G赋予映射f：V-W,或g：E-W,W为任意集合，常用实数集及其子集,此时称G为赋权图，常用<V,E,W,f>或〈V,E,W,g>或〈V,E,W,f,g>表示之。f(v)称为结点v的权，g(e)称为边e的权。结点的度定义在无向图中，结点v的度(degree)d(v)是v作为边的端点的数目。在有向图中，结点的度d(v)是v的出度d+(v)(out-degree)与入度d-(v)(in-degree)的和；v的出度是v作为有向边起点的数目，v的入度是v作为有向边终点的数目。定理对任意图G,设其边数为m,顶点集为{v,v,…，v},那么l2n工d(v)二2mii=1定理图的奇数度顶点必为偶数个。定理自然数序列(a,a,…,a)称为一个度序列，如果它是一个图的12n顶点的度的序列。(a,a,…,a)为一度序列，当且仅当工a为一偶数。12nii=1定义一度的顶点称为悬挂点(pendantnodes)。定义各顶点的度均相同的图称为正则图(regulargraph)。各顶点度均为k的正则图称为k-正则图。图运算及图同构由于图由结点集、边集及关联映射组成，因此对图可作种种与集合运算相类似的运算。定义设图G1=〈V1,El,屮1>,G2=<V2,E2,屮2>，称G1为G2的子图(subgraph),如果V1?V2,E1?E2,W1?屮2。称G1为G2的真子图，如果G1是G2的子图，且G1?G2。称G1为G2的生成子图(spanningsubgraph),如果G1是G2的子图，且V1=V2。定义设图G1=<V1,E1,W1>,G2=<V2,E2,W2>，且屮1与屮2是相容的，即对任一x,若屮1(x)=y1,屮2(x)=y2,则y1二y2，从而W1?W2为一函数。G1与G2的并，记为G1?G2=G3=<V3,E3,屮3>,其中V3=V1?V2,E3=E1?E2,W3=W1?W2OG1与G2的交，记为G1?G2=G3=<V3,E3,屮3>,其中V3二V1?V2,E3=E1?E2,W3=屮1?屮2。若G1为G2的子图，则可定义G2对G1的差，记为G2—G1=G3=<V3,E3,W3>，其中E3=E2-E1,V3=V2,W3=屮2?。E3G1与G2的环和，记为G1?G2,G1?G2=(G1?G2)—(G1?G2)若G为简单图，贝何定义G的补，记为G_,若?V(G)?=n,则G一二K—Gn定义设图G=<V,E,W>G—e表示对G作删除边e的运算，G—e=<V,E',W>，其中E'=E—{e},屮'二屮？。E'G—v表示对G作删除顶点v的运算，G—v=<V',E',W>,其中V'二V—{v},E'=E—{e?e以v为端点},W'=W?oE'边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)>}顶点v贯通运算。设G中顶点v恰为边e1,e2的端点，且屮(e1)=(u,v),W(e2)=(w,v)。对G作顶点v贯通得G'=<V',E',W>,其中V'=V—{v},E'=(E—{e1,e2})?{e},屮'=(屮一{<e1,(u,v)>,<e2,(w,v)>})?{<e,(u,w)>}o切割与贯通是互逆的，两者常被称为同胚运算。定义设G1=<V1,E1,W1>,G2=<V2,E2,W2>为两个图，称G1与G2同构(isomorphic),如果存在双射f：V1-V2，双射g：E1-E2，使得对每一边e?E1,屮l(e)=(u,v)(或〈u,v>)当且仅当屮2(g(e))=(f(u),f(v))(或<f(u),f(v)>)当限于讨论简单图时，可以用顶点的偶对表示边，即当屮(e)=(u,v)时，边e用(u,v)来表示。这时两图同构的条件可以简化为(u,v)?El当且仅当(f(u),f(v))?E2习题解答练习1、想一想，一只昆虫是否可能从立方体的一个顶点出发，沿着棱爬行、它爬行过每条梭一次且仅一次，并且最终回到原地为什么解不可能。可将立方体的一个顶点看作图的一个顶点，把立方体的棱看作图的边，那么该图的四个顶点都是三度的，因此不可能从一个顶点出发，遍历所有的边一次且仅一次，并且最终回到原顶点。2、请设想一张图，它的64个顶点表示国际象棋棋盘的64个方格，顶点间的边表示:在这两个顶点表示的方格之间可以进行“马步”的行走。试指出其顶点有哪几类(依其度分类)，每类各有多少个顶点。解其顶点有5类：二度顶点合计4个,三度顶点合计8个,四度顶点,合计20个,六度顶点,合计16个顶点,八度顶点,合计16个顶点。23444432346666434688886446888864468888644688886434666643234444323、（l）证明：n个顶点的简单图中不会有多于n（n—1）条边。2（2）n个顶点的有向完全图中恰有n2条边。证（l）n个顶点的简单完全图的边数总和为（n-1）+（n-2）+…+2+1=n（n-1）（2）n个顶点的有向完全图的边数总和为n+nHFn+n=nxn=n24、证明：在任何n（n#2）个顶点的简单图G中，至少有两个顶点具有相同的度。证如果G有两个孤立顶点，那么它们便是具有相同的度的两个顶点。如果G恰有一个孤立顶点，那么我们可对有n-1个顶点但没有孤立顶点的G'（它由G删除孤立顶点后得到）作下列讨论。不妨设G没有孤立顶点，那么G的n个顶点的度数应是：1,2,3,…,n-1这n-1无种可能之一，因此必定有两个顶点具有相同的度。5、图是一个迷宫,其中数字表示通道、和死胡同（包括目标）。请用一个图来表示这个迷宫（用结点表示通道、和死胡同（包括目标））,用边表示它们之间的可直接到达关系。22图16图166、在晚会上有n个人，他们各自与自己相识的人握一次手。已知每人与别人握手的次数都是奇数，问n是奇数还是偶数。为什么解n是偶数。用n个顶点表示n个人，顶点间的一条边表示一次握手,可构成一个无向图。若n是奇数，那么该图的顶点度数之和为奇数（奇数个奇数的和），这是不可能的，因此n是偶数。7、n个城市间有m条相互连接的直达公路。证明：当m>（“—1）（"—2）时,人们便能通过这些公路在任何两个城市间旅行。证用n个顶点表示n个城市，顶点间的边表示直达公路，据题意需证这n个城市的公路网络所构成的图G是连通的。反设G不连通，那么可设G由两个不相关的子图（没有任何边关联分别在两个子图中的顶点）Gl,G2组成，分别有n,n个顶点，从而，n二n+n,n21,n21。l2l2l2由于各子图的边数不超过n（"厂°（见练习之3），因此G的边数m满2足：mn(n-1)二(n(n-1)+n(n-1))2ii21122i=1=-((n-1)(n-1)+(n-1)(n-1))212=丄(n-1)(n+n-2)212=2(n-1)(n-2)与已知m〉(n-1)(n-2)矛盾，故图G是连通的。2(本题是定理的特例，当然也可以应用这一定理和它的证明方法来解题。）*8、（1）证明：序列（7，6，5，4，3，3,2），（6，5，5，4，3，2，2）以及（6，6，5，4，3，3，1）都不是简单图的度序列。（2）若自然数序列（d,d,…，d）满足d>d>・・・>d，那么当它为一简12n12n单图的度序列时必有工d为偶数；ii=1对任一k，lWkWn,工dWk(k-1)+min(k,d)。iii=1i=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)Yd为偶数是显然的。ii=1考虑图中的k个顶点(k=l,2,…,n)，这k个顶点的生成子图的度数总和Wk(k-l)，而其余n-k个顶点v,v,…,v,可使v,v,…，v增k+lk+2nl2k加的度数不会超过Ymin(k,d)ii=k+1因此我们有工dWk(k-l)+工min(k,d)。iii=1i=k+19、画出图中图的补图及它的一个生成子图。补图生成子图补图10、一个简单图，如果同构于它的补，则该图称为自补图。（1）给出一个4个顶点的自补图。（2）给出一个5个顶点的自补图。（3）是否有3个顶点或6个顶点的自补图（4）证明一个自补图一定有4k或4k+1个顶点（k为正整数）。解（1）4个顶点的自补图：2）5个顶点的自补图：解（1）4个顶点的自补图：2）5个顶点的自补图：（3）没有。（4）证设G为自补图，有n个顶点。我们已知n个顶点的完全图有

nn—1）条边，因此G应恰有呦—1）条边。故或者n是4的整数倍，或者n-124是4的整数倍，即图G—定有4k或4k+1个顶点（k为正整数）。11、（1）证明图中（a）与（b）同构。B图B图2）给出所有不同构的4个结点的简单图的图示。（l）证在图（a）图（b）间建立双射hvABDIJCEGHFh(v)??????????可逐一验证（不赘）（u,v）?E（a）当且仅当（h（u）,h（v））?E（b）（2）所有不同构的4个结点的简单图的图示有如下11个*12、K表示n个顶点的无向完全图。n（1）对K的各边用红、蓝两色着色，每边仅着一种颜色，红、蓝任选。6证明：无论怎样着色，图上总有一个红色边组成的K或一个蓝色边组成的3K。3（2）用（l）证明下列事实：任意6个人之间或者有三个人相互认识，或者有3个人相互都不认识。证（l）考虑K的顶点V,与之关联的边有5条，其中至少有3条着同6一颜色。不妨设均着红色，这三边的另一个端点分别是u1,u2,u3（如图所

示）。再考虑关联u1,u2,u3的三条边。如果它们中有一条着红色的边，那

么我们就已经得到一个红色边组成的K,如果它们中没有着红色的边，那3么我们就能够得到一个蓝色边组成的K。3u2u1u2u1证（2）用六个顶点表示6个人，顶点间红色边表示人员间相互认识，顶点间蓝色边表示人员间相互不认识，便产生一个边着红、蓝两色的完全图K。利用（1）的结论，可以断定6个人之间或者有三个人相互认识，或6者有3个人相互都不认识。路径、回路及连通性内容提要路径与回路定义图G的顶点v到顶点v的拟路径（pseudopath）是指如下顶点1l与边的序列：l-1el-1l-1el-111223其中v,v,v,…，v,v为G的顶点e,e,…，e为G的边，且e(i=123l-1l12l-1i1,2,…，l-1）以v及v为端点，（对有向图G，e以v为起点，以vii+1iii+1为终点）,拟路径的边数1—1称为该拟路径的长度。当e（i=1,2,…，1-1）i各不相同时，该拟路径称为路径（walk）,又当v（i=1,2,…，1）各不相i同时（除v与v），则称此路径为通路（Path）。v=v的路径称为闭路径1111（closedwalk）；v=v的通路称为回路（circuit）。11当讨论限于简单图或无平行边的有向图时，上述拟路径、路径、通路等可用顶点序列来表示，例如用（「笃，.…U）代替式v1'e1'v2，e2，v3，・・・」1-1，「1，人。定理在有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是强连通的，如果G的任何两个顶点都是相互可达的;称有向图G是单向连通的，如果G的任何两个顶点中，至少从一个顶点到另一个顶点是可达的；称有向图G是弱连通的，如果G的有向边被看作无向边时是连通的。定义图G'称为图G的连通分支(connectedcomponents),如果G'是G的子图，G'是连通的，并且不存在G的真子图G''，使G''是连通的，且G''以G'为真子图。定义设G'为有向图G的子图，若G'是强连通的(单向连通的、弱连通的)，且G没有真子图G''使G'为其真子图，而G''强连通(单向连通、弱连通)，那么称G'为G的一个强分图(单向分图、弱分图)。定理8・6一个图G是不连通的，当且仅当G的顶点集V可以分成两个不交的非空子集V1和V2,使得任何边都不以V1的一个顶点和V2一个顶点为其两端点。定理如果图G恰有两个不同的奇数度的顶点u，v，那么u到v必定是可达的。定理若图G为具有n个顶点、k个连通分支的简单图，那么G至多有(n-k)(n-k+1)条边。2八°A8・2・3连通度定义设S为连通图G的顶点集V的子集，称S为G的点割集(cut-setofnodes)，如果从G中删除S中的所有顶点后得到的图不连通，但S的任何真子集均无这一特性。当点割集为单元素集合｛v｝时，v称为割点(cut-nodes)。定义x(G)称为G的点连通度(node-connectivity)，定义如下：0若G非连通图X(G)=\n-1若G为Knmin｛|S|:S为点割集｝若G连通，G丰Kn定义设S为连通图G边集E的子集，称S为G的边割集(cut-setofedges)，或割集，如果从G中删除S的所有边后所得的图是不连通的，但S的任何真子集均无这一特性。当割集为单元素集｛e｝时，称e为割边(cut-edges)。定义入(G)称为图G的边连通度(edge-connectivity)，定义如下：0当G非连通图时九(G)=<0当G为一孤立结点时min｛|S|:S为G的割集｝否则定理对任何简单无向图G,x(G)W入(G)S(G)定理设G为n个顶点、m条边的简单连通图，那么入(G)W如。n习题解答练习1、证明定理。证设n个顶点的图G中，有从v到v的闭路径，表示为（v,v,v,…，V,v）12k如果v,v,v,…,v中没有相同顶点（因而不多于n个），那么它便是一条12k从v到v的长度不大于n的回路。如果v,v,v,v中有相同顶点v二v，12kij例如（v,v,…，v,…，v,v，…，v,v）1ijj+1k那么删除v到v的闭路径，得到ij（v,v,…，v,v,…，v,v）1ij+1k仍然为从v到v的闭路径。如此不断删除闭路径内相同顶点构成的闭路径，最终必可得到一条从v到v的长度不大于n的回路。2、证明：在简单无向图G中，从结点u到结点v,如果既有奇数长度的通路又有偶数长度的通路，那么G中必有一奇数长度的回路。证设G中，从结点u到结点v的奇数长度的通路为0，偶数长度的通路为E。对O和E的除结点u和v的相交结点的数目归纳k。k=0,那么O和E恰好构成G的奇数长度的回路。设奇数长度的通路与偶数长度的通路的相交结点的数目少于k时，命题成立。设图G中，从结点u到结点v的奇数长度的通路与偶数长度的通路有k个相交结点，如图所示：-1"-个相交结点，如图所示：-1"-””””「.2J".」,k考虑结点u到结点k,如果从结点u到结点k,既有奇数长度的通路又有偶数长度的通路，那么据归纳假设，其中有一奇数长度的回路，因而G中必有一奇数长度的回路。如果从结点u到结点k的两条通路均为偶数长度，或均为奇数长度,那么结点k到结点v必然既有奇数长度的通路又有偶数长度的通路，因而构成一奇数长度的回路。3、证明：若简单无向图G是不连通的，那么G—3、证设简单无向图G是不连通的，那么G由两个不相关的子图（没有任何边关联分别在两个子图中的顶点）G1，G2组成，分别有顶点，u,u,…,u和v,v,…,V］。12k12l由于边(u,v)均不在6中(i=1,2,…，k,j=1,2,・・・，i)ij因此（u,v）全部在G—中，从而G—是连通的。ij4、有向图可用于表示关系，图表示的二元关系是传递的吗说说如何由有向图判定关系的传递性。求图表示的二元关系的传递闭包，说说构作有向图传递闭包的方法。

解图表示的二元关系不是传递的。有向图表示的关系是传递的，当且仅当对图中任意两个结点u,v,如果有从u到V的路径，则必有从u到V的边。图表示的二元关系的传递闭包如图（b）所示。构作有向图传递闭包的方法是：对图中任意两个结点u,v,如果有从u到V的路径，则添加从u到V的边。5、给出图中有向图的强分图,单向分图和弱分图,作出它的凝聚图。图V5、给出图中有向图的强分图,单向分图和弱分图,作出它的凝聚图。图V10解图中有向图的强分图有：<{V,V},{<V,V>,<V,V>}>,121221<{V,V,V},{<V,V>,<V,V>,<V,V>,<V,V>}>,34535434554<{V6},{<V6,V6>}>,<{V,V,V},{<V,V>,<V,V>,<V,V>}>,789788997

<{v},{}>10图中有向图的单向分图有：<{v,v,v,v,v,v},{<v,v>,<v,v>,<v,v>,<v,v>,<v,v>,<v,v>123456122114234335,<v,v>,<v,v>,<v,v>}>,455436<{v,v,v,v},{<v,v>,<v,v>,<v,v>,<v,v>}>78910788997710TOC\o"1-5"\h\z图的凝聚图：{v}102o*o{V3，V4{V3，V4，V「}5o789106、有7人a,b,c,d,e,f,g分别精通下列语言，问他们7人是否可以自由交谈（必要时借助他人作翻译）。a精通英语。b精通汉语和英语。c精通英语、俄语和意大利语。d精通日语和英语。e精通德语和意大利语。f精通法语、日语和俄语。g精通法语和德语。解下图中7个顶点表示7个人,关联两个顶点的边表示两个人同时精a通某一种语言：d

d由于该图是连通的，因此他们7人是可以自由交谈（必要时借助他人作翻译）。7、证明：一个有向图是单向连通的，当且仅当它有一条经过每一结点的路径。证充分性是显然的。必要性：设有向图G是单向连通的，P是G中的一条路径，起点为u,1终点为u。如下延长这一路径：k考虑路径外的任意顶点w,若（1）有顶点w到u的路径，则我们如愿。1（2）有顶点u到w的路径，则我们如愿。否则，由于有向图是单向连通k的，（3）有顶点w到u的路径，和顶点u到w的路径，则我们如愿。否则,kk-1由于有向图是单向连通的，⑷有顶点w到7的路径，和顶点儿-2到w的路径，则我们如愿。否则,（5）如此等等…，有顶点w到u的路径，和顶点u到w的路径，则我k1们如愿。如上不断延长这一路径，直至产生一条经过每一结点的路径。8、称d(u,v)为图G=<V,E,屮〉中结点u,v间的距离：0当u=vd(u,v)=当u到v不可达u,v间最短路径长度否则d称为图G的直径，如果d=max{d(u,v)?u,v?V}。试求图中图的直径,x(G)，入(G),6(G),并指出一个点割集和一个边割集。图解d=3,x(G)=3，入(G)=3,S(G)=3。9、顶点v是简单连通图G的割点，当且仅当G中存在两个顶点vl,v2,使vl到v2的通路都经过顶点v。试证明之。证充分性是显然的。必要性：设顶点v是简单连通图G的割点，如果不存在两个顶点vl,v2,使v1到v2的通路都经过顶点v,那么对任意两个顶点vl,v2,都有一条通路不经过顶点v，因而删除顶点v不能使G不连通，与v是简单连通图G的割点矛盾。故G中必存在两个顶点vl,v2，使vl到v2的通路都经过顶点v。10、边e是简单连通图G的割边，当且仅当e不在G的任一回路上。试证明之。证设e是简单连通图G的割边，其端点为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怎样把三个动物带过河去（提示：用结点代表状态，状态用序偶〈S1,S2＞来表示，这里S1，S2分别是左岸和右岸的人及动物集合，例如初始状态为＜{m,d,c,r},?＞。解描述上述问题的有向图如下：12、有向图可以刻划一个系统的状态转换，例如用图中的有向图可以描述识别010?10序列的状态转换系统。其中S为初始状态，在此读入序列，然后依序列中符号转入后续状态（读到0进入S1,读到1进入S2,如此等等）°S4表示读完序列010?10应进入的最后状态,S5表示读完一个非010?10序列应进入的最后状态。试自行构作识别序列01（10）?10的有向图刻划的状态转换系统。（上文中w?表示空字或重复任意多次导所得的字。）Q-―~~o1-—o——oSK.11S30欧拉图与哈密顿图内容提要3.1欧拉图与欧拉路径定义图G称为欧拉图（Eulergraph）,如果图G上有一条经过G的所有顶点、所有边的闭路径。图G称为欧拉路径（Eulerwalk），如果图G上有一条经过G所有顶点、所有边的路径。定理无向图G为欧拉图当且仅当G连通，并且所有顶点的度都是偶数。有向图G为欧拉图，当且仅当G是弱连通的，并且每个顶点的出度与入度相等。定理如果G为欧拉图，那么G可分成若干个（一个或几个）回路。定理无向图G为欧拉路径（非欧拉图），当且仅当G连通，并且恰有两个顶点的度是奇数。有向图G为欧拉路径（非欧拉图），当且仅当G连通，并且恰有两个顶点的入度与出度不等，它们中一个的出度比入度多1，另一个入度比出度多l。哈密顿图及哈密顿通路定义无向图G称为哈密顿图（Hamiltongraph），如果G上有一条经过所有顶点的回路（也称这一回路为哈密顿回路）。称无向图有哈密顿通路（非哈密顿图），如果G上有一条经过所有顶点的通路（非回路）。定理设图G为具有n个顶点的简单无向图，如果G的每一对顶点的度数之和都不小于n-1,那么G中有一条哈密顿通路；如果G的每一对顶点的度数之和不小于n,且n#3,那么G为一哈密顿图。

定理当n为不小于3的奇数时，K上恰有」条互相均无任何公共2边的哈密顿回路。定义图G称为可2-着色（2-chromatic），如果可用两种颜色给G的所有顶点着色，使每个顶点着一种颜色，而同一边的两个不同端点必须着不同颜色。定理设图G是可2-着色的。如果G是哈密顿图，那么着两种颜色的顶点数目相等；如果G有哈密顿通路，那么着两种颜色的顶点数目之差至多为一。习题解答练习&31、试作出四个图的图示，使第一个既为欧拉图又为哈密顿图；第二个是欧拉图而非哈密顿图；第三个是哈密顿图却非欧拉图；第四个既非欧拉图也非哈密顿图。解（a）既为欧拉图又为哈密顿图；（b）是欧拉图而非哈密顿图；（c）是哈密顿图却非欧拉图；（d）既非欧拉图也非哈密顿图。(b)(b)2、像第一题要求的那样对欧拉路径和哈密顿通路作出四个图。解（a）既有欧拉路径又有哈密顿通路；（b）有欧拉路径而无哈密顿通a)欧拉(b)(c)a)欧拉(b)(c)3、问n为何种数值时，K既是欧拉图又是哈密顿图。问k为何值时，nk-正则图既是欧拉图又是哈密顿图。解n为奇数时，K既是欧拉图又是哈密顿图。k为大于或等于n/2的n偶数时，k-正则图既是欧拉图又是哈密顿图。4、证明：恰有两个奇数度顶点u,v的无向图G是连通的，当且仅当在G上添加边（u,v）后所得的图G*是连通的。证必要性是显然的。设G*是恰有两个奇数度顶点u,v的无向图G添加边（u，v）后所得，且是连通的,那么图G*是一个欧拉图（每一个顶点都是偶数度的连通图），因此G*中删除边（u,v）后所得的图G仍是连通的。5、参阅练习第2题。问马可否从某处出发完成所有可能的跳步一次且仅一次后回到原地。解练习第2题中的图不是欧拉图（它有三个3度的顶点），因此马不可能从某处出发完成所有可能的跳步一次且仅一次后回到原地。6、参阅练习第2题。问马可否从某处出发跳遍棋盘的所有方格一次且仅一次后回到原地。解马可以从某处出发跳遍棋盘的所有方格一次且仅一次后回到原地。具体跳步如下图所示:

幻方中数字n表示第n个跳步的起点。下图则表示跳步的图示。50112463143726352362511225341538104964214013362761229523328391648760120415429594458533217426472574419305535854631564318幻方7、试计算K(n#3)中不同的哈密顿回路共有多少条。n解不同的哈密顿回路共有(n1)!条。可以用依次选取每一条边来生成2哈密顿回路。因为组成回路的第一条边的选择可能是n种,组成回路的第

二条边的选择可能是n-1种，…，组成回路的第n-1条边的选择可能是2种，组成回路的第n条边的选择可能是1种，而每一哈密顿回路由此生成两次，因此不同的哈密顿回路共有0二1!条。28、十一个学生在一张圆桌旁共进晚餐，要求在每次晚餐上每个学生的邻座都与其它各次晚餐的邻座不同。问这样共进晚餐能安排多少次。解每次晚餐上每个学生的邻座都与其它各次晚餐的邻座不同的安排方式有口种（根据定理。）29、判别图中各图是否为哈密顿图，若不是，请说明理由，并回答它是否有哈密顿通路。(c)(c)解（a），（b）是为哈密顿图。（c）不是哈密顿图，也没有哈密顿通路。在图（c）中增加顶点k,并对其顶点做二着色，构成图（d）（如下）。图（d）不是哈密顿图，也没有哈密顿通路。因为图中白色顶点比黑色顶点多两个。故（c）不是哈密顿图，也没有哈密顿通路。否则它的哈密顿回路或哈密顿通路必定经过顶点k（k在两个二度顶点之间的边上），从而图（d）也是哈密顿图，也有哈密顿通路，矛盾。kk2210、证明：对哈密顿图G=〈V,E,屮〉删除S(?V)中的所有顶点后，所得图G'的连通分支数不大于？S?。证设G1是G中的哈密顿回路，显然在G1中删除S(?V)中的所有顶点后，所得图G1'的连通分支数k1,不小于在G中删除S(?V)中的所有顶点后，所得图G'的连通分支数k,即kWk1。由于G1是一条回路，在G1中删除S(?V)中的所有顶点后，所得图G1'的连通分支数k1不大于？S?是显然的，即k1W?S?。因此kWk1W?S?11、设G为(n,m)图。证明：如果m>C2+2，那么G为哈密顿图(提n—1示：运用定理)。证设G中有两个顶点v1和v2的度数之和不大于n-1，那么以v1和v2为端点的边不多于n-1条。而其余顶点之间的边的数目不多于(n—2)(n—3)条。故G的总边数m满足kk=1k=1m<n—1+(n—2)(n—3)2=*(2n一2+n2一5n+6)=2(n2一3n+4)=-(n—1)(n—2)+12=C2+1n—1与m>C2+2矛盾，故G中任意两个顶点的度数之和大于n。根据定理，Gn—1为哈密顿图。12、设有n个围成一圈跳舞的孩子，每个孩子都至少与其中n个是朋2友。试证明，总可安排得使每个孩子的两边都是他的朋友。证设n个孩子为n个顶点，用边表示顶点间的朋友关系构成一个图G。由于每个孩子都至少与其中n个是朋友，因此G的每一顶点的度数至少是2n，从而G的任何两个顶点的度数之和至少是n。根据定理，G为哈密顿图。2即G有哈密顿回路，这表明，总可安排n个孩子围成一圈跳舞，使每个孩子的两边都是他的朋图的矩阵表示内容提要8.4.1关联矩阵定义设G为(n，m)图，那么n?m矩阵A二［a.］，ij［1当边e以顶点v为端点a=<j°ij|0否则称为G的关联矩阵(incidencematrix)，记为A(G)。

定理若G为(n,m)连通简单图。那么A的秩为n-l(即其最大非零行列式的阶数为n-l)。邻接矩阵定义设G二〈V,E,屮〉为一无重边的有向图。其中V二{v,v,…,v},TOC\o"1-5"\h\z12n那么n?n矩阵A=[a],ij'1a=<

ij0当<v,v>GE(或(v'1a=<

ij0ijij当<v,v>电E(或(v,v)电E)ijij称为图G的邻接矩阵(adjacencymatrix),记为A[G]用A】表示l个矩阵A的乘积。令A】二[a(i)]，那么a(i)的意义是：G中从顶点v到v的长度为lijijij的拟路径恰为a(i)条。ij令AOAi=[b]，那么b的意义是：有b个顶点v,使得v到v,ijijijiv到v都有边(两边交于v)。因而b表示顶点v的出度。jiii令AiOA=[b]，那么b的意义是：有b个顶点v,使得v到ijijijv,v到v都有边；因而b表示顶点v的入度。ijiii路径矩阵与可达性矩阵设n个顶点的图G的邻接矩阵为A,V及人表示如下定义的矩阵运算.若A=[a],C=[c]，贝Ui