资源描述：
《离散课后习题答案5.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第十四章部分课后习题参考答案5、设无向图G有10条边，3度与4度顶点各2个，其余顶点的度数均小于3，问G至G∆、少有多少个顶点？在最少顶点的情况下，写出度数列、解：由握手定理图G的度数之和为：2×10=20()ä(G)。3度与4度顶点各2个，这4个顶点的度数之和为14度。其余顶点的度数共有6度。其余顶点的度数均小于3，欲使G的顶点最少，其余顶点的度数应都取2,−所以，G至少有7个顶点,出度数列为3,3,4,4,2,2,2,∆()=4,()=2.GäG7、设有向图D的度数列为2，3，2，3，出度列为1，2，1，1，求D的入度列，并求∆(D),ä(D)，+∆(D),ä+(),∆−D(D
2、),ä(D).解：D的度数列为2，3，2，3，出度列为1，2，1，1，D的入度列为1,1,1,2.−∆()=3,()=2,∆+DäD(D)=2,ä+()=1,∆−D(D)=2,ä(D)=18、设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点？解：由握手定理图G的度数之和为：2×6=12设2度点x个，则3×1+5×1+2x=12，x=2，该图有4个顶点.14、下面给出的两个正整数数列中哪个是可图化的？对可图化的数列，试给出3种非同构的无向图，其中至少有两个时简单图。(1)2,2,3,3,4,4,5(2)2,2,2,2,3,3,4,4解：(1)2+2+3
3、+3+4+4+5=23是奇数，不可图化；(2)2＋2+2+2+3+3+4+4=16,是偶数，可图化；18、设有3个4阶4条边的无向简单图G1、G2、G3，证明它们至少有两个是同构的。证明：4阶4条边的无向简单图的顶点的最大度数为3，度数之和为8，因而度数列1为2，2，2，2；3，2，2，1；3，3，1，1。但3，3，1，1对应的图不是简单图。所以从同构的观点看，4阶4条边的无向简单图只有两个：所以，G1、G2、G3至少有两个是同构的。20、已知n阶无向简单图G有m条边，试求G的补图G的边数m′。−解：′=n(n−1)m2m21、无向图G如下图(1)求G的全部点割集与边割集，指出其中的割点和桥
4、；(2)求G的点连通度k(G)与边连通度ë(G)。ae1e2debe5解：点割集:{a,b},(d)e3e4c边割集{e2,e3},{e3,e4},{e1,e2},{e1,e4}{e1,e3},{e2,e4},{e5}kë()=(GG)=1k23、求G的点连通度(G)、边连通度(ëG)与最小度数()。äGk解：(G)=2、ë(G)=3、()=4Gä28、设n阶无向简单图为3-正则图，且边数m与n满足2n-3=m问这样的无向图有几种非同构的情况？⎨3解：⎧n=2m得n=6,m=9.⎩2n−3=m231、设图G和它的部图G的边数分别为m和m，试确定G的阶数。解：m+m=n(n+1
5、)2−1+得n=1+8(m+m)245、有向图D如图(1)求v2到v5长度为1，2，3，4的通路数；(2)求v5到v5长度为1，2，3，4的回路数；(3)求D中长度为4的通路数；(4)求D中长度小于或等于4的回路数；(5)写出D的可达矩阵。v1v4v5v2v3解：有向图D的邻接矩阵为：⎛0000⎜10100⎟⎜00002⎟⎜02020⎟⎜0⎝⎜01011⎞⎟1⎟，A⎟⎠⎛01⎜⎜A=⎜0000⎟2⎜101⎟3⎜020⎟⎜10100⎟⎜00002⎟⎜02020⎟=⎜0⎜⎝20010⎞⎟0⎟A⎟020⎠⎛20200⎞⎜⎟=⎜20⎟4⎜⎟⎝0000⎠⎛00004⎞⎜⎟⎜40400⎟4=
6、⎜00004⎟A⎜⎟⎜40400⎟0⎜⎟⎝0404⎠2A+A+3A+A⎛01⎜⎜524=⎜21⎜⎜42⎜⎝25215⎞⎟522⎟215⎟⎟522⎟⎟425⎠(1)v2到v5长度为1，2，3，4的通路数为0,2,0,0；(2)v5到v5长度为1，2，3，4的回路数为0,0,4,0；(3)D中长度为4的通路数为32；(4)D中长度小于或等于4的回路数10；3⎛1⎜⎜1(4)出D的可达矩阵=⎜1P⎜⎜1⎜⎝11111⎞⎟1111⎟1111⎟⎟1111⎟1⎠111⎟第十六章部分课后习题参考答案1、画出所有5阶和7阶非同构的无向树.2、一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是
7、3度顶点，问T有几个顶点?解：设3度分支点x个，则5×1+3×2+3x=2×(5+3+x−1)，解得x=3T有11个顶点3、无向树T有8个树叶，2个3度分支点，其余的分支点都是4度顶点，问T有几个4度分支点？根据T的度数列，请至少画出4棵非同构的无向树。解：设4度分支点x个，则8×1+2×3+4x=2×(8+2+x−1)，解得x=2度数列11111111334444、棵无向树T有ni几片树叶?(i=2，3，
