图论应用案例

题目：最小生成树在城市交通建设中的应用

姓名：

学号：

指导老师：

专业：机械工程

2014年3月16

目录

摘要..................................................................................... 错误！未定义书签。

1 绪论 (1)

2 有关最小生成树的概念 (2)

3 prim算法介绍 (3)

4 系统设计及其应用 (5)

一、系统设计 (5)

二、最小生成树应用 (8)

5 总结 (11)

参考文献 (12)

附件： (13)

最小生成树在城市交通建设中的应用

摘要：连通图广泛应用于交通建设，求连通图的最小生成树是最主要的应用。比如要在n个城市间建立通信联络网，要考虑的是如何保证n点连通的前提下最节省经费，就应用到了最小生成树。

求图的最小生成树有两种算法，一种是Prim（普里姆）算法，另一种是Kruskal（克鲁斯卡尔）算法。

本文通过将城市各地点转换成连通图，再将连通图转换成邻接矩阵。在Microsoft Visual C++上，通过输入结点和权值，用普里姆算法获得权值最小边来得到最小生成树，从而在保证各个地点之间能连通的情况下节省所需费用。

本文从分析课题的题目背景、题目意义、题目要求等出发，分别从需求分析、总体设计、详细设计、测试等各个方面详细介绍了系统的设计与实现过程，最后对系统的完成情况进行了总结。

关键字：PRIM算法、最小生成树、邻接矩阵、交通建设

Abstract

Connected graph is widely applied in traffic construction, connected graph of minimum spanning tree is the main application.Such as to establish a communication network between the n city, want to consider is how to ensure n points connected under the premise of the most save money, apply to the minimum spanning tree.

O figure there are two kinds of minimum spanning tree algorithm, one kind is Prim (she) algorithm, the other is a Kruskal algorithm (Kruskal).

In this article, through the city around point into a connected graph, then connected graph is transformed into adjacency matrix.On Microsoft Visual c + +, through the input nodes and the weights, gain weight minimum edge using she algorithm to get minimum spanning tree, which in the case of guarantee every location between connected to save costs.

Based on the analysis topic subject background, significance, subject requirements, etc, from requirements analysis, general design, detailed design, testing, and other aspects detailed introduces the system design and implementation process, finally the completion of the system are summarized.

Key words: PRIM algorithm, minimum spanning tree, adjacency matrix, traffic construction

1绪论

中国国际工程咨询公司交通业务部主任周晓勤指出，“以前的各专业规划主要是按照本行业交通发展的需求进行研究和规划的，在交通设施总量不足、基本网不完善的时候，互相之间的矛盾并不突出。但随着多种运输方式设施建设的快速发展，各行业交通网络的逐步完善，多种运输方式网络之间的叠加，难免显现出各种运输方式在通道和枢纽衔接上的不协调。其结果是，资源浪费，效率低下，使用不便利。而综合交通网发展规划的颁布有利于运输整体结构的调整，资源节约和集约利用，对于交通运输业的可持续发展具有重要和深远的意义。”

在社会主义建设时期，各个城市建设问题尤其是交通建设尤为重要。在保证各个城市能互相连通的情况下，怎么保证建设公路，怎么建设最省钱是建设工程公司所需考虑的重大情况。从而能节省更多的钱来投资其他地方建设，如农村交通建设。

各个农村交通建设好之后，则可再根据将农村作为一个结点和其它农村再次运用最小生成树。

最小生成树则能有效的解决此问题。例如，以尽可能低的总价建设若干条高速公路，把n个城市联系在一起。

普里姆算法通过寻找无向图中权值最小的边，并且将其组合成最小生成树，同时将最小生成树以点集的形式输出，便于观察。

根据课程设计任务书要求，本系统开发主要完成以下功能和性

能。

(1) 输入无向图的方式要尽量简单方便。 (2) 要能够形象方便的观察无向图的结构。

(3) 要能够形象地演示PRIM 算法求最小生成树的过程。 本文第二章主要介绍图和最小生成树、邻接矩阵等概念。第三章主要介绍prim 算法。第四章进行系统设计与调试及其在交通建设中的应用。

2 有关最小生成树的概念

最小生成树：连通加权图里权和最小的生成树称为最小生成树。 从最小生成树定义看主要先了解图、树及生成树。本文中最小生成树在计算机中存储方法是应用邻接矩阵的形式存储。故也应了解邻接矩阵的定义。

定义一（图）：图是有一个非空的顶点集合和一个描述顶点之间的关系即边的集合组成。它可以形式化的定义为： G=(V ,E)

V={ i V | j V VertexType}

E={|i V ,j V ∈V ∧P (i V ,j V ) }

其中，G 表示一个图，V 是图G 中顶点的集合，E 是V 中顶点偶对的有限集，这些顶点偶对称为边，VertexType 是用于描述顶点类型，集合E 中P (i V ,j V )的含义是：对有向图来说用“<>”表示，对无向图来说用“（）”表示，即从i V 到 j V 两个顶点之间存在边。

定义二（树）：树包含n （n>=0）个节点。当n=0时表示为空树。其定义如下： T=(D,R)

其中，D 为树中节点的有限集合，关系R 满足一下条件：

1） 有且仅有一个节点k0属于D ，它对于关系R 来说没有前趋节点，结点k0称作树的根结

点。

2）除根结点k0之外，D中的每个结点仅有一个前趋结点，但可以有过个后继结点。

3）D中可以有多个终端结点。

即除根结点无父结点，其余各结点都有一个父结点和n（n>=0）个子结点。

图的矩阵表示，本文中只用到了邻接矩阵，故在这只提出邻接矩阵的定义，及其图在邻接矩阵中的表示。

设图A = (V, E)是一个有n 个顶点的图, 图的邻接矩阵是一个二维数组A.edge[n][n]，用来存放顶点的信息和边或弧的信息。

定义三（邻接矩阵（Adjacency Matrix））：是表示顶点之间相邻关系的矩阵。设G=(V,E)是一个图，其中V={v1,v2,…,vn}。G的邻接矩阵是一个具有下列性质的n阶方阵：（本文主要为无向图的邻接矩阵）

（1）无向图的邻接矩阵是对称的;有向图的邻接矩阵可能是不对称的。

（1）无向图的邻接矩阵中第i行第j列表示i结点到j结点的度即权值，可以表示为某一具体应用的数据。也表示i结点是否与j结点连通。

定义四（生成树）：如果T是G的一个生成子图又是一棵树，则称T是图G的一棵生成树。

3 prim算法介绍

最小生成树的两个著名算法：prim算法[和克鲁斯卡尔算法[2] ,本文应用的是prim算法。则克鲁斯卡尔算法则不进行描述了。

Prim算法的基本思想：首先，选择带最小的边，把它放进生成树里，相继添加带权最小的边，这些边与已在树立的顶点相关联，并且不与已在数理的边形成圈，当已经添加了n-1条边为止。

PRIM算法介绍：设图中顶点的全集为V, U中存放已选中过的点,用数据结构closedge[]存放选择需要的数据,先把下标0对应点放入U中, closedge[i].uxiabiao=0,(因为U中只有下标0这一个点), closedge[i].lowcost中存放其他点到下标为0的点的权,closedge[0].lowcost=0;表示下标为0的点已在U中了。在closedge按顺序找到最先不在U中,且与U中点直接相连的点,把此边的权赋给min，用擂台式比较法选出closedge[j].lowcost中最小的,此时min中存放的是最小值所在下标,也就是下一个要放入U中的点的下标。输出选中的这条边，它是最小生成树中的一条边。因为U中又加入了一个点，所以要修改closedge[i].lowcost的值，比较新选中点与V-U中点的权和原来的closedge[i].lowcost,取小的那个存入。然后继续如上的选择,循环vexnum-1次,就选出了最小生成树中的vexnum-1条边。本程序采用数组存储结构进行存储，把第一个点所到的边记录下来，然后把权值最小的边存入数组，同时将刚才所存边的的终点作为起点再次记录该点所到的边，并记录权值最小的边存入数组，这个过程中，已经被访问的点不再访问。知道

最后所有的权值最小的边全部输出。这就是PRIM算法求最小生成树。

Prim算法有两种形式，其伪代码如下：

算法一：

procedure Prim;

begin

T:=Φ；

U:={1};

while U<>V do

begin

(u,v):= u∈U且v∈V-U的最小权边;

T:=T∪{(u,v)};

U:=U∪{v};

end;

end;

改进的prim算法2如下：

procedure Prim(var G:adj_matrix;size:integer);{G为图，size为图的节点数目;注意：假设输入的图是连通图}

var

lowcost:array [1..maxsize] of integer;

used:array [1..maxsize] of boolean;

closeset:array[1..maxsize] of integer;

i,j,k,min:integer;

begin

for i:=2 to size do {初始化，此时U只含有顶点1}

begin

lowcost[i]:= G[1,i];

closeset[i]:=1;

used[i]:=false;

end;

used[1]:=true;

for i:=2 to size do

begin

min:=maxint;

j:=i;

for k:=2 to size do {用选择法寻找顶点分别在V-U与U中权最小的边}

if (not used[k])and(lowcost[k] begin

min:=lowcost[k];

j:=k;

end;

writeln(fout,'(',closeset[j],',',j,')'); {输出找到的最小生成树的一条边，此处可根据情况修改}

used[j]:=true; {将j填加到U}

for k:=2 to size do {调整lowcost和closeset}

if (not used[k])and(G[j,k] begin

lowcost[k]:=G[j,k];

closeset[k]:=j;

end;

end;

end;

4 系统设计及其应用

一、系统设计

数据信息以结构体【3】【4】和数组形式储存，结点的信息结构体定义如下：

struct graph

{

char tnode;

char hnode;

double quanzhi;

}gr[100];

char node[50]=" ";

图的存储结构为：

#define INFINITY INT_MAX //最大值

#define MAX_VERTEX_NUM 20 //最多的顶点个数

typedef enum{DG,DN,UDG,UDN} GraphKind;

//{有向图、有向网、无向图、无向网} typedef struct ArcCell{

VRType adj; //顶点关系类型：图：0、1 网：权值

InfoType *info;//该弧相关信息指针

}ArcCell,AdjMaTrix[MAX_VERTEX_NUM] [MAX_VERTEX_NUM];

typedef struct{

VertexType vexs[MAX_VERTEX_NUM];//顶点向量

AdjMaxtrix arcs; //邻接矩阵

int vexnum,arcnum; //顶点数和弧或边数

GraphKind kind; //图的种类标志

}Mgraph;

Prim算法：

void prim(mgraph g,int k,int n) //核心算法Prim算法实现函数

{

int i,j,min,p; //定义整型变量i,j用于循环 min和p分别用于临时存放最小权值及其下标

struct //定义型类型数据closedge[]用于临时存放

下标和最小边

{

int adjvex;

int lowcost;

}closedge[100];

for(i=1;i<=n;i++) //初始化辅助数组

if(i!=k)

{

closedge[i].adjvex=k;

closedge[i].lowcost=g.v[k][i];

}

closedge[k].lowcost=0; //将节点加入生成树中

for(i=1;i

{

p=1; //初始化p

min=maxvalue; //初始化最小权值

for(j=1;j<=n;j++) //循环n次比较最小权值

if(closedge[j].lowcost!=0&&closedge[j].lowcost

{

min=closedge[j].lowcost; //替换最小权值为当前节点的权值

p=j; //记录该节点下标

}

printf("%d_ _%d\n",closedge[p].adjvex,p,min); //打印最小的权值的下标和最小边

closedge[p].lowcost=0; //将该节点加入生成树中

for(j=1;j<=n;j++) //刷新临时存放空间

if((g.v[p][j]) < (closedge[j].lowcost))

{

closedge[j].lowcost=g.v[p][j]; //赋值最小边

closedge[j].adjvex=p; //赋值最小边对应下标

}

}

二、最小生成树应用

C编写的程序测试【5】数据：假设如图

结果应该如下

程序运行如图：

5 总结

该算法循序渐进，通过数组的灵活应用，构造无向连通图并最终轻松实现了生产最小生成树的目的。实验表明最小生成树能具体应用到交通建设上去。这个程序还有待开发，将其运用到交通建设上，能起到节约资源和时间的作用，并且也是交通建设发展必要的工具。

参考文献

【1】《数据结构与算法教程》第二版，李春葆等，清华大学出版社。【2】《图论及其算法》，殷剑宏等，中国科学技术大学出版社。

【3】《C语言程序设计》(第三版)，谭浩强，清华大学出版社。

【4】《数据结构》(C语言版)，严蔚敏吴伟民，清华大学出版社。【5】《c语言习题集与上机指导》第二版，谭浩强，高等教育出版社。

附件：

程序代码：

#include "stdio.h"

#define maxnum 10

#define maxvalue 88

typedef struct //定义存放各节点间边的权值的二位数组为新的数据类型可称为图{

int v[maxvalue][maxvalue];

} mgraph; //该数据类型用标识符mgraph表示

mgraph input(int n) //数据输入函数用于输入各节点间边的权值

{

mgraph x; //定义x为mgraph类型

while(n<=0||n>maxnum) //控制输入出错重新执行

{

printf("输入有误,请重新输入:");

scanf("%d",&n);

}

for(int i=1;i<=n;i++) //双层循环控制每个节点到其他各节点的权值

{

for(int j=0;j<=n;j++)

{

int temp; //定义临时变量用于存放输入权值便于接下的过滤操作

if(i==j) //各节点到自身的权重赋为0

x.v[i][j]=0;

else

if(i

{

printf("请输入节点%d到节点%d的权:",i,j);

scanf("%d",&temp); //将输入临时存放在temp

while(temp==0||temp<-1) //过滤输入数据

{

printf("输入有误,请重新输入:\n");

printf("请输入%d到%d的权:",i,j);

scanf("%d",&temp);

}

if(temp>0) //将符合要求数据赋值给temp

x.v[i][j]=temp;

else //temp=-1时将权重赋值最大值88

x.v[i][j]=maxvalue;

}

else //i>j由于权重是对称的即呈上三角或下三角分布故只需将i,j对换即可

x.v[i][j]=x.v[j][i];

}

printf("\n");

}

return x; //返回图x

}

void print(mgraph g,int n) //打印函数

{

int i,j; //定义整型i,j

printf(" "); //打印美观需要

for(i=1;i<=n;i++)

printf("%2d ",i);

printf("\n");

for(i=1;i<=n;i++) //双层循环按矩阵方式打印输出各节点间权值

{

printf("%d ",i);

for(j=1;j<=n;j++)

printf("%2d ",g.v[i][j]);

printf("\n");

}

}

void prim(mgraph g,int k,int n) //核心算法Prim算法实现函数

{

int i,j,min,p; //定义整型变量i,j用于循环min和p分别用于临时存放最小权值及其下标

struct //定义型类型数据closedge[]用于临时存放下标和最小边

{

int adjvex;

int lowcost;

}closedge[maxnum];

for(i=1;i<=n;i++) //初始化辅助数组

if(i!=k)

{

closedge[i].adjvex=k;

closedge[i].lowcost=g.v[k][i];

}

closedge[k].lowcost=0; //将节点加入生成树中

for(i=1;i

{

p=1; //初始化p

min=maxvalue; //初始化最小权值

for(j=1;j<=n;j++) //循环n次比较最小权值

if(closedge[j].lowcost!=0&&closedge[j].lowcost

{

min=closedge[j].lowcost; //替换最小权值为当前节点的权值

p=j; //记录该节点下标

}

printf("%d_ _%d\n",closedge[p].adjvex,p,min); //打印最小的权值的下标和最小边

closedge[p].lowcost=0; //将该节点加入生成树中

for(j=1;j<=n;j++) //刷新临时存放空间

if((g.v[p][j]) < (closedge[j].lowcost))

{

closedge[j].lowcost=g.v[p][j]; //赋值最小边

closedge[j].adjvex=p; //赋值最小边对应下标

}

}

}

int main() //主函数

{

int n,start; //定义整型n,start表示节点数和开始节点

printf("请输入节点数(不大于10):");

scanf("%d",&n);

mgraph red; //定义图red

red=input(n); //调用输入函数用户输入数据

print(red,n); //调用输出函数打印输出所输入的数据

printf("请输入开始节点:");

scanf("%d",&start);

图论期末考试整理复习资料

目录 第一章图的基本概念 (2) 二路和连通性 (4) 第二章树 (4) 第三章图的连通度 (6) 第四章欧拉图与哈密尔顿图 (8) 一，欧拉图 (8) 二．哈密尔顿图 (10) 第五章匹配与因子分解 (14) 一．匹配 (14) 二．偶图的覆盖于匹配 (15) 三．因子分解 (16) 第六章平面图 (20) 二．对偶图 (24) 三．平面图的判定 (25) 四．平面性算法 (28) 第七章图的着色 (34) 一．边着色 (34) 二．顶点着色 (35)

第九章 有向图 (40) 二 有向树 (41) 第一章 图的基本概念 1. 点集与边集均为有限集合的图称为有限图。 2. 只有一个顶点而无边的图称为平凡图。 3. 边集为空的图称为空图。 4. 既没有环也没有重边的图称为简单图。 5. 其他所有的图都称为复合图。 6. 具有二分类（X, Y ）的偶图（或二部图）：是指该图的点集可以分解为两个（非空）子 集 X 和 Y ，使得每条边的一个端点在 X 中，另一个端点在Y 中。 7. 完全偶图：是指具有二分类（X, Y ）的简单偶图，其中 X 的每个顶点与 Y 的每个顶点 相连，若 |X|=m ，|Y|=n ，则这样的偶图记为 Km,n 8. 定理1 若n 阶图G 是自补的（即 ），则 n = 0, 1（mod 4） 9. 图G 的顶点的最小度。 10. 图G 的顶点的最大度。 11. k-正则图: 每个点的度均为 k 的简单图。 例如,完全图和完全偶图Kn,n 均是正则图。 12. 推论1 任意图中，奇点的个数为偶数。 ()G δ()G ?

13. 14.频序列：定理4 一个简单图G的n个点的度数不能互不相同。 15.定理5 一个n阶图G相和它的补图有相同的频序列。 16. 17. 18.对称差：G1△G2 = (G1∪G2) - (G1∩G2) = (G1-G2)∪(G2-G1) 19.定义：联图在不相交的G1和G2的并图G1+G2中，把G1的每个顶点和G2的每个 顶点连接起来所得到的图称为G1和G2的联图，记为G1∨G2 20.积图：积图设G1= (V1, E1)，G2 = (V2, E2)，对点集V = V1×V2中的任意两个点u = (u1,u2)和v = (v1,v2)，当(u1 = v1和u2 adj v2) 或(u2 = v2 和u1 adj v1) 时就把u 和v 连接起来所得到的图G称为G1和G2积图。记为G = G1×G2 设G1= (V1, E1)，G2 = (V2, E2)，对点集V = V1×V2中的任意两个点u = (u1,u2)和v = (v1,v2)，当(u1 adj v1) 或(u1= v1 和u2 adj v2) 时就把u 和v 连接起来所得到的图G称为G1和G2的合成图。记为G=G1[G2]。

电子科技大学研究生试题《图论及其应用》(参考答案)

电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：120分钟 一．填空题(每题3分，共18分) 1．4个顶点的不同构的简单图共有__11___个； 2．设无向图G 中有12条边，已知G 中3度顶点有6个，其余顶点的度数均小于3。则G 中顶点数至少有__9___个； 3．设n 阶无向图是由k(k ?2)棵树构成的森林，则图G 的边数m= _n-k____; 4．下图G 是否是平面图？答__是___; 是否可1-因子分解？答__是_. 5．下图G 的点色数=)(G χ______, 边色数=')(G χ__5____。 图G 二．单项选择(每题3分，共21分) 1．下面给出的序列中，是某简单图的度序列的是( A ) (A) (11123); (B) (233445); (C) (23445); (D) (1333). 2．已知图G 如图所示，则它的同构图是（ D ） 3． 下列图中，是欧拉图的是（ D ） 4． 下列图中，不是哈密尔顿图的是（B ） 5． 下列图中，是可平面图的图的是（B ） A C D A B C D

6．下列图中，不是偶图的是（ B ） 7．下列图中，存在完美匹配的图是（B ） 三．作图(6分) 1．画出一个有欧拉闭迹和哈密尔顿圈的图； 2．画出一个有欧拉闭迹但没有哈密尔顿圈的图； 3．画出一个没有欧拉闭迹但有哈密尔顿圈的图； 解： 四．(10分)求下图的最小生成树，并求其最小生成树的权值之和。 解：由克鲁斯克尔算法的其一最小生成树如下图： 权和为：20. 五．(8分)求下图G 的色多项式P k (G). 解：用公式 (G P k -G 的色多项式： )3)(3)()(45-++=k k k G P k 。 六．(10分) 22，n 3个顶点的度数为3，…，n k 个顶点的度数为k ，而其余顶点的度数为1，求1度顶点的个数。 解：设该树有n 1个1度顶点，树的边数为m. 一方面：2m=n 1+2n 2+…+kn k 另一方面：m= n 1+n 2+…+n k -1 v v 1 3 图G

(完整版)八年级最短路径问题归纳小结

八年级数学最短路径问题 【问题概述】最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径．算法具体的形式包括： ①确定起点的最短路径问题 - 即已知起始结点，求最短路径的问题． ②确定终点的最短路径问题 - 与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题． ③确定起点终点的最短路径问题 - 即已知起点和终点，求两结点之间的最短路径． ④全局最短路径问题 - 求图中所有的最短路径． 【问题原型】“将军饮马”，“造桥选址”，“费马点”． 【涉及知识】“两点之间线段最短”，“垂线段最短”，“三角形三边关系”，“轴对称”，“平移”． 【出题背景】角、三角形、菱形、矩形、正方形、梯形、圆、坐标轴、抛物线等． 【解题思路】找对称点实现“折”转“直”，近两年出现“三折线”转“直”等变式问题考查．

在直线l 上求一点P ，使PB PA -的值最大． 作直线AB ，与直线l 的交 点即为P ． 三角形任意两边之差小于 第三边．PB PA -≤AB ． PB PA -的最大值＝AB ． 【问题11】 作法 图形 原理 在直线l 上求一点P ，使PB PA -的值最大． 作B 关于l 的对称点B ＇作直线A B ＇，与l 交点即 为P ． 三角形任意两边之差小于 第三边．PB PA -≤AB ＇． PB PA -最大值＝AB ＇． 【问题12】“费马点” 作法 图形 原理 △ABC 中每一内角都小于120°，在△ABC 内求一点P ，使P A +PB +PC 值最小． 所求点为“费马点”，即满足∠APB ＝∠BPC ＝∠ APC ＝120°．以AB 、AC 为边向外作等边△ABD 、△ACE ，连CD 、BE 相交于P ，点P 即为所求． 两点之间线段最短． P A +PB +PC 最小值＝CD ． 【精品练习】 1．如图所示，正方形ABCD 的面积为12，△ABE 是等边三角形，点E 在正方形ABCD 内，在对角线AC 上有 一点P ，使PD +PE 的和最小，则这个最小值为（ ） A ．3 B ．26 C ．3 D 6 2．如图，在边长为2的菱形ABCD 中，∠ABC ＝60°，若将△ACD 绕点A 旋转，当AC ′、AD ′分别与BC 、CD 交于点E 、F ，则△CEF 的周长的最小值为（ ） A ．2 B ．32 C ．32+ D ．4 l B A l P A B l A B l B P A B' A B C P E D C B A A D E P B C

图论及其应用答案电子科大

图论及其应用答案电子科 大 This model paper was revised by the Standardization Office on December 10, 2020

习题三： 证明：e是连通图G 的割边当且仅当V(G)可划分为两个子集V1和V2，使对任意u ∈V 1及v ∈V 2, G 中的路（u，v）必含e . 证明：充分性: e是G的割边，故G ?e至少含有两个连通分支，设V 1是其中一个连通分支的顶点集，V 2是其余分支的顶点集，对12,u V v V ?∈?∈，因为G中的u ,v不连通， 而在G中u与v连通，所以e在每一条(u ,v )路上，G中的(u ,v )必含e。 必要性：取12,u V v V ∈∈，由假设G中所有(u ,v )路均含有边e，从而在G ?e中不存在从 u与到v的路，这表明G不连通，所以e 是割边。 3.设G 是阶大于2的连通图，证明下列命题等价： （1） G 是块 （2） G 无环且任意一个点和任意一条边都位于同一个圈上； （3） G 无环且任意三个不同点都位于同一条路上。 （1）→（2）： G是块，任取G的一点u，一边e，在e边插入一点v，使得e成为两条边，由此得到新图G 1，显然G 1的是阶数大于3的块，由定理，G中的u,v 位于同一个圈上，于是G 1中u 与边e都位于同一个圈上。 （2）→（3）： G无环，且任意一点和任意一条边都位于同一个圈上，任取G的点u ，边e ，若u在e 上，则三个不同点位于同一个闭路，即位于同一条路，如u不在e上，由定理，e的两点在同一个闭路上，在e边插入一个点v ，由此得到新图G 1，显然G 1的是阶数大于3的块，则两条边的三个不同点在同一条路上。 （3）→（1）： G连通，若G不是块，则G中存在着割点u，划分为不同的子集块V 1, V 2, V 1, V 2无环，12,x v y v ∈∈，点u在每一条(x ,y )的路上，则与已知矛盾，G是块。 7.证明：若v 是简单图G 的一个割点，则v 不是补图G ?的割点。 证明：v是单图G的割点，则G ?v有两个连通分支。现任取x ,y ∈V (G ?v ), 如果x ,y 不在G ?v的同一分支中，令u是与x ,y处于不同分支的点，那么，x ,与y在G ?v的补图中连通。若x ,y在G ?v的同一分支中，则它们在G ?v的补图中邻接。所以，若v是G 的割点，则v不是补图的割点。 12.对图3——20给出的图G1和G2，求其连通度和边连通度，给出相应的最小点割和最小边割。 解：()12G κ= 最小点割 {6,8} 1()2G λ= 最小边割{（6,5），（8,5）}

gis计算最短路径的Dijkstra算法详细讲解

最短路径之Dijkstra算法详细讲解 １最短路径算法 在日常生活中，我们如果需要常常往返A地区和B 地区之间，我们最希望知道的可能是从A地区到B地区间的众多路径中，那一条路径的路途最短。最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。算法具体的形式包括： （１）确定起点的最短路径问题：即已知起始结点，求最短路径的问题。 （２）确定终点的最短路径问题：与确定起点的问题相反，该问题是已知终结结点，求最短路径的问题。在无向图中该问题与确定起点的问题完全等同，在有向图中该问题等同于把所有路径方向反转的确定起点的问题。 （３）确定起点终点的最短路径问题：即已知起点和终点，求两结点之间的最短路径。 （４）全局最短路径问题：求图中所有的最短路径。 用于解决最短路径问题的算法被称做“最短路径算法”，有时被简称作“路径算法”。最常用的路径算法

有：Dijkstra算法、A*算法、Bellman-Ford算法、Floyd-Warshall算法、Johnson算法。 本文主要研究Dijkstra算法的单源算法。 ２Dijkstra算法 2.1 Dijkstra算法 Dijkstra算法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。 Dijkstra算法是很有代表性的最短路算法，在很多专业课程中都作为基本内容有详细的介绍，如数据结构，图论，运筹学等等。 2.2 Dijkstra算法思想 Dijkstra算法思想为：设G=(V,E)是一个带权有向图，把图中顶点集合V分成两组，第一组为已求出最短路径的顶点集合（用S表示，初始时S中只有一个源点，以后每求得一条最短路径, 就将加入到集合S中，直到全部顶点都加入到S中，算法就结束了），第二组为其余未确定最短路径的顶点集合（用U 表示），按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中，总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外，每个顶点对应一个距离，S中的顶点的距离就是从v到此顶点的最短路径长度，U中的顶点的距离，是从v到此顶点只包括S 中的顶点为中间顶点的当前最短路径长度。 2.3 Dijkstra算法具体步骤 （1）初始时，S只包含源点，即S＝，v的距离为0。U包含除v外的其他顶点，U中顶点u距离为边上的权（若v与u有边）或）（若u不是v的出边邻接点）。 （2）从U中选取一个距离v最小的顶点k，把k，加入S中（该选定的距离就是v到k的最短路径长度）。 （3）以k为新考虑的中间点，修改U中各顶点的距离；若从源点v到顶点u（u U）的距离（经过顶点k）比原来距离（不经过顶点k）短，则修改顶点u 的距离值，修改后的距离值的顶点k的距离加上边上的权。 （4）重复步骤（2）和（3）直到所有顶点都包含在S中。 2.4 Dijkstra算法举例说明 如下图，设A为源点，求A到其他各顶点（B、C、D、E、F）的最短路径。线上所标注为相邻线段之间的距离，即权值。（注：此图为随意所画，其相邻顶点间的距离与图中的目视长度不能一一对等）

运筹学期末试题

《运筹学》试题样卷（一） 一、判断题（共计10分，每小题1分，对的打√，错的打X ） 1. 无孤立点的图一定是连通图。 2. 对于线性规划的原问题和其对偶问题，若其中一个有最优解， 另一个也一定有最优解。 3. 如果一个线性规划问题有可行解，那么它必有最优解。 4．对偶问题的对偶问题一定是原问题。 5．用单纯形法求解标准形式（求最小值）的线性规划问题时，与0 >j σ对应的变量 都可以被选作换入变量。 6．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷 多个最优解。 7. 度为0的点称为悬挂点。 8. 表上作业法实质上就是求解运输问题的单纯形法。 9. 一个图G 是树的充分必要条件是边数最少的无孤立点的图。 二、建立下面问题的线性规划模型（8分） 某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日；春夏季4000人日。如劳动力本身用不了时可外出打工，春秋季收入为25元 / 人日，秋冬季收入为20元 / 人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养每头奶牛需投资800元，每只鸡投资3元。养奶牛时每头需拨出1.5公顷土地种饲料，并占用人工秋冬季为100人日，春夏季为50人日，年净收入900元 / 每头奶牛。养鸡时不占用土地，需人工为每只鸡秋冬季0.6人日，春夏季为0.3人日，年净收入2元 / 每只鸡。农场现有鸡舍允许最多养1500只鸡，牛栏允许最多养200头。三种作物每年需要的人工及收入情况如下表所示： 试决定该农场的经营方案，使年净收入为最大。

三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表，表中54,x x 为 (1)写出原线性规划问题；（4分） (2)写出原问题的对偶问题；（3分） (3)直接由上表写出对偶问题的最优解。（1分） 四、用单纯形法解下列线性规划问题（16分） 3212max x x x Z +-= s. t. 3 x 1 + x 2 + x 3 ≤ 60 x 1- x 2 +2 x 3 ≤ 10 x 1+ x 2- x 3 ≤ 20 x 1 , x 2 , x 3 ≥0 五、求解下面运输问题。 （18分） 某公司从三个产地A 1、A 2、A 3 将物品运往四个销地B 1、B 2、B 3、B 4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示： 问：应如何调运，可使得总运输费最小? 六、灵敏度分析（共8分） 线性规划max z = 10x 1 + 6x 2 + 4x 3 s.t. x 1 + x 2 + x 3 ≤ 100 10x 1 +4 x 2 + 5 x 3 ≤ 600 2x 1 +2 x 2 + 6 x 3 ≤ 300 x 1 , x 2 , x 3 ≥ 0

离散数学图论部分经典试题及答案

离散数学图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝，则下列结论成立的是 ( )． A ．deg(V )=2∣E ∣ B ．deg(V )=∣E ∣ C ．E v V v 2)deg(=∑∈ D ．E v V v =∑∈)deg( 4．图G 如图一所示，以下说法正确的是 ( ) ． A ．{(a , d )}是割边 B ．{(a , d )}是边割集 C ．{(d , e )}是边割集 D ．{(a, d ) ,(a, c )}是边割集 5．如图二所示，以下说法正确的是 ( )． A ．e 是割点 B ．{a, e }是点割集 C ．{b , e }是点割集 D ．{d }是点割集 6．如图三所示，以下说法正确的是 ( ) ． A ．{(a, e )}是割边 B ．{(a, e )}是边割集 C ．{(a, e ) ,(b, c )}是边割集 D ．{(d , e )}是边割集 ο ο ο ο ο c a b e d ο f 图一 图二

图三 7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( ) ． 图四 A ．（a ）是强连通的 B ．（b ）是强连通的 C ．（c ）是强连通的 D ．（d ）是强连通的 应该填写：D 8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路． A ．m 为奇数 B ．n 为偶数 C ．n 为奇数 D ．m 为偶数 9．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 10．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树． A ．1m n -+ B ．m n - C ．1m n ++ D ．1n m -+ 12．无向简单图G 是棵树，当且仅当( )． A ．G 连通且边数比结点数少1 B ．G 连通且结点数比边数少1 C ．G 的边数比结点数少1 D ．G 中没有回路． 二、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结 点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 ο ο ο ο c a b f

最短路径问题

最短路径问题 摘要 在图论当中，任意两点间的最短路径问题，运用Dijkstra 算法，Flord 算法，匈牙利算法等都可以就解决这类相关问题,本文主要就是运用图论相关知识，来分析问题的。 在问题一中，需要为货车司机选择一条从地点1到地点11的最短时间问题，其实际归结为求一个两点间最短路径问题，运用运筹学中的网络模型相关知识，建立了一个一个0-1线性模型，并最终求的其结果，最短时间为21，货车司机的运输路线为1891011v v v v v →→→→。 运用Floyd 算法解决问题二，并且运用Matlab 软件编程，Floyd 算法与Matlab 软件编程所得出的结果一致，最后得出了一个最短航程表，及任意两点间的最短航程图。 本文的最大亮点在于将问题二进行更深一步的拓展，从问题实际出发，从公司的差旅费用最小出发，利用Mtlab 软件编程的出了公司到个城市间差旅费用最小图，从而更能为公司节省成本。 任意城市间差旅费用最小 其次是本文结果的准确性，问题一运用Lingo 软件编程，和WinQSB 软件，所得出结果都是一致的，问题二更是运用Floyd 算法，Matlab 软件编程，WinQSB 软件，大大地保证了结果的准确性，并且十分恰当地运用WinQSB 软件将作图功能，把每一提的最短路径都清晰的描绘出来，更加直观地将结果展现出来。 关键字：Matlab Lingo WinQSB Floyd 算法 0-1规划

一、 问题重述 问题一需要解决的问题是在一个城市交通网络中（图一），如何从地点1找到一条时间最短路径通往地点11，在这个城市交通网络中，有单向道，也有双向道，即如何处理一个有向图与无向图结合的图论问题，并且是一个两点间的最短路径问题： 图（一） 问题二阐述的是某公司员工往来于六个城市间，给出了这六个城市间的直达航班票价（表二），需要为这家公司提供出这六个城市间任意两点间的最小航班费用表 05040251050015202515010204020100102525201005510 2525550∞ ?? ??∞???? ∞∞?????? ∞?? ∞?? 表（二） 二、问题分析

图论与组合数学期末复习题含答案

组合数学部分 第1章 排列与组合 例1： 1)、求小于10000的含1的正整数的个数； 2、)求小于10000的含0的正整数的个数； 解：1)、小于10000的不含1的正整数可看做4位数,但0000除外.故有9×9×9×9－1＝6560个.含1的有：9999－6560=3439个 2)、“含0”和“含1”不可直接套用。0019含1但不含0。在组合的习题中有许多类似的隐含的规定，要特别留神。不含0的1位数有19个，2位数有29个，3位数有39个，4位数有49个 不含0小于10000的正整数有() ()73801919999954321=--=+++个含0小于10000的正整数9999－7380=2619个。 例2： 从[1,300]中取3个不同的数，使这3个数的和能被3整除，有多少种方案？ 解：将[1,300]分成3类： A={i|i ≡1(mod 3)}={1,4,7,…,298}, B={i|i ≡2(mod 3)}={2,5,8,…,299}, C={i|i ≡0(mod 3)}={3,6,9,…,300}. 要满足条件，有四种解法： 1)、3个数同属于A; 2)、3个数同属于B ； 3)、3个数同属于C; 4)、A,B,C 各取一数；故共有3C(100,3)+1003=485100+1000000=1485100。 例3：（Cayley 定理：过n 个有标志顶点的数的数目等于2-n n ） 1）、写出右图所对应的序列； 2）、写出序列22314所对应的序列； 解： 1）、按照叶子节点从小到大的顺序依次去掉节点（包含与此叶子 节点相连接的线），而与这个去掉的叶子节点相邻的另外一个点值则记入序列。如上图所示，先去掉最小的叶子节点②，与其相邻的点为⑤，然后去掉叶子节点③，与其相邻的点为①，直到只剩下两个节点相邻为止，则最终序列为51155.。 2）、首先依据给定序列写出（序列长度+2）个递增序列，即1234567，再将给出序列按从小到大顺序依次排列并插入递增序列得到：7。我们再将给出序列22314写在第一行，插入后的递增序列写在第二行。如下图第一行所示： ??→????? ??--②⑤67112223344522314??→???? ? ??--②⑥11223344672314 ??→????? ??--③②11233447314??→???? ? ??--①③11344714

电子科技大学2017年图论期末试卷

1 2017年图论课程练习题 一．填空题 1.图1中顶点a 到顶点b 的距离d (a ,b )= 。 a b 9 图1 1 2.已知图G 的邻接矩阵0 11011 01001 1010001011001 0A = ，则G 中长度为2的途径总条数为 。 3.图2中最小生成树T 的权值W (T )= 。 4.图3的最优欧拉环游的权值为 。 12 图 2

2 图3 5.树叶带权分别为1,2,4,5,6,8的最优二元树权值为 。 二．单项选择 1．关于图的度序列，下列说法正确的是( ) (A) 对任意一个非负整数序列来说，它都是某图的度序列； (B) 若非负整数序列12(,,,)n d d d π= 满足1n i i d =∑为偶数，则它一定是图序 列； (C) 若图G 度弱于图H ，则图G 的边数小于等于图H 的边数； (D) 如果图G 的顶点总度数大于或等于图H 的顶点总度数，则图G 度优 于图H 。 2．关于图的割点与割边，下列说法正确的是（ ） (A) 有割边的图一定有割点； (B) 有割点的图一定有割边； (C) 有割边的简单图一定有割点； (D) 割边不在图的任一圈中。 3.设()k G ，()G λ，()G δ分别表示图G 的点连通度，边连通度和最小度。下面说法错误的是( )

3 (A) 存在图G ，使得()k G =()G δ=()G λ； (B) 存在图G ，使得()()()k G G G λδ<<； (C) 设G 是n 阶简单图，若()2n G δ ≥ ，则G 连通，且()()G G λδ=； (D) 图G 是k 连通的，则G 的连通度为k 。 4.关于哈密尔顿图，下列命题错误的是( ) (A) 彼得森图是非哈密尔顿图； (B) 若图G 的闭包是哈密尔顿图，则其闭包一定是完全图； (C) 若图G 的阶数至少为3且闭包是完全图，则图G 是哈密尔顿图； (D) 设G 是三阶以上简单图，若G 中任意两个不邻接点u 与v ，满足 ()()d u d v n +≥，则G 是哈密尔顿图。 5.下列说法错误的是( ) (A) 有完美匹配的三正则图一定没有割边； (B) 没有割边的三正则图一定存在完美匹配； (C) 任意一个具有哈密尔顿圈的三正则图可以1因子分解； (D) 完全图21n K +是n 个哈密尔顿圈的和。 三、 设无向图G 有10条边，3度与4度顶点各2个，其余顶点度数均小于3，问G 中至少有几个顶点？在最少顶点数的情况下，写出G 的度序列，该度序列是一个图序列吗？。

运筹学期末试题

一、判断题（共计10分，每小题1分，对的打√，错的打X） 1.无孤立点的图一定是连通图。 2.对于线性规划的原问题和其对偶问题，若其中一个有最优解， 另一个也一定有最优解。 3.如果一个线性规划问题有可行解，那么它必有最优解。 4．对偶问题的对偶问题一定是原问题。 5．用单纯形法求解标准形式（求最小值）的线性规划问题时，与 > j σ 对应的变量都可以被选作换入变量。 6．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷 多个最优解。 7. 度为0的点称为悬挂点。 8. 表上作业法实质上就是求解运输问题的单纯形法。 9. 一个图G 是树的充分必要条件是边数最少的无孤立点的图。 二、建立下面问题的线性规划模型（8分） 某农场有100公顷土地及15000元资金可用于发展生产。农场劳动力情况为秋冬季3500人日；春夏季4000人日。如劳动力本身用不了时可外出打工，春秋季收入为25元/ 人日，秋冬季收入为20元/ 人日。该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。种作物时不需要专门投资，而饲养每头奶牛需投资800元，每只鸡投资3元。 养奶牛时每头需拨出1.5公顷土地种饲料，并占用人工秋冬季为100人日，春夏季为50人日，年净收入900元 / 每头奶牛。养鸡时不占用土地，需人工为每只鸡秋冬季0.6人日，春夏季为0.3人日，年净收入2元 / 每只鸡。农场现有鸡舍允许最多养1500只 三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表，表中5 4 ,x x 为松弛变量，问题的约束为?形式（共8分）

(1)写出原线性规划问题；（4分） (2)写出原问题的对偶问题；（3分） (3)直接由上表写出对偶问题的最优解。（1分） 四、用单纯形法解下列线性规划问题（16分） 3212max x x x Z +-= s. t. 3 x 1 + x 2 + x 3 ≤ 60 x 1- x 2 +2 x 3 ≤ 10 x 1+ x 2- x 3 ≤ 20 x 1, x 2 , x 3 ≥0 五、求解下面运输问题。 （18分） 某公司从三个产地A 1、A 2、A 3 将物品运往四个销地B 1、B 2、B 3、B 4，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示： 六、灵敏度分析（共8分） 线性规划max z = 10x 1 + 6x 2 + 4x 3 s.t. x 1 + x 2 + x 3 ≤ 100 10x 1 +4 x 2 + 5 x 3 ≤ 600 2x 1 +2 x 2 + 6 x 3 ≤ 300 x 1 , x 2 , x 3 ≥ 0 的最优单纯形表如下：

复杂网络基础2(M.Chang)

复杂网络基础理论 第二章网络拓扑结构与静态特征

第二章网络拓扑结构与静态特征 l2.1 引言 l2.2 网络的基本静态几何特征 l2.3 无向网络的静态特征 l2.4 有向网络的静态特征 l2.5 加权网络的静态特征 l2.6 网络的其他静态特征 l2.7 复杂网络分析软件 2

2.1 引言 与图论的研究有所不同，复杂网络的研究更侧重 于从各种实际网络的现象之上抽象出一般的网络几何 量，并用这些一般性质指导更多实际网络的研究，进 而通过讨论实际网络上的具体现象发展网络模型的一 般方法，最后讨论网络本身的形成机制。 统计物理学在模型研究、演化机制与结构稳定性 方面的丰富的研究经验是统计物理学在复杂网络研究 领域得到广泛应用的原因；而图论与社会网络分析提 供的网络静态几何量及其分析方法是复杂网络研究的 基础。 3

2.1 引言 静态特征指给定网络的微观量的统计分布或宏观 统计平均值。 在本章中我们将对网络的各种静态特征做一小结 。由于有向网络与加权网络有其特有的特征量，我们 将分开讨论无向、有向与加权网络。 4 返回目录

2.2 网络的基本静态几何特征 ￠2.2.1 平均距离 ￠2.2.2 集聚系数 ￠2.2.3 度分布 ￠2.2.4 实际网络的统计特征 5

2.2.1 平均距离 1.网络的直径与平均距离 网络中的两节点v i和v j之间经历边数最少的一条简 单路径（经历的边各不相同），称为测地线。 测地线的边数d ij称为两节点v i和v j之间的距离（或 叫测地线距离）。 1／d ij称为节点v i和v j之间的效率，记为εij。通常 效率用来度量节点间的信息传递速度。当v i和v j之间没 有路径连通时，d ij＝∞，而εij＝0，所以效率更适合度 量非全通网络。 网络的直径D定义为所有距离d ij中的最大值 6

集合论图论 期中考试试题及答案

08信安专业离散数学期中考试试题 1.设A, B, C, D为4个集合. 已知A?B且C?D.证明: A∪C?B∪D; A∩C?B∩D . (15分) 2.化简以下公式: A∪((B―A)―B) (10分) 3.设R是非空集合A上的二元关系.证明:R∪R-1是包含R的 最小的对称的二元关系. (15分) 4.设A={1,2,…,20},R={|x,y∈A∧x≡y(mod 5)}.证 明:R为A上的等价关系. 并求商集A/R. (15分) 5.给出下列偏序集的哈斯图,并指出A的最大元,最小元,极 大元和极小元. A={a,b,c,d,e},?A= I A∪{,, ,,,,} (15分) 6.设g:A→B, f:B→C.已知g f是单射且g是满射,证明:f 是单射. (10分) 7.设S={0,1}A, 其中A={a1,a2,…,a n}.证明:P(A)与S等势. (10分) 8.证明:任何一组人中都存在两个人,他们在组内认识的人 数恰好相等(假设,若a认识b,则a与b互相认识). (10分)

期中考试试题解答 1.证明: ?x, x∈A∪C x∈A∩C ?x∈A∨x∈C ?x∈A∧x∈C ?x∈B∨x∈D (A?B,C?D) ?x∈B∧x∈D (A?B,C?D) ?x∈B∪D ?x∈B∩D ∴A∪C?B∪D ∴A∩C?B∩D 2.解: A∪((B―A)―B) =A∪((B∩∽A)∩∽B) =A∪(∽A∩(B∩∽B)) =A∪(∽A∩φ) =A∪ф =A . 3.证明:首先证R∪R-1是对称关系. ?, ∈R∪R-1 ?∈R∨∈R-1 ?∈R-1∨∈R ?∈R-1∪R ?∈R∪R-1

2015电子科技大学_图论期末考试复习题

2015电子科技大学 图论考试复习题 关于图论中的图，以下叙述不正确的是 A ．图中点表示研究对象，边或有向边表示研究对象之间的特定关系。 B ．图论中的图，画边时长短曲直无所谓。 C ．图中的边表示研究对象，点表示研究对象之间的特定关系。 D ．图论中的图，可以改变点与点的相互位置，只要不改变点与点的连接关系。 一个图中最长的边一定不包含在最优生成树内。 下面哪个图形不与完全二分图K 3,3同构？ A ． B ． C ． D ． 有10条边的5顶单图必与K 5同构。 完全二分图K m ,n 的边数是 A ．m B ．n C ．m +n D ．mn 无向完全图K n 的边数为 A ．n B ．n 2 C ．n (n -1) D ．n (n -1)/2 若一个无向图有5个顶点，如果它的补图是连通图，那么这个无向图最多有 条边。 对于两个图，如果顶点数目相等，边数相等，次数相等的顶点数目也相等，则这两个图同构。 有15个顶的单图的边数最多是 A ．105 B ．210 C ．21 D ．45 图G 如右，则dacbeb A ．是G 中的一条道路 B ．是G 中的一条道路但不是行迹 C ．是G 中的一条行迹但不是轨道 D ．不是G 的一条道路 图G 如右，则befcdef A ．是G 的一个圈 B ．是G 的一条道路但不是行迹 C ．是G 的一条行迹但不是轨道 D ．是G 的一条轨道但不是圈

v1 36 7 图G如右图所示，则ω (G)= A．1 B．2 C．7 D．8 下列图形中与其补图同构的是 A．B．C．D． 求下图中顶u0到其余各顶点的最短轨长度。 u0v1=8，u0v2=1，u0v3=4，u0v4=2，u0v5=7，v1v2=7，v1v3=2，v1v6=4，v2v4=2，v2v7=3，v3v5=3，v3v6=6，v4v5=5，v4v7=1， v5v 6 =4，v 5 v7=3，v6v7=6， 请画出6阶3正则图。 请画出4个顶，3条边的所有非同构的无向简单图。 设图G={V(G)，E(G)}其中V ={ a1, a2, a3, a4, a5}，E(G)={(a1, a2)，(a2, a4)，(a3, a1)，(a4, a5)，(a5, a2)}，试给出G的图形表示并画出其补图的图形。 一个图的生成子图必是唯一的。 不同构的有2条边，4个顶的无向简单图的个数为 A．1 B．2 C．3 D．4 画出5个具有5个结点5条边的非同构的无向连通简单图。 u0到v1的最短轨长度为6，u0到v2的最短轨长度为1，u0 到v3的最短轨长度为4，u0到v4的最短轨长度为2，u0到v5的最短轨长度为6 ，u0到v6的最短轨长度为9，u0到v7的最短轨长度为3。

图论及其应用

图和子图 图 图 G = (V, E)， 其中 V = {νv v v ,......,,21} V ---顶点集， ν---顶点数 E = {e e e 12,,......,ε} E ---边集， ε---边数 例。 左图中， V={a, b,......,f}, E={p,q, ae, af,......,ce, cf} 注意， 左图仅仅是图G 的几何实现（代表）， 它们有无穷多个。真正的 图G 是上面所给出式子，它与顶点的位置、边的形状等无关。不过今后对两者将经常不加以区别。 称 边 ad 与顶点 a (及d) 相关联。也称 顶点 b(及 f) 与边 bf 相关联。 称顶点a 与e 相邻。称有公共端点的一些边彼此相邻，例如p 与af 。 环（loop ，selfloop ）：如边 l 。 棱（link ）：如边ae 。 重边：如边p 及边q 。 简单图：（simple graph ）无环，无重边 平凡图：仅有一个顶点的图（可有多条环）。 一条边的端点：它的两个顶点。 记号：νε()(),()().G V G G E G ==。 习题 1.1.1 若G 为简单图，则 εν≤?? ?? ?2 。 1.1.2 n ( ≥ 4 )个人中，若每4人中一定有一人认识其他3人，则一定有一 人认识其他n-1人。 同构 在下图中， 图G 恒等于图H , 记为 G = H ? V （G)=V(H), E(G)=E(H)。 图G 同构于图F ? V(G)与V(F), E(G)与E(F)之间各存在一一对应关系，且这二对应关系保持关联关系。 记为 G ?F 。 注 往往将同构慨念引伸到非标号图中，以表达两个图在结构上是否相同。 d e f G = (V, E) y z w c G =(V , E ) w c y z H =(V ?, E ?) ?a ? c ? y ? e ?z ? F=(V ??, E ??)

图论中最短路径问题

图论最短路径问题 在消防选址中的应用 【摘 要】 最短路径问题是图论解决的典型实际问题之一，可用来解决管路铺设、线路 安装、厂区布局和设备更新等实际问题。介绍了图论最短路径问题及其算法，并应用图论最短路径问题的分析方法，解决城市消防站的选址问题。 【关键词】 最短路径；Floyd 算法；消防 1 引言 图论是运筹学的一个重要分支，旨在解决离散型的优化问题，近年来发展十分迅速。在人们的社会实践中，图论已成为解决自然科学、工程技术、社会科学、生物技术以及经济、军事等领域中许多问题的有力工具之一。图论中的“图”，并不是通常意义下的几何图形或物体的形状图，也不是工程设计图中的“图”，而是以一种抽象的形式来表达一些确定的对象，以及这些对象之间具有或不具有某种特定关系的一个数学系统。也就是说，几何图形是表述 物体的形状和结构，图论中的“图”则描述一些特定的事物和这些事物之间的联系。它是数学中经常采用的抽象直观思维方法的典型代表。 2 图论基本概念 2.1 图的定义 有序三元组),,(?E V G =称为一个图，其中： (1)),,,(21n V V V V =是有穷非空集，称为顶点集，其元素叫做图的顶点； (2)E 称为边集，其元素叫做图的边； (3)?是从边集E 到顶点集V 的有序或者无序对集合的影射，称为关联函数。 2.2 图的分类 在图G 中，与V 中的有序偶),(j i V V 对应的边e 称为图的有向边(或弧)，而与V 中顶点的无序偶对应的边e 称为图形的无向边，每一条边都是无向边的图，叫做无向图，记为 ),(E V G =；每一条边都是有向边的图叫做有向图，记为),(E V D =；既有无向边又有有 向边的图叫做混合图。 2.3 权 如果图G 中任意一条边),(j i V V 上都附有一个数ij W ，则称这样的图G 为赋权图， ij W 称为边),(j i V V 上的权。

电子科技大学研究生试题图论及其应用参考答案完整版

电子科技大学研究生试题图论及其应用参考答 案 HUA system office room 【HUA16H-TTMS2A-HUAS8Q8-HUAH1688】

电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：120分钟 一．填空题(每题3分，共18分) 1．4个顶点的不同构的简单图共有__11___个； 2．设无向图G 中有12条边，已知G 中3度顶点有6个，其余顶点的度数均小于3。则G 中顶点数至少有__9___个； 3．设n 阶无向图是由k(k2)棵树构成的森林，则图G 的边数m= _n-k____; 4．下图G 是否是平面图？答__是___; 是否可1-因子分解？答__是_. 5．下图G 的点色数=)(G χ______, 边色数=')(G χ__5____。 图G 二．单项选择(每题3分，共21分) 1．下面给出的序列中，是某简单图的度序列的是( A ) (A) (11123); (B) (233445); (C) (23445); (D) (1333). 2．已知图G 如图所示，则它的同构图是（ D ） 3． 下列图中，是欧拉图的是（ D ） 4． 下列图中，不是哈密尔顿图的是（B ）

5． 下列图中，是可平面图的图的是（B ） 6．下列图中，不是偶图的是（ B ） 7．下列图中，存在完美匹配的图是（B ） 三．作图(6分) 1．画出一个有欧拉闭迹和哈密尔顿圈的图； 2．画出一个有欧拉闭迹但没有哈密尔顿圈的图； 3．画出一个没有欧拉闭迹但有哈密尔顿圈的图； 解： 四． A C D 1 2 3 A B C D

解：由克鲁斯克尔算法的其一最小生成树如下图： 权和为：20. 五．(8分) 求下图G 的色多项式P k (G). 解：用公式 )(e G P k -G 的色多项式： )3)(3)()(345-++=k k k G P k 。 六．(10分) 一棵树有n 2个顶点的度数为2，n 3个顶点的度数为3，…，n k 个顶点的度数 为k ，而其余顶点的度数为1，求1度顶点的个数。 解：设该树有n 1个1度顶点，树的边数为m. 一方面：2m=n 1+2n 2+…+kn k 另一方面：m= n 1+n 2+…+n k -1 由上面两式可得：n 1=n 2+2n 3+…+(k -1)n k 七．证明：(8分) 设G 是具有二分类(X,Y)的偶图，证明(1)G 不含奇圈；（2）若|X |≠|Y |，则G 是非哈密尔顿图。 证明：(1) 若不然，设C=v 1v 2…v m v 1为G 的一个奇圈，不妨设v 1X, v 5 v v v 6 图G

图论及其应用(精)

图论及其应用 学时：40 学分：2 课程属性：专业选修课开课单位：理学院 先修课程：高等代数后续课程：无 一、课程的性质 《图论及其应用》是数学与应用数学专业的专业选修课程。 二、教学目的 通过教学，使学生掌握图论及其算法的基本理论和基本技巧，初步掌握图论及其算法的基本应用手段、基本算法设计及编程，并能用所学理论解决一些应用问题。 三、教学内容 1.图的基本概念 2.图的连通性 3.树的基本性质及其应用 4.Euler Graphs and Hamilton Graphs with Applications 5.平面图性质 6.匹配，求最大匹配算法及应用 7.图的染色及应用 8.极图理论 四、学时分配 章课程内容学时 1 图的基本概念 4 2 图的连通性 6 3 树的基本性质及其应用 6 4 Euler Graphs and Hamilton Graphs with Applications 4 5 平面图性质 6 6 匹配，求最大匹配算法及应用 6

7 图的染色及应用 4 8 极图理论 4 合计40 五、教学方式 本课程采用多媒体课堂讲授，结合实际范例深入浅出讲解讨论。 六、考核方式 本课程考核采用平时与期末考核相结合的办法，特别注重平时的考核，作业采用简单练习、论文等形式，期末考试采用简单考题或论文形式。 七、教材及教学参考书 参考教材： [1] J.A.Bondy and U.S.R.Murty. Graph Theory with Applications, The Macmillan Press LTD,1976. [2] 蒋长浩．图论与网络流．北京：中国林业出版社，2000． 参考书目： [1] Bela Bollobas．Modern Graph Theory（现代图论，影印版）．北京：科学出版社，2001． [2] 殷剑宏、吴开亚．图论及其算法．合肥：中国科学技术大学出版社，2003． [3] 谢金星、邢文训．网络优化．北京：清华大学出版社．2000． [4] 程理民、吴江、张玉林．运筹学模型与方法教程．北京：清华大学出版社，2000． [5] 三味工作室．SPSS V10.0 for Windows 实用基础教程．北京：北京希望电子出版社2001． [６] 孙魁明、张海彤．Mathematica工具软件大全．北京：中国铁道出版社，1994． [７] 楼顺天、于卫、闫华梁．MATLAB程序设计语言．西安：西安电子科技大学出版社，1997．八、教学基本内容及要求 第一章图的基本概念 1．教学基本要求 掌握的图的基本概念、特殊图概念，了解最短路问题。 2．教学具体内容 图的基本概念，路和圈，最短路问题。