习题参考答案
1、设无向图G有16条边，有3个4度结点，4个3度结点，其余结点的度数均小于3，问：G中至少有几个结点。
阮允准同学提供答案:
解：设度数小于3的结点有x个，则有 3×4＋4×3＋2x≥2×16 解得：x≥4
所以度数小于3的结点至少有4个 所以G至少有11个结点
2、设无向图G有9个结点，每个结点的度数不是5就是6，证明：G中至少有5个6度结点或至少有6个5度结点。
阮允准同学答案：
证明：由题意可知：度数为5的结点数只能是0,2，4,6，8。
若度数为5的结点数为0,2，4个，则度数为6的结点数为9，7,5个结论成立。
若度数为5的结点数为6,8个，结论显然成立。
由上可知，G中至少有5个6度点或至少有6个5度点。
3、证明：简单图的最大度小于结点数。
阮同学认为题中应指定是无向简单图.
晓津证明如下：设简单图有n个结点，某结点的度为最大度，因为简单图任一结点没有平行边，而任一结点的的边必连有另一结点，则其最多有n-1条边与其他结点相连，因此其度数最多只有n-1条，小于结点数n.
4、设图G有n个结点，n+1条边，证明：G中至少有一个结点度数≥3 。 阮同学给出证明如下：
证明：设G中所有结点的度数都小于3，即每个结点度数都小于等于2，则所有结点度数之和小于等于2n，所以G的边数必小于等于n，这和已知G有n+1条边相矛盾。所以结论成立。
5、试证明下图中两个图不同构。
晓津证明：同构的充要条件是两图的结点和边分别存在一一对应且保持关联关系。我们可以看出，(a)图和(b)图中都有一个三度结点，(a)图中三度结点的某条边关联着两个一度结点和一个二度结点，而(b)图中三度结点关联着两个二度结点和一个一度结点，因此可断定二图不是同构的。
6、画出所有5个结点3条边，以及5个结点7条边的简单图。 解：如下图所示： (晓津与阮同学答案一致)
7、证明：下图中的图是同构的。
证明如下：
在两图中我们可以看到有 a→e,b→h,c→f,d→g
两图中存在结点与边的一一对应关系，并保持关联关系。
8、证明：下面两图是同构的。
阮同学给出证明如下：
证明：找出对应关系：a---q, b----r, c-----s, d----t, e-----u, f------v, g-----w, h----x
9、证明：三次正则图必有偶数个结点。 阮同学证明如下：
由题意可知每个结点度数都是3度，即每个结点均为奇结点，根据有偶数个奇结点可知，三次正则图必有偶数个奇结点。
习题参考答案
1、 给定图G，如下图所示，求出G中从A到F的所有初级路。
2、
解：从A到F的初级路有：
ABCF、ABEF、ADEF、ABECF、ABCEF、ADECF、ADEBCF
2、给定图G，如下图所示，找到G中从v2出发的所有初级回路。
晓津认为图中少了一个箭头：从V1到V2有一箭头。 从V2出发的初级回路有：V2V4V1V2、V2V3V4V1V2.
3、设G为无向连通图，有n个结点，那么G中至少有几条边为什么对有向图如何
解：若G为无向连通图，有n个结点，则G中至少有n-1条边。因为在n个结点的图中，任取一个结点为起始点，若要连通其他每个结点，则其他每个结点至少应有1度,此结点则有n-1度。因此总的度数至少为2n-2度，而度数为边的2倍，可算得边数为n-1.
相关推荐：
loading