2004图论复习题答案

习题一作者---寒江独钓1.证明：在n 阶连通图中(1) 至少有n-1条边；(2) 如果边数大于n-1，则至少有一条闭迹；(3) 如果恰有n-1条边，则至少有一个奇度点。

证明: (1) 若G 中没有1度顶点，由握手定理：()2()21v V G m d v n m n m n ∈=≥⇒≥⇒>-∑若G 中有1度顶点u ，对G 的顶点数作数学归纳。

当n=2时，结论显然；设结论对n=k 时成立。

当n=k+1时，考虑G-u,它仍然为连通图，所以，边数≥k-1.于是G 的边数≥k.(2) 考虑G 中途径：121:n n W v v v v -→→→→L若W 是路，则长为n-1;但由于G 的边数大于n-1,因此，存在v i 与v j ,它们相异，但邻接。

于是：1i i j i v v v v +→→→→L 为G 中一闭途径，于是也就存在闭迹。

(3) 若不然，G 中顶点度数至少为2，于是由握手定理：()2()21v V G m d v n m n m n ∈=≥⇒≥⇒>-∑这与G 中恰有n-1条边矛盾！ 2.(1)2n −12n 2−12n −1 (2)2n−2−1(3) 2n−2。

证明:u 1的两个邻接点与v 1的两个邻接点状况不同。

所以，两图不同构。

4.证明下面两图同构。

u 1 v 1证明:作映射f : v i ↔ u i (i=1,2….10)容易证明，对∀v i v j ∈E ((a)),有f (v i v j,),=,u i,u j,∈,E,((b))(1≤ i ≤ 10, 1≤j ≤ 10 )由图的同构定义知，图(a)与(b)是同构的。

5.指出4个顶点的非同构的所有简单图。

分析：四个顶点的简单图最少边数为0，最多边数为6，所以可按边数进行枚举。

(a)v 2 v 3u 4u(b)6.证明:1)充分性:当G 是完全图时，每个顶点的度数都是n −1,共有n 个顶点，总的度数为n(n −1)，因此总的边数是n(n−1)2=(n 2). 2)必要性:因为G 是简单图,所以当G 是完全图的时候每个顶点的度数才达到最大:n −1.若G 不是完全图，则至少有一个顶点的度数小于n −1,这样的话，总的度数就要小于n (n −1)，因此总的边数小于(n 2)，矛盾。

数 学 试 题一、选择题：本大题共12小题，每小题5分，共60分，在每小题给出的四个选项中，只有一项是符合题目要求的。

1、若p r q p ⇒⇔,则q 是r 的（ ）条件。

A 、充分不必要条件B 、必要不充分条件C 、充要条件D 、非充分又非必要条件2、对于x ∈R ,恒有)1()1(x f x f --=+成立，则f(x)的表达式可能是( ).A 、x x f πcot )(=B 、()x x f πtan =C 、x x f πcos )(=D 、x x f πsin )(=3、已知函数1)(---=a x x a x f , f --1(x )的图象的对称中心为M （m ,3）则a+m 的值为( ).A 、1B 、2C 、-1D 、-54.(理 )设i 2321+-=ω,{}Z k x x A k k ∈+==-,ωω则集合A 中的元素个数为( ).A 、1个B 、2个C 、3个D 、无穷多个（文）集合{x S =|Z x x ∈>,161)21(}，{x T =|Z x x ∈<-,21}，则T S 中元素的个数为( )A 、1个B 、2个C 、3个D 、无穷多个5、三个平面两两垂直，有三条交线，若直线l 和这三条交线所成的角分别为γβα,,，则γβα2cos 2cos 2cos ++的值是( ).A 、2B 、23 C 、1 D 、1-6、将抛物线y 2=4x 按向量)2,1(=平移后与直线x-2y+m=0相切，则m 的值为( ).A 、-1B 、7C 、9D 、17、右图是函数1)32cos(-+=θπx A y (|θ|≤2π)的图象的一部分，则a 的值为( ).A 、2B 、25 C 、4 D 、5 8、若x,y ∈R +,且x+2y=3，则y x 11+的最小值为( ).A 、2B 、23C 、1+322 D 、3+22 9、在正四面体ABCD 中，E 为AB 中点，F 为△BCD 的中心，则EF 与BC 所成的角为( ).A 、30°B 、45°C 、60°D 、90°10、（理）若lim 2→x 434222=--+x ax x ，则a 的值为( ).A 、0B 、1C 、-1D 、21 （文）在()n x +1的展开式中,奇数项之和为A,偶数项之和为B,则()nx 21-的值为( ). A. 0 B. B A ⋅ C. 22B A - D. 22B A +11、P 为曲线1162522=+y x 上一动点，F 为右焦点，设点)2,34(A ，则3|P A |+5|PF |的最小值为( ).A 、7B 、14C 、28D 、2112、已知函数f(x)满足f(x+2)=21)2(),()(1)(1=∈-+f R x x f x f ，则f (2004)等于( ).A 、21B 、1C 、2D 、3二、填空题：本大题共4小题，每小题4分，共16分。

图论课后习题答案图论是数学中的一个分支，主要研究图的结构和性质。

图论的课后习题通常包括证明题、计算题和应用题。

下面给出一些典型的图论课后习题答案：1. 证明题：证明一个图是连通的当且仅当它的任意两个顶点都存在一条路径相连。

答案：首先定义连通图的概念：一个图是连通的，如果对于任意两个顶点，都存在一条路径将它们连接起来。

接下来，我们证明两个方向：- 如果一个图是连通的，那么对于任意两个顶点\( u \)和\( v \)，根据定义，必然存在一条路径\( P \)将它们连接起来。

- 反之，如果对于任意两个顶点\( u \)和\( v \)，都存在一条路径将它们连接起来，那么我们可以构造一个从任意顶点\( u \)出发，访问图中所有顶点的路径，这表明图是连通的。

2. 计算题：给定一个有\( n \)个顶点的完全图，计算它的边数。

答案：在完全图中，每个顶点都与其他所有顶点相连。

因此，对于一个顶点，它将与\( n-1 \)个其他顶点相连。

但是，每条边被计算了两次（因为它连接了两个顶点），所以边数应该是\( \frac{n(n-1)}{2} \)。

3. 应用题：在一个社交网络中，每个用户可以与其他人建立联系。

如果一个用户与至少一半的用户建立了联系，那么这个社交网络是连通的吗？答案：是的，这个社交网络是连通的。

假设社交网络中有\( n \)个用户，如果一个用户与至少\( \lceil \frac{n}{2} \rceil \)个用户建立了联系，那么我们可以构造一条从任意用户\( u \)到这个中心用户的路径。

由于中心用户与至少一半的用户建立了联系，我们可以继续通过这些联系到达其他用户，从而证明社交网络是连通的。

4. 证明题：证明在任何图中，边数至少是顶点数减一。

答案：考虑一个图的生成树，它是一个最小的连通子图，包含图中的所有顶点，并且没有环。

在生成树中，边数等于顶点数减一。

由于任何图都至少包含一个生成树，因此原图的边数至少与生成树的边数相同，即至少是顶点数减一。

图论及其应用习题答案图论及其应用习题答案图论是数学的一个分支，研究的是图的性质和图之间的关系。

图是由节点和边组成的，节点表示对象，边表示对象之间的关系。

图论在计算机科学、电子工程、物理学等领域有着广泛的应用。

下面是一些图论习题的解答，希望对读者有所帮助。

1. 问题：给定一个无向图G，求图中的最大连通子图的节点数。

解答：最大连通子图的节点数等于图中的连通分量个数。

连通分量是指在图中，任意两个节点之间存在路径相连。

我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历图，统计连通分量的个数。

2. 问题：给定一个有向图G，判断是否存在从节点A到节点B的路径。

解答：我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历图，查找从节点A到节点B的路径。

如果能够找到一条路径，则存在从节点A到节点B的路径；否则，不存在。

3. 问题：给定一个有向图G，判断是否存在环。

解答：我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历图，同时记录遍历过程中的访问状态。

如果在搜索过程中遇到已经访问过的节点，则存在环；否则，不存在。

4. 问题：给定一个加权无向图G，求图中的最小生成树。

解答：最小生成树是指在无向图中，选择一部分边，使得这些边连接了图中的所有节点，并且总权重最小。

我们可以使用Prim算法或Kruskal算法来求解最小生成树。

5. 问题：给定一个有向图G，求图中的拓扑排序。

解答：拓扑排序是指将有向图中的节点线性排序，使得对于任意一条有向边(u, v)，节点u在排序中出现在节点v之前。

我们可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来遍历图，同时记录节点的访问顺序，得到拓扑排序。

6. 问题：给定一个加权有向图G和两个节点A、B，求从节点A到节点B的最短路径。

解答：我们可以使用Dijkstra算法或Bellman-Ford算法来求解从节点A到节点B的最短路径。

这些算法会根据边的权重来计算最短路径。