离散数学及其应用-第2版第10章部分习题解答

习题设无向图G=（V，E），V={v1，v2，v3，v4，v5}，E={（v1，v2），（v2，v2），（v2，v4），（v4，v5），（v3，v4），（v1，v3），（v3，v1）}。画出G的图形；求出G中各结点的度及奇数度结点的个数。解答：a)b)d(v1)=3，d(v2)=4，d(v3)=3，d(v4)=3，d(v5)=1下列序列中，哪些是可构成无向简单图的结点度数序列？1）（1，1，2，2，3）2）（1，1，2，2，2）3）（0，1，3，3，3）4）（1，3，4，4，5）5）（0，1，1，2，3，3）解答：1)N2)Y3)N4)N5)Y(当删去一个3度结点的度数序列为(0,0,1,1,2,0)时)，N（当删去一个3度结点的度数序列为(0,0,0,1,3,0)时)设无向图G有16条边，3个4度结点，4个3度结点，其余结点的度数均小于3，问：G中至少有几个结点。解：设度数小于3的结点有x个，则有3×4＋4×3＋2x≥2×16解得：x≥4所以度数小于3的结点至少有4个所以G至少有11个结点证明：若有n个人，每个人恰恰有三个朋友，则n必为偶数。证明：n个人对应n个结点，每个人恰恰有三个朋友，即为每个结点有3度，根据握手定理的推论，n必为偶数。设图G有n个结点，n+1条边，证明：G中至少有一个结点度数≥3。证明：用反证法.若G的最大度(G)则按握手定理2m其中m是边数.从而mn,证明：无向简单图G=(V,E),e=|E|,v=|V|则有ev(v-1)/2.证明：无向简单图是完全图时边数最多，完全图的边数为v(v-1)/2，所以无向简单图有ev(v-1)/2.设图G=(V,E),e=|E|,v=|V|,d(v)min为G中结点的最小度数,d(v)max为G中结点的最大度数.证明:d(v)min2e/vd(v)max.证明：根据握手定理：将式（1）代入式（2），整理得：d(v)min2e/vd(v)max.有n个抽屉，若每两个抽屉里有一种相同的物品，每种物品恰好放在两个抽屉中，问共有多少种物品？解：每个抽屉用一个结点表示；每两个抽屉放相同的物品，在每两个抽屉对应的结点间连接一条边，则构成一个n个结点的完全图，每条边是一个物品。n个结点的完全图有n(n-1)/2条边，所以共有n(n-1)/2种物品。证明：无向简单图的最大度小于结点数。证明：由定义可知，无向简单图是无环无多重边的图，因此n个节点的无向简单图，每个结点最多和其它结点都有边相连接时有n-1条边。因此，简单图的最大度为n-1，小于结点个数n。下列各图有多少个结点和多少条边？1）Kn2）Cn3）Wn4）Km，n5）Qn解：1）n个结点，n(n-1)/2条边2）n个结点，n条边3)n+1个结点，2n条边4)m+n个结点，mn条边5）2n个结点，n*2n-1条边当n为何值时，下列各图是正则图？1）Kn2）Cn3）Wn4）Qn解：(1)对所有n1(2)对所有n>=3(3)4(4)对所有n1证明：3正则图必有偶数个结点。试证明下图中两个图不同构。(b)证明：同构的充要条件是两图的结点和边分别存在一一对应且保持关联关系。我们可以看出，(a)图和(b)图中都有一个三度结点，(a)图中三度结点的某条边关联着两个一度结点和一个二度结点，而(b)图中三度结点关联着两个二度结点和一个一度结点，因此可断定二图不是同构的。证明：下图中的图是同构的。证明：下面两图是同构的。证明：简单图的同构关系是等价关系。提示：简单图的同构关系是自反、对称和传递的。连通图G有n个结点，e条边，则en-1。证明：用归纳法证明。当n=2时，连通图G至少有一条边，e1，所以en-1成立。设n£k时，结论成立，即ek-1。当n=k+1时，=1\*GB3①若删去一个度数为d(v)的结点得到图G’，而且图G’仍是连通的，图G’的结点数和边数分别为k和e’，则e’k-1，e’=e-d(v)，所以e-d(v)k-1，则ek-1+d(v),因为G是连通图，d(v)1,因而ek,所以en-1.=2\*GB3②若删去一个度数为d(v)的结点得到图G’，而且图G’不连通的，假设图G’有两个连通分支G1’、G2’,结点数和边数分别为k1’和e1’，k2’和e2’，则e1’k1’-1，e2’k2’-1,e1’+e2’=e-d(v)，所以e-d(v)k-2，则ek-2+d(v),因为G是连通图，d(v)2,因而ek,所以en-1.给定图G，如下图所示，求出G中从v1到v6的所有基本通路。给定图G，如下图所示，找到G中从v2出发的所有基本回路。设G为无向连通图，有n个结点，那么G中至少有几条边？为什么？对有向图如何？解答：根据定理7.2.3，无向连通图，有n个结点，至少有n-1条边。有向连通图，有n个结点，至少有n-1条边。图G如下图所示，以下说法正确的是()．

A．{(a,d)}是割边N

B．{(a,b),(b，f)}是边割集Y

C．{(d,e)}是割边Y

D．{d}是割点YE.{b,c}是点割集NF.{a,f}是点割集Y设V'和E'分别为无向连通图G的点割集和边割集，G-E'的连通分支数一定是多少？G-V'的连通分支数也是定数吗?解答：G-E'的连通分支数一定是2，G-V'的连通分支数不是一个确定的数。一个有向图是强连通的，当且仅当G中有一个回路，它至少包含每个结点一次。证明：必要性：如果图中的任何一个回路都不能包含所有结点，则可知未被包含在回路内的结点不能与其他结点中的某一结点连通。这与本图是强连通的相矛盾。因此必有这样一个回路它至少包含每个结点一次。充分性：当G中有一个回路，它至少包含每个结点一次时，可以知道，任一结点可达其他所有结点，因此它是强连通的若有简单图至多有2n个结点，每个结点度数至少为n，G是连通图。又若简单图G至多有2n个结点，每个结点度数至少为n-1，那么G是连通图吗？为什么？证明：假设G是不连通的，有两个连通分支，若简单图至多有2n个结点，则至少有一个连通分支的结点数n，这个连通分支的结点最大度数n-1，和每个结点度数至少为n矛盾，所以G是连通图。若简单图G至多有2n个结点，每个结点度数至少为n-1，那么G不一定是连通图。因为由2个n个结点的完全图组成的图有2n个结点，每个结点度数为n-1，是不连通的图。简单图G有n个结点，e条边，设e>0.5(n-1)(n-2),证明：G是连通的。证明：用反证法。假若简单无向图G不是连通图，那么G必可成K（≥2）个连通分支G1，G2，…，Gk，每个连通分支Gi（1≤i≤k）都是一个简单无向图，因此它们的结点数分别为n1，n2，m2，…nk，边数分别为e1，e2，…，ek，显然有n=n1+n2+…nk，e=e1+e2+…ek，且ni≤n-1（1≤i≤k）于是有e=e1+e2+…ek=(n-1)··((n1-1)+(n2-1)+…+(nk-1))=(n-1)((n1+n2+…+nk)-k)=(n-1)(n-k)≤(n-1)(n-2)(k≥2)这与已知e＞0.5（n-1）(n-2)矛盾。因此假设错误，G是连通图。设图G=<V,E>,V={v1,v2,v3,v4}的邻接矩阵则v1的入度是多少？v4的出度是多少？从v1到v4长度为2的通路有几条？有向图G如图所示，求G中长度为4的路径总数，并指出其中有多少条是回路。v3到v4的简单通路有几条。26题图27题图给定图G，求：a)给出G的邻接矩阵，b)求各结点的出、入度，c)求从结点V3出发长度为3的所有回路(1).给出G的邻接矩阵按结点顺序v1,v2,v3,v4给出邻接矩阵如下: [0110]A=[1000] [0101] [0001](2).各结点的出入度 v1 v2 v3 v4出度:2 1 2 1入度:1 2 1 2(3).从结点V3出发长度为3的所有回路 由A3=[1111]可知,长度为3的回路有1条 [1101] [0111] [0001]它是:(v3,v2,v1,v3)给定G如图所示，a)写出邻接矩阵b)G中长度为4的路有几条？c)G中有几条回路？28题图30题图试用矩阵法判断有向图G=({a,b,c,d},{<a,b>,<a,d>,<c,b>,<c,d>})的连通性。解答：1）图G的邻接矩阵：因为B（G）中存在0元素，所以图G不是强连通图。2）图G的可达矩阵为：因为可达矩阵关于主对角线对称位置的存在全为0的元素，所以图G不是单向连通。3）若将图G视为无向图，则邻接矩阵为B无(G)的元素全为1，所以图G是弱连通。求出所示图G的邻接矩阵、可达矩阵，找出从v2到v3长度为3的通路，并计算出A2,A3进行验证。设图G中的边满足W(G-e)>W(G),称e为G的割边（桥）。证明：e是割边，当且仅当e不包含在G的任一回路中。证明： 1）e为割边=〉e不包含于G的任一回