图论练习题
一、基本题
1、设G是由5个顶点构成的完全图,则从G中删去( )边可以得到树。 A.6 B.5 C.8 D.4
2、下面哪几种图不一定是树( )。
A.无回路的连通图
C.对每对结点间都有通路的图
D.连通但删去任意一条边则不连通的图。
3、5阶无向完全图的边数为( )。
A.5 B.10 C.15 D.20
4、把平面分成x个区域,每两个区域都相邻,问x最大为( )
A.6 B.4 C.5 D.3
5、设图G有n个结点,m条边,且G中每个结点的度数不是k,就是k+1,则G中度数为k的节点数是( ) A.n/2 B.n(n+1) C.nk-2m D.n(k+1)-2m
6、设G=<V,E>为有向图,则有( )。
A.EV x V B.EV x V C.V x VE D.V x V=E
7、图G1和G2的结点和边分别存在一一对应关系是G1和G2同构的( )。
A.充分条件 B.必要条件 C.充分必要条件 D.既不充分也不必要条件
8、设G=<V,E>为有向图,V={a,b,c,d,e,f},E={<a,b>,<b,c>,<a,d>,<d,e>,<f,e>}是( )。
A.强连通图 B.单向连通图 C.弱连通图 D.不连通图
9、无向图G中的边e是G的割边(桥)的充分必要条件是()。
A.e是重边 B.e不是重边
C.e不包含在G的任一简单回路中 D.e不包含在G的某一简单回路中
10、在有n个结点的连通图中,其边数( )
A.最多有n-1条 B.至少有n-1条 C.最多有n条 D.至少有n条
11.设无向简单图的顶点个数为n,则该图最多有( )条边。
A.n-1 B.n(n-1)/2 C. n(n+1)/2 D.n2
12.要连通具有n个顶点的有向图,至少需要( )条边。
A.n-l B.n C.n+l D.2n
13.n个结点的完全有向图含有边的数目( )。
A.n*n B.n(n+1) C.n/2 D.n*(n-l)
14.一个有n汉译英个结点的图,最少有( )个连通分量。
A.0 B.1 C.n-1 D.n
15.一个有n个结点的图,最多有( )个连通分量。
A.0 B.1 C.n-1 D.n
16.在一个无向图中,所有顶点的度数之和等于所有边数( )倍。
A.1/2 B.2 C.1 D.4
17.在一个有向图中,所有顶点的入度之和等于所有顶点出度之和的( )倍。
A.1/2 B.2 C.1 D.4
18、连通图G是一棵树,当且仅当G中( )
A.有些边不是割边 B.所有边都是割边
C.无割边集 D.每条边都不是割边
19.4个顶点的完全图G,其生成树个数是( )。
A.4 B.8 C.16 D.64
20、设有33盏灯,拟公用一个电源,则至少需有5插头的接线板数( )。
A.7 B.8 C.9 D.14
二、应用题
题1:(1996年全国数学联赛)
有n(n6)个人聚会,已知每个人至少认识其中的[n/2]个人,而对任意的[n/2]个人,或者其中有两个人相互认识,或者余下的n-[n/2]个人中有两个人相互认识。证明这nmrpk个人中必有3个人互相认识。注:[n/2]表示不超过n/2的最大整数。
题2:已知图的结点集V={a,b,c,d}以及图G和图D的边集合分别为:
E(G)={(a,a), (a,b), (b,c), (a,c)}
E(D)={<a,b>, <a,c>, <c,d>, <c,a>, <c,b>}
试作图G和图D,写出各结点的度数,回答图G、图D是简单图还是多重图?
题3:设简单连通无向图G有12条边,G中有2个1度结点,2个2度结点,3个4度结点,其余结点度数为3.求G中有多少个结点.试作一个满足该条件的简单无向图.
题4:porand设简单连通无向图G有9条边,G中有4个3度结点,2个1度结点,其余结点度数为2.求G中有多少个结点.
题5:两个图同构有下列必要条件:
(1) 结点数相同;
(2) 边数相同;
(3) 度数相同的结点数相同.
但它们不是两个图同构的充分条件,下图中(a)和(b)满足上述三个条件,但这两个图并不同构,请说明理由。 题6:三名商人各带一随从乘船过河,一只小船只能容纳2人,由他们自己划行。随从们密约,在河的任一案,一旦随从的人数比商人多,就杀人越货。但是如何乘船渡河的大权掌握在商人手中,商人们怎样安排每次乘船方案才能安全渡河?
题7 在平面上有n个点S={x1,x2,……,xn},其中任两个点之间的距离至少是1,证明在这n个点中距离为1的点对数不超过3n。
题8 n个点由若干线段连接着。已知每一点与另外任何一点都有道路相连通。而任何两点都没有两种不同的道路。证明:线段总数为n-1。
题9:设无向图G有12条边,已知G中度数为3的节点个数为6个,其余结点的度数均小于3,问G中至少有多少边?
题10:若图G是不连通的,则G的补图是连通的。
题11:当且仅当G的一条边e不包含在G的回路中,e才是G的割边(桥)。
题12:n个城市由k条公路网络连接(一条公路定义为两个城市间的一条道路,它们之间不能通过任何中间城市),证明:如果有
k> (n-1)(n-2)
则人们总能通过连接城市的公路在任何城市间旅行。
题13:判断下图是否能一笔画出,并说明理由。
图(a) 图(b)
题14:构造一个欧拉图,其结点数n与边数m满足下列条件
(1)、n,m的奇偶性一样的简单图。
(2)、n,m的奇偶性相反的简单图。
如果不可能,请说明原因。
题15:设G是一个具有n个结点的简单无向图,n3,设G的结点表示n个人,G的边表示他们间的友好关系,若两个结点杯一条边连接,当且仅当对应的人是朋友。
(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,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(n≥7)的各边随意涂上红或绿,若已知从某个结点v0引出的n-1条边中至少有六条边涂红,则存在红的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汉末三国、对下图顶点进行着。
题35:、利用Dijkstra算法,求下图从1出发到其余各点的最短路径。
题36、现有4名教师:张、王、李、赵,要求他们去教四门课程:数学、物理、电工和计算机科学。已知张老师能教数学和计算机科学,王老师能教物理和电工,李老师能教数学、物理和电工,而赵老师只能教电工。如何安排才能使4位教师都能教课,并且每门课都有人教,共有几种方案?