图与遍历算法习题参考答案.docVIP

第二章部分习题参考答案 1.证明下列结论： 1）在一个无向图中，如果每个顶点的度大于等于2，则该该图一定含有圈； 2）在一个有向图D中，如果每个顶点的出度都大于等于1，则该图一定含有一个有向圈。 1）证明：设无向图最长的迹每个顶点度大于等于2，故存在与相异的点与相邻，若则得到比更长的迹，与P的取法矛盾。因此，，是闭迹，从而存在圈 证明*：设在无向图G中，有n个顶点，m条边。由题意知，m=(2n)/2=n，而一个含有n个顶点的树有n-1条边。因m=nn-1，故该图一定含有圈。 （定义：迹是指边不重复的途径，而顶点不重复的途径称为路。起点和终点重合的途径称为闭途径，起点和终点重合的迹称为闭迹，顶点不重复的闭迹称为圈。） 2）证明：设有向图最长的有向迹每个顶点出度大于等于1，故存在为的出度连接点，使得成为一条有向边，若则得到比更长的有向迹，与P矛盾，因此必有，从而该图一定含有有向圈。 2.设D是至少有三个顶点的连通有向图。如果D中包含有向的Euler环游（即是通过D中每条有向边恰好一次的闭迹），则D中每一顶点的出度和入度相等。反之，如果D中每一顶点的出度与入度都相等，则D一定包含有向的Euler环游。这两个结论是正确的吗？请说明理由。如果G是至少有三个顶点的无向图，则G包含Euler环游的条件是什么？ 证明：1）若图D中包含有向Euler环游，下证明每个顶点的入度和出度相等。 如果该有向图含有Euler环游，那么该环游必经过每个顶点至少一次，每经过一次，必为“进”一次接着“出”一次，从而入度等于出度。从而，对于任意顶点，不管该环游经过该顶点多少次，必有入度等于出度。 2）若图D中每个顶点的入度和出度相等，则该图D包含Euler环游。证明如下。 对顶点个数进行归纳。 当顶点数|v(D)|=2时，因为每个点的入度和出度相等，易得构成有向Euler环游。 假设顶点数|v(D)|=k时结论成立，则 当顶点数|v(D)|=k + 1时，任取v∈v(D).设S={以v为终点的边}，K={以v为始点的边}，因为v的入度和出度相等，故S和K中边数相等。记G=D-v.对G做如下操作: 任取S和K中各一条边，设在D中，，则对G和S做如下操作 , ，重复此步骤直到S为空。这个过程最终得到的G有k个顶点，且每个顶点的度与在G中完全一样。由归纳假设，G中存在有向Euler环游，设为C。在G中从任一点出发沿C的对应边前行，每当遇到上述添加边v1v2时，都用对应的两条边e1，e2代替，这样可以获得有向Euler环游。 3）G是至少有三个顶点的无向图，则G包含Euler环游等价于G中无奇度顶点。（即任意顶点的度为偶数）。 3．设G是具有n个顶点和m条边的无向图，如果G是连通的，而且满足m = n-1,证明G是树。 证明：思路一： 只需证明G中无圈。 若G中有圈，则删去圈上任一条边G仍连通。而每个连通图边数e=n(顶点数) – 1，但删去一条边后G中只有n-2条边，此时不连通，从而矛盾，故G中无圈，所以G为树。 思路二： 当时，，两个顶点一条边且连通无环路，显然是树。 设当时，命题成立，则 当时，因为G连通且无环路，所以至少存在一个顶点，他的度数为1，设该顶点所关联的边为那么去掉顶点和，便得到了一个有k-1个顶点的连通无向无环路的子图，且的边数，顶点数。由于m=n-1,所以，由归纳假设知，是树。 由于相当于在中为添加了一个子节点，所以G也是树。 由（1），（2）原命题得证。 4. 假设用一个的数组来描述一个有向图的邻接矩阵，完成下面工作： 1）编写一个函数以确定顶点的出度，函数的复杂性应为： 2）编写一个函数以确定图中边的数目，函数的复杂性应为 3）编写一个函数删除边，并确定代码的复杂性。 解答：（1）邻接矩阵表示为，待确定的顶点为第m个顶点 int CountVout(int *a,int n,int m){ int out = 0; for(int i=0;in;i++) if(a[m-1][i]==1) out++; return out; } （2）确定图中边的数目的函数如下： int EdgeNumber(int*a,int n){ int num =0; for(int i=0;in;i++) for(int j=0;jn;j++) if(a[i][j]==1) num++; return num; } （3）删除边（i , j）的函数如下： void deleteEdge(int *a，int i ,int j){ if(a[i-1][j-1]==0) return; a[i-1][j-1] = 0; return; } 代码的时间复杂性为Θ(1) 5.实现图的D-有哪些信誉好的足球投注网站算法，要求用SPARKS语