《图论练习题》由会员分享，可在线阅读，更多相关《图论练习题（4页珍藏版）》请在金锄头文库上搜索。
1、图论练习题一、基本题1、设G是由5个顶点构成的完全图，则从G中删去（A）边可以得到树。A6 B5 C8 D42、下面哪几种图不一定是树（A）。A无回路的连通图 B有n个结点，n-1条边的连通图C对每对结点间都有通路的图D连通但删去任意一条边则不连通的图3、5阶无向完全图的边数为（B）。A5 B10 C15 D204、设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是（ ）An/2 Bn(n+1) Cnk-2m Dn(k+1)-2m5、设G=为有向图，V=a,b,c,d,e,f，E=,是（B）。A强连通图 B单向连通图 C弱连通图 D不连通图6、在有n个结
2、点的连通图中，其边数（B）A最多有n-1条 B至少有n-1条 C最多有n条 D至少有n条7、设无向简单图的顶点个数为n，则该图最多有（C）条边。An-1 Bn(n-1)/2 C n(n+1)/2 Dn28、要连通具有n个顶点的有向图，至少需要（A ）条边。An-l Bn Cn+l D2n9、n个结点的完全有向图含有边的数目（B）。An*n n（n） Cn2 Dn*（nl）10、在一个无向图中，所有顶点的度数之和等于所有边数（B）倍。A1/2 B2 C1 D411、在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C）倍。A1/2 B2 C1 D412、连通图G是一棵树，当且仅当G中（B
3、）A有些边不是割边 B所有边都是割边 C无割边集 D每条边都不是割边13、4个顶点的完全图G，其生成树个数是（ ）。A4 B8 C16 D64二、应用题题1、判断下图是否能一笔画出，并说明理由。V0VnVnV0 图（a） 图（b）答：图a ，b 都可以 因为奇度点的个数为偶数，其余都是偶度点。题2、用Kruskal算法求下图的的最小生成树，并计算其权。ABDCFE答： 其权之和为 38。题3、求出下图中以v1为起点的一条中国邮路。题4、利用Dijkstra算法，求解下图中从顶点1到其余各点的最短路径。 题5、求下图最大流。题6、求下图的最大流。题7、利用Dijkstra算法，求下图从1出发到其余各点的最短路径。
