图论练习题2009(学生练习

1、图论练习题一、基本题1、设G是由5个顶点构成的完全图，则从G中删去（ ）边可以得到树。A6 B5 C8 D42、下面哪几种图不一定是树（ ）。A无回路的连通图B有n个结点，n-1条边的连通图C对每对结点间都有通路的图D连通但删去任意一条边则不连通的图。3、5阶无向完全图的边数为（ ）。A5 B10 C15 D204、把平面分成x个区域，每两个区域都相邻，问x最大为（ ）A6 B4 C5 D35、设图G有n个结点，m条边，且G中每个结点的度数不是k，就是k+1，则G中度数为k的节点数是（ ）An/2 Bn(n+1) Cnk-2m Dn(k+1)-2m6、设G=为有向图，则有（ ）。AEV x V

2、 BEV x V CV x VE DV x V=E7、图G1和G2的结点和边分别存在一一对应关系是G1和G2同构的（ ）。A充分条件 B必要条件 C充分必要条件 D既不充分也不必要条件8、设G=为有向图，V=a,b,c,d,e,f，E=,是（ ）。A强连通图 B单向连通图 C弱连通图 D不连通图9、无向图G中的边e是G的割边（桥）的充分必要条件是（）。Ae是重边 Be不是重边 Ce不包含在G的任一简单回路中 De不包含在G的某一简单回路中10、在有n个结点的连通图中，其边数（ ）A最多有n-1条 B至少有n-1条 C最多有n条 D至少有n条11设无向简单图的顶点个数为n，则该图最多有（ ）条边

3、。An-1 Bn(n-1)/2 C n(n+1)/2 Dn212要连通具有n个顶点的有向图，至少需要（ ）条边。An-l Bn Cn+l D2n13n个结点的完全有向图含有边的数目（）。An*n n（n） Cn2 Dn*（nl）14一个有n个结点的图，最少有（ ）个连通分量。A0 B1 Cn-1 Dn15一个有n个结点的图，最多有（ ）个连通分量。A0 B1 Cn-1 Dn16在一个无向图中，所有顶点的度数之和等于所有边数（ ）倍。A1/2 B2 C1 D417在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（ ）倍。A1/2 B2 C1 D418、连通图G是一棵树，当且仅当G中（ ）

4、A有些边不是割边 B所有边都是割边 C无割边集 D每条边都不是割边194个顶点的完全图G，其生成树个数是（ ）。A4 B8 C16 D6420、设有33盏灯，拟公用一个电源，则至少需有5插头的接线板数（ ）。A7 B8 C9 D14二、应用题题1：（1996年全国数学联赛）有n（n6）个人聚会，已知每个人至少认识其中的n/2个人，而对任意的n/2个人，或者其中有两个人相互认识，或者余下的n-n/2个人中有两个人相互认识。证明这n个人中必有3个人互相认识。注：n/2表示不超过n/2的最大整数。题2：已知图的结点集V=a,b,c,d以及图G和图D的边集合分别为：E(G)=(a,a), (a,b),

5、 (b,c), (a,c)E(D)=, , , , 试作图G和图D，写出各结点的度数，回答图G、图D是简单图还是多重图？题3：设简单连通无向图G有12条边，G中有2个1度结点，2个2度结点，3个4度结点，其余结点度数为3求G中有多少个结点试作一个满足该条件的简单无向图题4：设简单连通无向图G有9条边，G中有4个3度结点，2个1度结点，其余结点度数为2求G中有多少个结点题5：两个图同构有下列必要条件：（1） 结点数相同；（2） 边数相同；（3） 度数相同的结点数相同.但它们不是两个图同构的充分条件，下图中(a)和(b)满足上述三个条件，但这两个图并不同构，请说明理由。(a)(b)题6：三名商人各

6、带一随从乘船过河，一只小船只能容纳2人，由他们自己划行。随从们密约，在河的任一案，一旦随从的人数比商人多，就杀人越货。但是如何乘船渡河的大权掌握在商人手中，商人们怎样安排每次乘船方案才能安全渡河？题7在平面上有n个点Sx1,x2,xn，其中任两个点之间的距离至少是1，证明在这n个点中距离为1的点对数不超过3n。题8n个点由若干线段连接着。已知每一点与另外任何一点都有道路相连通。而任何两点都没有两种不同的道路。证明：线段总数为n-1。题9：设无向图G有12条边，已知G中度数为3的节点个数为6个，其余结点的度数均小于3，问G中至少有多少边？题10：若图G是不连通的，则G的补图是连通的。题11：当且

7、仅当G的一条边e不包含在G的回路中，e才是G的割边（桥）。题12：n个城市由k条公路网络连接（一条公路定义为两个城市间的一条道路，它们之间不能通过任何中间城市），证明：如果有k(n-1)(n-2)则人们总能通过连接城市的公路在任何城市间旅行。题13：判断下图是否能一笔画出，并说明理由。V0VnVnV0 图（a） 图（b）题14：构造一个欧拉图，其结点数n与边数m满足下列条件 （1）、n，m的奇偶性一样的简单图。 （2）、n，m的奇偶性相反的简单图。 如果不可能，请说明原因。题15：设G是一个具有n个结点的简单无向图，n3，设G的结点表示n个人，G的边表示他们间的友好关系，若两个结点杯一条边连接

8、，当且仅当对应的人是朋友。（1）、结点的度数能做怎样的解释？（2）、G是连通图能做怎样的解释？（3）、假定任意两个人合起来认识所留下的n-2个人，证明n个人能站成一排，使得中间每个人两旁站着自己的朋友，而两端的两个人，他们每个人旁边只站着他的一个朋友。（4）、证明对于n4，（3）中保证n个人能站成一圈，使每个人的两旁站着自己的朋友。题16：设G是有11个或更多结点的图，证明G或（补图）是非平面图。题17：一棵树有n2个结点度数为2，n3个结点度数为3，nk个结点度数为k，问它有几个度数为1的结点。题18：证明在完全二叉树中，边的总数m等于2(nt-1)，nt是树叶总数。题19：给设d=（d1,

9、d2,dn），其中di为正数，i=1,2, ,n。若存在n个结点的简单图，使得结点vi的度数为di，则称d是可图解的。下面给出的各序列中哪些是可图解的，哪些不是，为什么？（1）、（1，1，1，2，3） （2）、（0，1，1，2，3，3） （3）、（3，3，3，3）（4）、（2，3，3，4，4，5） （5）、（2，3，4，4，5） （6）、（2，3，3，3）（7）、（2，3，3，4，5，6） （8）、（1，3，3，4，5，6，6） （9）、（2，2，4）（10）、（1，2，2，3，4，5）题20：给无向完全图Kn（n7）的各边随意涂上红色或绿色，若已知从某个结点v0引出的n-1条边中至少有六条边

10、涂红色，则存在红色的K4或绿色的K3。题21：证明：在任何两个或两个以上人的组内，存在两个人在组内有相同个数的朋友。题22、设G为n个结点的简单无向图。（1）、若G的边数m=(1/2)(n-1)(n-2)+2，证明G是哈密尔顿图。（2）、若G的边数m=(1/2)(n-1)(n-2)+1，那么图G是否一定为哈密尔顿图？请阐述你的理由。题23、把平面分成x个区域，每两个区域都相邻，问x最大为几？题24、设图G有n个结点，m条边，其中有nk个结点的度数为k，其余结点的度数均为k+1，试证明：nk=(k+1)n-2m。题25、用Kruskal算法求下图的的最小生成树，并计算其权。题26、求出下图中以v1为起点的一条中国邮路。题27、利用Dijkstra算法，求解下图中从顶点1到其余各点的最短路径题28、求下面PERT图的关键路径。题29、利用Huffman算法，求权为20,30,50,70,80的最优二叉树T，并求出其W(T)。 W(T)=550。题30：给定权1，4，9，16，25，36，49，64，81，100，利用Huffman算法构造一棵最优二叉树，并求出其W(T)。题31、用Dinic算法求下图最大流。题32、用2F标号算法求下图的最大流。题33、用匈牙利算法求下图的最大匹配。题34、对下图顶