作业参考[精选].docVIP

第一周： P9. 2 证明： 用反证法，假设存在一个孤立节点，则根据简单图的定义，刨去这个孤立节点后的图仍然是简单图。而对节点数为n-1的简单图存在不等式： 而题目中的条件为： 矛盾，所以假设不成立，G中不存在孤立节点。 P9. 3 证明： 在有向完全图中，任意一个结点的总度数 所以， 所以，等式两边相等。 证毕。 ---------------------------------------------------------------------------------------------------------------------- 第二周： P10. 7图的同构 答：a图的出度序列是22a，11a，22b，03，11b，30；b图的序列是11c，22c，22d，11d，03，30，两图可能同构，但是还需要看具体能否找到映射。为了利用上面的信息，这里把节点的名字改写（实际上上面已经是改写后的节点名称了）。然后我们对左图写出每个节点的出边的入射点，如果我们存在一个映射使得这种列表是同构的，那么原图就同构。列表如下，注意左图是按照原始的节点顺序，右图不是，而是为了方便找到映射，改变了节点在列表中的顺序。 左图 右图 22a-11a、03 22c-11c, 03 11a-11b 11c-11d 22b-22a, 03 22d-22c, 03 03 03 11b-22b 11d-22d 30-22a, 22b, 03 30-22c, 22d, 03 比较显然的是，存在这样的映射，对应到原图这个映射是（1，b）, （2，a）, （3，c）, （4，e）, （5，d）, （6，f）。 P10. 8 1.8.1邻接矩阵 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 1.8.2关联矩阵 为了写出关联矩阵，我们需要对边进行排序，排序要有个规则，规则是首先按照节点顺序，对于同一个节点，按照顺时针的方向排序，这样比较有规律，需要说明的是，课本上貌似是按照节点顺序的，但是对于同一个节点，其排边的顺序不是很统一。 1 -1 1 -1 0 0 0 0 0 -1 0 0 0 1 0 0 0 0 0 1 0 0 0 1 -1 -1 0 0 0 -1 0 0 -1 0 0 -1 0 0 0 0 -1 0 1 0 0 0 0 0 1 0 0 0 1 1 1.8.3边列表 1 3 1 6 2 3 5 6 6 2 1 4 1 5 4 3 3 4 1.8.4正向表 1 3 4 6 6 7 10 Null null 2 4 5 1 4 3 1 3 4 P35.1 证明：设G的k个连通支的结点数分别为n1，n2……，nk， 易知n1+n2+……+nk = n。 对于任意的ni，另外（k-1）个连通支至少有（k-1）个结点 所以， 对每个连通支， （完全图达到最大值） 所以，得证。 P35.2 证明：若G为非连通图，设G有k个连通分支，则G中某连通支内任意点与其余（k-1）各连通支的点无连线，那么在中这个点与其余（k-1）个连通支的点都有连线。 所以，不同连通支中的任意两个点之间在中都有连线。 在G中位于同一连通支内的任两点，在中可以通过与其余（k-1）个连通支的某一点相连而形成通路。 所以，为连通图。 同理，若非连通，则G连通。 证毕。 P35.3 证明思路：设（v1……v2）和（v3……v4）是连通图G的两个不相交的最长道路， 由连通性知v2和v3之间存在道路。 因此，道路（v1……v2…v3……v4）必大于（v1……v2）和（v3……v4） 与题设矛盾 所以，不存在两条不相交的最长道路 ---------------------------------------------------------------------------------------------------------------------- 第三周： 当m和n为何值时，二分图Km，n是欧拉图？ 解：Km，n是完全二分图 两个顶点集合 |V1| = m，|V2| = n V1 中任一节点的度为m，V2 中任一节点的度为n 每个节点的度为偶数时该图为欧拉图 所以，m，n均为偶数时，满足题目要求。 P35.4 证明： 用数学归纳法。 n=4，命题成立。 n=5时假设命题成立， n+1时，若图中有度小于等于2的点V，则G-V是有n个结点的图，且满足m=2n-3， 故G-V中有带弦回路。 综上，命题成立。 P35.5 证明： （a） 因为图中没有三角形，所以d（Vi）+ d（Vj）= n。 左式求