当前位置：文档之家 › 图论进阶几道题

图论进阶几道题

  • 格式：doc
  • 大小：48.00 KB
  • 文档页数：5

图论进阶几道题（最短路+最小生成树部分）-hjl收集整理
1.
时间：1s
空间：128M
题目描述
已知一个无向图，选择n-1条边，使得每两点之间可以互相到达（答案保证
有解），求n-1条边的权值和最小是多少？

输入格式
第一行两个整数n，m。表示图的的结点数和边数。(n≤100，m≤10000)。
接下来的m行每行描述了一个边的状况，包含三个整数（U,V,W）,W表
示该边的权值且大于等于0.

输出格式
一个整数，表示最小值。
输入样例
3 3
1 2 1
2 3 1
1 3 5

输出样例
2

2.
时间：1s
空间：128M
题目描述：
随着ls校园网的壮大，管理员的数目也越来越多，现在你身为管理层的联络员，
希望你找到一些通信渠道，使得管理员两两都可以联络（直接或者是间接都可
以）。你要尽可能的使费用少才可以。
目前你已经知道，网站通信渠道分为两大类，一类是必选通信渠道，无论价

源文件 shu1.pas/exe shu2.pas/exe travel.pas/exe island.pas/exe
输入文件 Shu1.in Shu2.in Travel.in Island.in
输出文件 Shu1.out Shu2.out Travel.out Island.out
时限 1s 1s 2s 1s
空限 128M 128M 128M 128M
格多少，你都需要把所有的都选择上；还有一类是选择性的通信渠道，你可以从
中挑选一些作为最终管理员联络的通信渠道。数据保证给出的通行渠道可以让所
有的管理员联通。
输入格式
第一行n，m表示一共有n个管理员，有m个通信渠道
第二行到m+1行，每行四个非负整数，p,u,v,w 当p=1时，表示这个通信渠道为
必选通信渠道；当p=2时，表示这个通信渠道为选择性通信渠道；u,v,w表示本
条信息描述的是u，v管理员之间的通信渠道，u可以收到v的信息，v也可以收
到u的信息，w表示费用。
输出格式最小的通信费用

样例输入
5 6
1 1 2 1
1 2 3 1
1 3 4 1
1 4 1 1
2 2 5 10
2 2 5 5

样例输出
9

数据范围和注释
样例解释：
1-2-3-4-1存在四个必选渠道，形成一个环，互相可以到达。需要让所有管理员联
通，需要联通2和5号管理员，选择费用为5的渠道，所以总的费用为9

注意：
U,v之间可能存在多条通信渠道，你的程序应该累加所有u,v之间的必选通行渠
道

数据范围：
对于30%的数据，n<=10 m<=100
对于50%的数据, n<=200 m<=1000
对于100%的数据，n<=2000 m<=10000

3.
时间：2s

空间：128M
题目描述
wxc突发奇想，要去G地，于是他搞来了一张地图，看怎么走才好。
地图上有很多城市，G地也是一座城市。每两座城市之间都可能有直达方法，也
有可能两座城市之间并不能直接相通，而要通过其他的城市转达。对于两个城市
之间的直达方法，需要一定的时间，当然，如果从A城市到B城市的直达方法
需要T时间，那么从B城市到A城市的直达方法也是T时间。
wxc想要用最短的时间到达G地，但是有个问题，他发现，地图上有些
城市对他很有吸引力。所以他要在经过这些城市的基础上时间最短。
wxc已经用1、2、3、4、5……n标记了他可能经过的城市（1代表出发
地，n代表G地），但是眼花缭乱的地图让他感到烦恼。他请你来解决这个问题，
告诉他最小需要多少时间到达G地。
输入格式
输入文件的第一行是三个正整数n和m，t，n表示总共有多少个城市（包括
出发地和G地），城市数不会超过200个；m是城市的直达路线数
（1<=m<=20000），t表示一定去的城市数0<=t<=10（不包括出发地和G地）。
接下来一行有t个整数，表示一定要去的城市。
接下来m行，每行包含三个正整数，前两个数表示分别代表一个城市，第
三个数是这两个城市之间的直达时间。直达时间不会超过1000000。
输出格式
输出一个数，题目要求的得最短时间。
输入样例
travel.in
5 10 2
2 3
1 2 5
1 3 45
1 4 61
1 5 81
2 3 9
2 4 91
2 5 4
3 4 74
3 5 42
4 5 61
输出样例
travel.out
27

4.问题描述
时间：1s
空间：128M
话说yzy阴差阳错地来到了神秘岛。不久，他们发现，这是一个由n个小岛
和一个中心岛组成的群岛，群岛之间有m座桥。令他们感到惊讶的是，这些桥
并不是固定不变的，经较长时间的观察，发现它们会随时间作周期性的变化（即
桥的两端会不断更换）。
yzy很早就留意到远远的那个中心岛了。他们发现岛的上空好像有一个很巨
大的东西，但实在太远了，看不清楚。此时他们得意地从身上拿出一个超高倍数
望远镜，好像很自豪的样子，因为他们平时专门用来看美女的工具此时终于派得
上用场了。
“那是一间小屋！架在一棵好大好大的树上！”
“yzy！我们也许可以暂时在那安顿，好用来遮风避雨！”
于是他们便决定前往中心岛上的那间空中楼阁。yzy的懒惰是出了名的，他
们当然希望越早到越好，那么，你能帮帮他们吗？
为方便计算，yzy把小岛按1..n编号，0表示中心岛。yzy一开始在编号为
1的小岛上。在岛上行走的时间忽略不计，过桥的时间为1个单位。岛上的桥变
化的周期为T，在nT+i(n=0,1,2,„;i=1,2,„,T)时刻岛上的桥为第i种状态，
一开始的时刻为1。两个小岛间可能有多条桥相连。在任一时刻，yzy可以选择
过桥，也可以原地不动。当然，如果无桥可过，yzy只能在原地等待。

输入格式
输入文件island.in的第一行包括三个整数n（1<=n<=80），m(1<=m<=10000)
和T(1<=T<=10)，分别表示小岛的个数，岛上桥的数量和桥改变的周期T。
接下来分别描述第1..T种状态，每种状态有m行，每行有两个整数a, b
（0<=a,b<=n），表示这种状态时小岛a和b有一条桥相连。两状态之间用一空
行隔开。
输出格式
输出文件island.out仅有一个整数，表示yzy最少得花多少时间到达中心岛。
如果yzy无法到达中心岛，则输出“Poor yzy!”。

输入样例1
4 5 2
1 2
1 3
1 4
2 0
4 0

1 3
1 3
2 3
4 3
3 0
输出样例1
2

输入样例2
7 3 2
1 2
1 4
6 0

2 5
3 6
4 7

输出样例2
Poor yzy!

HINT（良心提示…大神无视…）
1,2最小生成树
3,4最短路

合集下载

图论 三四章习题

图论 三四章习题

v G
G1的度序列为： (d1+1,d2+1,…,dn+1, n) 由条件：不存在小于(n+1)/2的正整数m,使得dm+1≦m,且 d(n+1)-m <(n+1)-m。于是由度序列判定定理知：G1是H图，得 G有H路。
G1Leabharlann 613.证明：若G不是H图，则G度弱于某个 Cm1 ,n ， 且有
v m1 2
3
32. （1）证明：考虑G=Cn˅H 的最小点割V。根据联图的定义， 则必有V包含Cn 或者H，否则G-V后一定连通。如果Cn ∈V，则 由H是K连通的可知|V|=n+k。若H ∈V，则V中至少还需要包含Cn 中两个不相邻的顶点，也可得|V|=n+k。故G是n+k连通的。 （2）在Cn 上任取相邻的两点x,y，设这两个点在Cn上的两条路分 别为P1和P2。考虑宽为n+k的x-y容器，因为H仅包含n+k-2个点， 经过H中的点，且独立的（x，y）路最多有n+k-2个，且每条路的 长度都为2。因此在每个容器中必包含P1和P2。故dn+k(x,y)=n-1。
1. 证明方法与p. 47 定理3类似
3. 设无环图G是阶数大于2的连通图，则下列命题等价 （1）G是块，即G是2-连通的； （2）G的任意两个顶点在某个圈上； （3）G的任一个顶点和任一条边在某个圈上； （4）G的任意两边在某个圈上； （5）G的任意两个顶点u，v及任一边e，总存在连接u，v 且过e的路； （6）G的任意三个顶点，总存在连接其中任意两个顶点， 并且通过第三个顶点的路 （7）G的任意三个顶点，总存在连接其中任意两个顶点， 并且不过第三个顶点的路 证明：1 2 2：p.48 定理4 3：令u是任一顶点，vw是任一边，由（2），存在
《图论》练习题201410

《图论》练习题201410

《图论》练习题(2014)1、利用Dijkstra 算法求下图中顶点0v 到其它各顶点的距离，并写出到顶点8v 的最短路。

2、1、列出色数3为的三个图： 。

2、p 阶完全图的色数为： 。

3、p 阶树的邻接多项式为： 。

4、p 阶完全图的邻接多项式为： 。

5、如下图所示的图的邻接矩阵为 ，关联矩阵为 。

6、度序列为(2,2,2,2,2,2)的简单图是 。

7、是否存在度序列为(2,2,3,4,5,6)，(1,2,3,4,4,5)的简单图？若存在，给出一个图；若不存在，请说明理由。

8、画出如下图的所有生成子图。

9、设图G 如下图所示，求该图的生成树个数)(G 。

v 2v 6v 4v 610、已知图G （V 、E ），画出G －V 5，G －v 3v 4，G[{v 2，v 3，v 5}]，G[{v 3v 4，v 4，v 6，v 7v 8}]G ：11、已知图G 的邻接矩阵⎪⎪⎪⎪⎪⎭⎫ ⎝⎛=2111102112011111A ，画出G ，并求出度序列。

12、证明：偶图G 的任意子图H 仍为偶图。

13、证明：设图G （V 、E ）的度序列为（p d d d ,,,21 ），边数为q ，则q i d pi 21==∑14、证明：在任何图中，奇顶点个数为偶数。

15、证明：整数序列（6，6，5，4，3，3，1）不可能为一个简单图的图序列。

16、证明顶点度数均为2的简单连通图是圈。

17、证明非平凡树T 的边连通度为'()1T κ=。

18、n 阶完全图n K 的连通度为()1T n κ=-。

19、设G 是一个p 阶图，且()()21,-≥∈∀p v d G V v ，则G 连通图。

20、若图G 是 不连通的，则其补图G C 是连通的。

21、证明：设G 是由1G 和2G 两个连通分支组成的图，则);();();(21x G P x G P x G P =。

v 1v 2v 3v 4v 5v 6v 8v 722、证明：设G 是由1G 和2G 两个连通分支组成的图，则)}(),(max{)(21G G G χχχ=。

图论试题及答案解析图片

图论试题及答案解析图片

图论试题及答案解析图片一、选择题1. 图论中，图的基本元素是什么？A. 点和线B. 点和面C. 线和面D. 点和边答案：A2. 在无向图中，如果两个顶点之间存在一条边，则称这两个顶点是：A. 相邻的B. 相连的C. 相等的D. 相异的答案：A3. 在有向图中，如果从顶点A到顶点B有一条有向边，则称顶点A是顶点B的：A. 父顶点B. 子顶点C. 邻接顶点D. 非邻接顶点答案：B4. 一个图的度是指：A. 图中顶点的总数B. 图中边的总数C. 一个顶点的边数D. 图的连通性答案：C5. 一个图是连通的，当且仅当：A. 图中任意两个顶点都是相邻的B. 图中任意两个顶点都可以通过边相连C. 图中任意两个顶点都可以通过路径相连D. 图中任意两个顶点都可以通过子顶点相连答案：C二、填空题1. 在图论中，一个顶点的度数是该顶点的________。

答案：边数2. 如果一个图的任意两个顶点都可以通过边相连，则称该图为________。

答案：完全图3. 一个图中，如果存在一个顶点到其他所有顶点都有边相连，则称该顶点为________。

答案：中心顶点4. 图论中，最短路径问题是指在图中找到两个顶点之间的________。

答案：最短路径5. 如果一个图的任意两个顶点都可以通过有向路径相连，则称该图为________。

答案：强连通图三、简答题1. 请简述图论中的欧拉路径和哈密顿路径的定义。

答案：欧拉路径是指在图中经过每条边恰好一次的路径，而哈密顿路径是指在图中经过每个顶点恰好一次的路径。

2. 什么是图的着色问题？答案：图的着色问题是指将图中的顶点用不同的颜色进行标记，使得相邻的两个顶点颜色不同。

四、计算题1. 给定一个无向图G，顶点集为{A, B, C, D, E}，边集为{AB, BC, CD, DE, EA}，请画出该图，并计算其最小生成树的权重。

答案：首先画出图G的示意图，然后使用克鲁斯卡尔算法或普里姆算法计算最小生成树的权重。

图论部分复习题

图论部分复习题

已知无向图g有12条边6个3度顶点其余顶点的度数均小于3问g至少有几个顶点
已知无向图G 12条边 条边， 度顶点， 1. 已知无向图G有12条边，6个3度顶点，其余顶点的度数均 小于3 至少有几个顶点？ 小于3，问G至少有几个顶点？并画出满足条件的一个图 形. 阶无向图中， 度顶点的个数分别是1 2. 7阶无向图中，2度，3度，4度，5度顶点的个数分别是1、 1.求图 的边数.试画出满足条件的一个图形. 求图G 3、2、1.求图G的边数.试画出满足条件的一个图形. 是否存在7 无向简单图G 其度序列为1 3. 是否存在7阶无向简单图G，其度序列为1、3、3、4、6、 7.给出相应证明 给出相应证明. 6、7.给出相应证明. 个互不相同的正整数. 4. 设d1、d2、…、dn为n个互不相同的正整数. 、 证明：不存在以d 证明：不存在以d1、d2、…、dn为度序列的无向简单图. 、 为度序列的无向简单图. a 求右图的补图. 5. 求右图的补图. e d 6. 试画出一个自补图 图和其补图同构). (图和其补图同构). 给定整数序列是否构成无向图的度序列并说明原因。 7. 给定整数序2 2 8 7 5 1 3 3 4 2 8
8. 写出右图的一个生成子图。 ={m,s,z,b}的导出子图 的导出子图G[V 求V1={m,s,z,b}的导出子图G[V1]。 9. 10. 11. 12. 一个图和它的补图有什么联系？ 一个图和它的补图有什么联系？ 完全图的定义是什么？ 完全图的定义是什么？ 求右图割点和割边 Z 判断是否构成格， 判断是否构成格，并说明原因 a b c e d M B C
Q
S f d e b a
L
Z
c
试写出模6加法群<Z 13. 试写出模6加法群<Z6，+6>的每个子群及其相应的左陪集 14. 写出代数系统、半群、独异点、群、环、域的概念。 写出代数系统、半群、独异点、 域的概念。