列各组数中，那些能构成无向图的度数列？那些能构成无向简单图的度数列？（1）1，1，1，2，3（2）2，2，2，2，2（3）3，3，3，3（4）1，2，3，4，5（5）1，3，3，3解答：（1），（2），（3），（5）能构成无向图的度数列。（1），（2），（3）能构成五项简单图的度数列。设有向简单图D的度数列为2，2，3，3，入度列为0，0，2，3，试求D的出度列。解：因为出度=度数-入度，所以出度列为2，2，1，0。设D是4阶有向简单图，度数列为3，3，3，3。它的入度列（或出度列）能为1，1，1，1吗？解：由定理可知，有向图的总入度=总出度。该有向图的总入度=1+1+1+1=4,总出度=2+2+2+2=8,4！=8，所以它的出度列（或入度列）不能为1，1，1，1。35条边，每个顶点的度数至少为3的图最多有几个顶点？解：根据握手定理，所有顶点的度数之和为70，假设每个顶点的度数都为3，则n为小于等于370的最大整数，即：２３∴最多有23个顶点7.7设n阶无向简单图G中，δ（G）=n-1，问△（G）应为多少？解：假设n阶简单图图n阶无向完全图，在Kn共有2)1(nn条边，各个顶点度数之和为n（n-1）∴每个顶点的度数为nnn)1(=n-1∴△（G）=δ（G）=n-1一个n（n≥２）阶无向简单图Ｇ中，n为奇数，有r个奇度数顶点，问Ｇ的补图G中有几个奇度顶点？解：在Kn图中，每个顶点的度均为（n-1），n为奇数，在Ｇ中度为奇数的顶点在G中仍然为奇数，∴共有r个奇度顶点在G中７.９设Ｄ是n阶有向简单图，Ｄ’是Ｄ的子图，已知Ｄ’的边数m’＝n（n-1），问Ｄ的边数m为多少？解：在Ｄ’中m’＝n（n-1）可见Ｄ’为有个n阶有向完全图，则Ｄ＝Ｄ’即Ｄ’就是Ｄ本身，∴m=n（n-1）有向图D入图所示。求D中长度为4的通路总数，并指出其中有多少条是回路？又有几条是V3到V4的通路？答:D中长度为四的通路总数：15其中有3条是回路2条是V3到V4的通路评语：此题的结果是对的，但是应该写出求解过程，即：先写出邻接矩阵A，然后求A的四次幂，通过矩阵指出通路或回路的条数。设n阶图G中有m条边，每个顶点的度不是k就是k+1，若G中有Nk个k度顶点，Nk+1个(k+1)度顶点，则Nk为？解:由题义可以得到:Nk*k+Nk+1*(k+1)=2m①握手定理Nk+Nk+1=n②n阶图由①②解得Nk=n*(k+1)-2m
