离散数学习题解答第6部分(图论).docx

离散数学习题解答第6部分(图论)离散数学习题解答 习题六 〔第六章 图论〕 1．从日常生活中列举出三个例子，并由这些例子自然地导出两个无向图及一个向图[解] ①用V代表全国城市的集合，E代表各城市间的铁路途的集合，那么所成之图G=〔V，E〕是全国铁路交通图是一个无向图②V用代表中国象棋盘中的格子点集，E代表任两个相邻小方格的对角线的集合，那么所成之图G=〔V，E〕是中国象棋中“马”所能走的路途图是一个无向图③用V代表FORTRAN程序的块集合，E代表任两个程序块之间的调用关系，那么所成之图G+〔V，E〕是FORTRAN程序的调用关系图是一个有向图 2．画出下左图的补图 [解] 左图的补图如右图所示3．证明下面两图同构v2 a 图G′v3 图Gv4[证] 存在双射函数 :V→V′及双射函数 : E→E′ (v1)=v1′ (v2)=v2′ (v3)=v3′ (v4)=v4′ (v5)=v5′ (v6)=v6′ (v1，v2)=(v1′，v2′) (v2，v3)=(v2′，v3′) (v3，v4)=(v3′，v4′) (v4，v5)=(v4′，v5) (v5，v6)=(v5′，v6′) (v6，v1)=(v6′，v1′) (v1，v4)=(v1′，v4′) (v2，v5)=(v2′，v5′) (v3，v6)=(v3′，v6′) 明显使下式成立： (vi，vj)=(vi,vj′) (vi)=v i′∧ (vj)=vj′ (1≤i·j≤6) 于是图G与图G′同构。

4．证明〔a〕，〔b〕中的两个图都是不同构的 图G中有一个长度为4的圈v1v2v6v5v1，其各顶点的度均为3点，而在图G′中却没有这样的圈，因为它中的四个度为3的顶点v1 ，v5 ，v7 ，v3 不成长度的4的圈图G中′有四个二度结点，v6 ，v8 ，v4 ，它们每个都和两个三度结点相邻，而G中一个区样的结点都没有在〔b〕中，图G 中有一2度结点v3 ，它相邻的两个项点v2 ，v4 的度均为4，而在图G中却没有这样的点GG′GG′v3v45．一个图假设同构于它的外图，那么称此图为自补图在满意以下条件的无向简洁图中： 1) 给出一个五个结点的自补图；2)有三个或一结点的自补图吗？为什么？3〕证明：假设一个图为自补图，那么它对应的完全图的边数不清势必为偶数 [解] 1) 五个结点的自补图如左图G所示同构函数 : V→V及 : E→E如下： (a)=a (b)=c (c)=e (d)=b (e)=d (a，b)=(a，c) (b，c)=(c，e) (c，d)=(e，d) (d，e)=(b，d) (e，a)=(d，a) GGebae2)〔a〕没有三个结点的自补图。

因为三个结点的完备图的边数为3(3 1)=32为奇数，所以由下面3)的结论，不行能有自补图〔b〕有五个结点的自补图1〕中的例子即是一个五个结点的自补图 3〕证：一个图是一个自补图，那么它对应的完全图的边数必为偶数因为假设一个图G是自补图，那么G∪G=对应的完全图，而且E∩E=φ，G现G同构，因此它们的边数相等，即|E|=|E|，因此对应的完全图的边数|E*|=|E|+|E|=2|E|，是偶数事实上，n个项点〔n＞3〕的自补图G，由于其对应的完全图的边数|E*|=n(n 1)n(n 1)，因此有=2|E|，为偶数这里n≥4对于全部大于或等22于4的正整数，都可表达成n=4k，4k+1，4k+2，4k+3的形式，这里k=1，2， 其中只有n=4k，4k+1，才能使4k或4k+1形式，〔k∈N〕n(n 1)为偶数，所以自补图的项点数只能是26．证明在任何两个或两个以上人的组内，总存在两个人在组内有一样个数的挚友[证] 令上述组内的人的集合为图G的项点集V，假设两人相互是挚友，那么其间联以一边所得之图G是组内人员的挚友关系图明显图G是简洁图，图中项点的度恰表示该人在组内挚友的个数，利用图G，上述问题就抽象成如下的图认论问题：在简洁图G中，假设|V|≥2，那么在G中恒存在着两个项点，v1，v2∈V，使得它们的度相等，即deg(v1)=deg(v2)。

其证明如下：假设存在着一个项点v∈V，使得deg(v)=0，那么图G中各项点的度最大不超过n-2因此n个项点的度在集合{0，1，2， ，n-2}里取值，而这个集合只有n-1个元素，因此，依据鸽笼原理，必有两个项点的度一样假设不存在一个度为零的项点，那么图G中各项点的度最大不超过n-1因此n个项点的度在集合{1，2， ，n-1}中取值，这个集合只有n-1个元素，因此，依据鸽笼原理，必有两具项点的度一样 7．设图G的图示如右所示： 1) 找出从A到F的全部初级路；2〕找出从A到F的全部简洁路； 3〕求由A到F的距离 [解] 1〕从A到F的初级路有7条EP1 : (A，B，C，F)，P2 (A，B，C，E，F)，P3 : (A，B，E，F) P4 : (A，B，E，C，F)，P5 : (A，D，C，E，F)，P6 : (A，D，E，C，F) P7 : (A，D，E，B，C，F) 2〕从A到F的简洁路有9条除了上述1〕中7条外，不有P8 : (A，D，E，C，B，E，F) P9 : (A，D，E，B，C，E，F) 3〕从A到F的距离为3由图可看出，明显从A到F，一步不行能到达，二步也不行到达；但有长度为3的路，比方P1，P3，P5等能从A到F，故从A到F的距离为3。

8．在下面的图中，哪此是边通图？哪些是简洁图？ 〔a〕 (b) (c)[解] 〔1〕图〔2〕与图〔b〕不连通，它们能分成两个边通支所以只有图〔c〕是连能图〔2〕图〔c〕是简洁图，图为它明显无同等边，无自环图〔a〕、〔b〕是多重图〔a〕有平行边〔b〕有自环9．求出全部具有四个结点的简洁无向连通图[解] 在不同构的意义下，具有四个结点的简洁无向连通图共有6个如下面所示：G1G2 G2G3G4 G4G5 G5G6 G6 lya定理得证参见卢〔事实上，具有四个结点的简洁图共有11个，这可由P o 开澄的《组合数学一算法与分析》上册P241-P244〕 10．设G是一个简洁无向图，且为〔n，m〕图，假设1m (n 1)(n 2)2证明G是连通图[证] 用反证法假如简洁无向图G不是连通图，那么G必可成K〔≥2〕个连通分支G1，G2， ，Gk，每个连通分支Gi〔1≤i≤k〕都是一个简洁无向图，因此它们分别为〔n1，m1〕，〔n2，m2〕， 〔nk，mk〕图明显有n=n1+n2+ nk，m=m1+m2+ mk，且ni≤n-1〔1≤i≤k〕于是有m=m1+m2+ mkn1(n1 1)n2(n2 1)n(n 1) kk 222 (n 1)(n1 1)(n 1)(n2 1)(n 1)(nk 1)222=(n-1)·== ≤1·((n1-1)+(n2-1)+ +(nk-1)) 21(n-1)((n1+n2+ +nk)-k) 21(n-1)(n-k) 21(n-1)(n-2) (k≥2) 21〔n-1〕(n-2)冲突。

2这与确定M＞因此假设错误，G是连通图11．设G=〔V，E〕是无向完全图〔无自环〕，|V|=n1〕 求G中有多少初级圈？2〕 设e∈E，求含有e的初级圈有几个？3〕 设u，v∈V，u≠v，求由u到v有几条初级路？[解] 1〕在一个有n个结点的无向完全图〔无自环〕中，构成一个初级圈，至少需3个结点，至多有n个结点，故G中初级圈的个数为2! n 3! n (n 2)! n (n 1)! n 2 3 2 4 2 n 2 2 n 1 Akn(个)k 32 列〔除2〕；长为k的圈排列可形成k个线排列〔除k〕 2〕含有边e的初级圈为n 2k 0n 即将从n个结点中选出的k个结点进展排列，然后除去重复：每个排列的倒排A1n 2 A 2n 2 A n 2n 2 Akn 2(个) 即，从u到v的干脆边〔完全图，该边存在〕是一条；再将该干脆边加到其它初级路里，就构成了含边〔u，v〕的初级圈，从而由2)可得如上数值12．试证在简洁有向图中1) 每个结点及每条边都属于且只属于一个弱分图； 2) 每个结点及每条边都至少属于一个单向分图[证] 1〕有向图中的弱连通性建立了G中结点集合V上的等价关系，因此构成了V上的一个划分；同时，还建立了边集上的一个划分。

因此，每一个弱连通支就是一个“划分块”设G1，G2， ，Gk为G的全部弱连通分图，那么有：V〔G〕=V〔G1〕∪V〔G2〕 ∪V〔Gk〕 E〔G〕=E〔G1〕∪E〔G2〕 ∪E〔Gk〕并且，当i≠j时，V〔Gi〕∩V〔Gj〕=φ，E〔Gi〕∩E〔Gj〕=φ因此，每个结点及每条边都属于且只属于一个弱图2〕有向图中的单向连通性建立了G中结点集合V上的一个相容关系，因此构成了V上的一个覆盖；同时，还建立了边集上的一个覆盖；每一个单向分图就是一个“覆盖快”设G1，G2 ，Gk为G的全部单向分图，那么有V〔G〕=V〔G1〕∪V〔G2〕∪ ∪V〔Gk〕 E〔G〕=E〔G1〕∪E〔G2〕∪ ∪E〔Gk〕 因此，每个结点及每条边都至少属于一个单向分图13．试用有向图描述出下述问题的解法路径：某人m带一条狗d，一只猫c和一只兔子r过河，没有船，他每次游过河时只能带一只动物，当没有人管理时狗和兔子不能相处，猫和兔子也不能相处在这些条件的约束下，他怎样才能将这三只动物从北岸带往南岸？[解] 将人，狗，兔中随意几种在一起的状况看作是一种状态；一个布局是一个二元组，由两个互补的状态构成，二元组的前者表示河北岸的状态，后者表示河南岸的状态。

初始布局为〔pdcr，φ〕，终止布局为〔φ，pdcr〕平安布局有十种，担心全布局有六种，它们是：〔dr，pc〕，〔cr，pd〕，〔dcr，p〕， 〔pc，dr〕，〔pd，cr〕，〔p，dcr〕14．求以下图中的全部强连通支，单向连通支，弱连通支 v5v6v10 [解] 1〕有六个强连通支，它们是：G1=({v1，v2，v3，v9，v10}，{(v1，v2)，(v2，v9)，(v9，v10)，(v10，v1)，(v2，v3)，(v3，v9)})G2=({v4}，φ)，G3=({v8}，φ)，G4=({v7}，φ)， G5=({v5}，{(v5，v5)})，G6=({v6}，φ)2〕有四个单向连通支，它们是：G1=({v1，v2，v3，v4，v9，v10}，{(v1，v2)，(v2，v9)，(v9，v10)，(v10，v1)，(v2，v3)，(v3，v9)，(v3，v4)})，G2=({v4，v7，v8}，{(v7，v8)，(v8，v4)})， G3=({v5}，{v5，v5})，G4=({v6}，φ) 3〕有三个弱连通支，它们是G1=({v1，v2，v3，v4，v7，v8。