图论实验代码
图论实验报告（代码）
学号：1241902129
姓名：肖尧
1.写一个程序，输入一个图，一对顶点和通路长度，输出两个顶点间指定长度的通路。
程序代码：
#include
#include
#include
using namespace std;
#define MAX 20
typedef struct ArcNode{
int adjvex;
struct ArcNode *nextarc;
}ArcNode;
typedef struct VNode{
char data;
ArcNode *firstarc;
}VNode,AdjList[MAX];
typedef struct{
AdjList vertices;
int n,e;
}MGraph;
int path[MAX];
int visited[MAX];
//返回字符v 在图中的位置
int LocateV ex(MGraph G, char v)
{
int i;
for(i=0;i { if(G.vertices[i].data==v) {return i;break;} } return -1; } //得到顶点 Vi char GetV alue(MGraph G,int i) { return (i>=0 && i //判断字符m 是否在图中 int IsIn(MGraph G,char m) {int p; for(p=0;p { if(G.vertices[p].data==m) return p; } return -1; } //创建图 void CreatGraph(MGraph &G) { int i,k; char m,n; ArcNode *s; cout<<"请输入顶点数和边数: "; cin>>G.n>>G.e; cout< while(G.n>20) { cout<<"输入的数字不符合要求,请重新输入: "; cin>>G.n>>G.e; } while(G.e>((G.n-1)*G.n/2)) { cout<<"输入的数字不符合要求,请重新输入: "; cin>>G.e; } cout<<"请输入各顶点的名称: "; //建立顶点表 for(i=0;i { cin>>G.vertices[i].data; G.vertices[i].firstarc=NULL;//初始化图 } cout< //输入边 for(k=0;k { int a,b,p,q; cout<<"请输入有边的2 个顶点: "; cin>>m>>n; cout< p=IsIn(G,m); q=IsIn(G,n); while(p==-1||q==-1) { cout<<"输入的数字不符合要求,请重新输入: "; cin>>m>>n; p=IsIn(G,m); q=IsIn(G,n); } a=LocateV ex(G, m); b=LocateV ex(G, n); //生成边表结点 s=(ArcNode*)malloc(sizeof(ArcNode)); s->adjvex=a; s->nextarc= G.vertices[b].firstarc; //将顶点m 插入到顶点n 之后 G.vertices[b].firstarc=s; s=(ArcNode*)malloc(sizeof(ArcNode)); s->adjvex=b; s->nextarc= G.vertices[a].firstarc; //将顶点n 插入到顶点m 之后 G.vertices[a].firstarc=s; } } //k 是要判断的长度，x,y 为给定的两个点的地址 int Search(MGraph G,int x,int y,int k,int visited[],int path[],int d) { int n,i; ArcNode *p; visited[x]=1; d++; path[d]=x; if(x==y && d==k) return 1; p=G.vertices[x].firstarc; while(p !=NULL) { n=p->adjvex; if(visited[n]==0) { if((i=Search(G,n,y,k,visited,path,d))==1) return i; } p=p->nextarc ; } visited[x]=0; d--; return 0; } int main() { char m,n; int x,y,k,j; for( int i=0;i { visited[i]=0; } cout<<"本程序的功能：输入一个图，一对顶点和通路长度，输出两个顶点间指定长度的通路数。"< MGraph G; CreatGraph(G); cout<<"寻找路径的两个顶点: "; cin>>m>>n; cout< while(IsIn(G,m)==-1 || IsIn(G,n)==-1) { cout<<"顶点不符合要求,请重新输入: "; cin>>m>>n; } cout<<"请输入想寻找的简单路径的长度："; cin>>k; cout< x=LocateV ex(G,m); y=LocateV ex(G,n); j=Search(G,x,y,k,visited,path,-1); if(j==1) { cout<<"两个顶点间长度为"< for(int i=0;i { cout< } cout< } else cout<<"长度为"< system("pause"); } 运行结果（以P287页(图7 - 2.8)数据为例）： 2.编程用图的关联矩阵实现结点的合并，并输出合并后图的关联矩阵。 程序代码： #include #include namespace std; typedef struct Node{ int v; }Node; typedef struct Edge{ int e0; Node begin; Node end; }Edge; Node node[20]; Edge edge[50]; int Incidence_Matrix [50][50]; int Incidence_Matrix_2 [50][50]; void inite(int m,int n); void memset(int m,int n); void mergence(int m,int n,int merge_node1,int merge_node2); //初始化顶点和边 void inite(int m,int n) { int i,j,a,b; for (i=0;i { node[i].v=i; } for (j=0;j { cout< cout<<"请按照边的序号输入边的2 个顶点: "; cin>>a>>b; edge[j].e0=j; edge[j].begin.v=a-1; edge[j].end.v=b-1; } } //设置关联矩阵 void memset(int m,int n) { int i,j; for (i=0;i { for (j=0;j { if ((node[i].v==edge[j].begin.v)||(node[i].v==edge[j].end.v)) { Incidence_Matrix [i][j]=1; } } } cout< cout<<"完全关联矩阵: "< for (i=0;i { cout< for (j=0;j { cout< } cout< } cout< } //相关结点合并及合并后图的关联矩阵输出 void mergence(int m,int n,int merge_node1,int merge_node2) { int i,j; int p=0,q=0; //两顶点合并及消失点标记 for (j=0;j { Incidence_Matrix [merge_node1-1][j]=Incidence_Matrix [merge_node1-1][j] + Incidence_Matrix [merge_node2-1][j]; if (Incidence_Matrix [merge_node1-1][j]==2) { Incidence_Matrix [merge_node1-1][j]=0; } Incidence_Matrix [merge_node2-1][j]=-1; } //在合并后图的关联矩阵中消去标记顶点行 for (i=0;i { for (j=0;j { if (Incidence_Matrix [i][j]!=-1) { Incidence_Matrix_2 [p][q]=Incidence_Matrix [i][j]; q++; if (q==n) { q=0; p++; } } } } //输出合并后图的关联矩阵 cout< cout<<"合并后图的完全关联矩阵: "< for (i=0;i { cout< for (j=0;j { cout< } cout< } cout< } void main(void) { int m,n,merge_node1,merge_node2; cout<<"本程序的功能：输入一个图，用图的关联矩阵实现结点的合并，并输出合并后图的关联矩阵。(顶点均按顺序用数字1,2,3...表示)"< cout<<"请输入顶点数和边数: "; cin>>m>>n; inite(m,n); memset(m,n); cout<<"请输入需要合并的两个顶点(顶点均按顺序用数字1,2,3...表示) : "; cin>>merge_node1>>merge_node2; mergence(m,n,merge_node1,merge_node2); system("pause"); } 运行结果（以P296页(图7-3.7)数据为例）： 3.写一个程序，输入一个图，确定是否是欧拉图，如果是欧拉图，输出欧拉回路。 程序代码： #include #include #include //顶点的堆栈 struct stack{ int top , node[210]; } f; //图的邻接矩阵 int AdjMatrix[20][20]; int n; //图的深度优先遍历 void Depth_First_Search(int x) { int i; f.top ++; f.node[f.top] = x; for (i = 1; i <= n; i ++) { if (AdjMatrix[i][x] > 0) { //删除此边 AdjMatrix[i][x] = 0; AdjMatrix[x][i] = 0; Depth_First_Search(i); break; } } } //欧拉路算法 void Euler(int x) { int i , b; f.top = 0; f.node[f.top] = x; printf("\n 该图的欧拉图（回路）是："); while (f.top >= 0) { b = 0; for (i = 1; i <= n; i ++) { if (AdjMatrix[f.node[f.top]][i] > 0) { b = 1; break; } } //如果没有点可以扩展，输出并出栈 if (b == 0) { printf("%d" , f.node[f.top]); f.top --; if(f.top != -1) { printf(" => "); } } //如果有，就DFS else { f.top --; Depth_First_Search(f.node[f.top+1]); } } printf("\n\n"); } int main() { int m , s , t , num ; int i , j , begin; printf("本程序的功能：输入一个图，确定是否是欧拉图。如果是欧拉图，输出欧拉回路。(顶点均按顺序用数字1,2,3...表示)\n\n"); printf("请输入顶点数和边数: "); scanf("%d %d" , &n , &m); memset(AdjMatrix , 0 , sizeof(AdjMatrix)); for (i = 0; i < m; i ++) { printf("\n 请输入有边的2 个顶点："); scanf("%d %d" , &s , &t); while(s < 0 || s > n || t < 0 || t > n) { printf("\n 输入的数字不符合要求,请重新输入: "); scanf("%d %d" , &s , &t); } AdjMatrix[s][t] = 1; AdjMatrix[t][s] = 1; } //判断是否存在欧拉回路 s = 0; begin = 1; for (i = 1; i <= n; i ++) { num = 0; for (j = 1; j <= n; j ++) { num += AdjMatrix[i][j]; } if (num % 2 == 1) { begin = i; s ++; } } if ((s == 0) || (s == 2)) { Euler(begin); } else { printf("\n 输入的图不是欧拉图！\n\n"); } system("pause"); return 0; } 运行结果（以P303页(图b)数据为例）： 4.写一个程序，输入一个图，输出每个顶点的度数。 程序代码： #include #include #define M 20 #define MAX 20 typedef struct { int begin; int end; }edge; typedef struct { int adj; }AdjMatrix[MAX][MAX]; typedef struct { AdjMatrix arc; int vexnum, arcnum; }MGraph; //函数申明 void CreatGraph(MGraph *); void DEG(MGraph *); //创建图 void CreatGraph(MGraph *G) { int i, j,n, m; printf("请输入边数和顶点数: "); scanf("%d %d",&G->arcnum,&G->vexnum); //初始化图 for (i = 1; i <= G->vexnum; i++) { for ( j = 1; j <= G->vexnum; j++) { G->arc[i][j].adj = G->arc[j][i].adj = 0; } } //输入边 for ( i = 1; i <= G->arcnum; i++) { printf("\n 请输入有边的2 个顶点: "); scanf("%d %d",&n,&m); while(n < 0 || n > G->vexnum || m < 0 || m > G->vexnum) { printf("输入的数字不符合要求,请重新输入: "); scanf("%d%d",&n,&m); } G->arc[n][m].adj = G->arc[m][n].adj = 1; getchar(); } printf("\n 邻接矩阵为:\n"); for ( i = 1; i <= G->vexnum; i++) { for ( j = 1; j <= G->vexnum; j++) { printf("%d ",G->arc[i][j].adj); } printf("\n"); } } //输出每个顶点的度数 void DEG(MGraph *G) { int i, j, count; printf("\n 每个顶点的度数如下：\n\n"); for ( i = 1; i <= G->vexnum; i++) { count=0; for (j = 1; j <= G->vexnum; j++) { if (G->arc[i][j].adj == 1) { count++; } } printf("deg(%c) = %d\n",i+64,count); } } //主函数 int main(void) { MGraph *G; G = (MGraph*)malloc(sizeof(MGraph)); if (G == NULL) { printf("申请内存失败！"); exit(1); } printf("本程序的功能：输入一个图，输出每个顶点的度数。(顶点均按顺序用数字1,2,3... 表示)\n\n"); CreatGraph(G); DEG(G); system("pause"); return 0; } 运行结果（以P272页(图b)数据为例）： 5.写一个程序，输入一个有向图，输出每个顶点的出度和入度。 程序代码： #include #include #define M 20 #define MAX 20 typedef struct { int begin; int end; }edge; typedef struct { int adj; }AdjMatrix[MAX][MAX]; typedef struct { AdjMatrix arc; int vexnum, arcnum; }MGraph; //函数申明 void CreatGraph(MGraph *); void OUT_DEG(MGraph *); void IN_DEG(MGraph *); //创建图 void CreatGraph(MGraph *G) { int i, j,n, m; printf("请输入边数和顶点数: "); scanf("%d %d",&G->arcnum,&G->vexnum); //初始化图 for (i = 1; i <= G->vexnum; i++) { for ( j = 1; j <= G->vexnum; j++) { G->arc[i][j].adj = G->arc[j][i].adj = 0; } } //输入边 for ( i = 1; i <= G->arcnum; i++) { printf("\n 请输入有边的2 个顶点（先输入起始结点，再输入终止结点）"); ： scanf("%d %d",&n,&m); while(n < 0 || n > G->vexnum || m < 0 || m > G->vexnum) { printf("\n 输入的数字不符合要求,请重新输入: \n"); scanf("%d%d",&n,&m); } G->arc[n][m].adj = 1; getchar(); } printf("\n 邻接矩阵为:\n"); for ( i = 1; i <= G->vexnum; i++) for ( j = 1; j <= G->vexnum; j++) { printf("%d ",G->arc[i][j].adj); } printf("\n"); } } //输出每个顶点的出度 void OUT_DEG(MGraph *G) { int i, j, count; printf("\n 每个顶点的出度如下：\n"); for ( i = 1; i <= G->vexnum; i++) { count=0; for (j = 1; j <= G->vexnum; j++) { if (G->arc[i][j].adj == 1) { count++; } } printf("out-degree(%c) = %d\n",i+64,count); } } //输出每个顶点的入度 void IN_DEG(MGraph *G) { int i, j, count; printf("\n 每个顶点的入度如下：\n"); for ( j = 1; j <= G->vexnum; j++) { count=0; for (i = 1; i <= G->vexnum; i++) { if (G->arc[i][j].adj == 1) { count++; } } printf("in-degree(%c) = %d\n",j+64,count); } //主函数 int main(void) { MGraph *G; G = (MGraph*)malloc(sizeof(MGraph)); if (G == NULL) { printf("申请内存失败！"); exit(1); } printf("本程序的功能：输入一个有向图，输出每个顶点的出度和入度。(顶点均按顺序用数字1,2,3...表示)\n\n"); CreatGraph(G); OUT_DEG(G); IN_DEG(G); system("pause"); return 0; } 运行结果（以P273页(图b)数据为例）： 6.写一个程序，输入一个图，一对顶点和通路长度，输出两个顶点间指定长度的通路数。 程序代码： #include #include #include using namespace std; #define MAX 20 typedef struct ArcNode{ int adjvex; struct ArcNode *nextarc; }ArcNode; typedef struct VNode{ char data; ArcNode *firstarc; }VNode,AdjList[MAX]; typedef struct{ AdjList vertices; int n,e; }MGraph; int path[MAX]; int visited[MAX]; //返回字符v 在图中的位置 int LocateV ex(MGraph G, char v) { int i; for(i=0;i { if(G.vertices[i].data==v) {return i;break;} } return -1; } //得到顶点 Vi char GetV alue(MGraph G,int i) { 1.1、prim算法: 无向图的生成树就是从图的边集中选择一些边，使得这些边构成一个连通无环图，也就是树。如果给每一条边加一个权，所有生成树中权和最小的生成树称为最小生成树。 【Prim算法思想】 任意时刻的中间结果都是一棵树，每次花费最小的代价，用一条边把不在树中的结点加进来。【最小生成树算法实例】 现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表公路造价。在分析了这张图后发现，任一对城市都是连通的。现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最少？ 【输入】第一行两个数v(v<=200),e，分别代表城市数和边数以下e行，每行为两个顶点和它们之间的边权w(w<1000)。 【输出】连通所有城市的公路最小造价。 【输入样例】 6 10 1 2 10 1 5 19 1 6 21 2 3 5 2 4 6 2 6 11 3 4 6 4 5 18 4 6 14 5 6 33 【输出样例】50 原图 最小生成树 #include d[i]=INT_MAX; } d[f]=0; s=0; for(i=1;i<=n;i++) { mi=INT_MAX; for (j=1;j<=n;j++) if ((v[j]==false) && (d[j] 电子科技大学研究生试题 《图论及其应用》(参考答案) 考试时间：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 如 何 建 立 数 学 模 型 及 实 例 数学建模培训 科研处数学建模小组 第五章：如何建立数学模型 怎样撰写数学建模的论文？ 1．什么是数学模型？ 数学模型是对于现实世界的一个特定对象，一个特定目的，根据特有的内在规律，做出一些必要的假设，运用适当的数学工具，得到一个数学结构。 简单地说：就是系统的某种特征的本质的数学表达式（或是用数学术语对部分现实世界的描述），即用数学式子（如函数、图形、代数方程、微分方程、积分方程、差分方程等）来描述（表述、模拟）所研究的客观对象或系统在某一方面的存在规律。 2．什么是数学建模?数学建模是利用数学方法解决实际问题的一种 实践。即通过抽象、简化、假设、引进变量等处理过程后，将实际问题用数学方式表达，建立起数学模型，然后运用先进的数学方法及计算机技术进行求解。 观点：“所谓高科技就是一种数学技术” 注数学建模其实并不是什么新东西，可以说有了数学并需要用数学去解决实际问题，就一定要用数学的语言、方法去近似地刻划该实际问题，这种刻划的数学表述的就是一个数学模型，其过程就是数学建模的过程。数学模型一经提出，就要用一定的技术手段（计算、证明等）来求解并验证，其中大量的计算往往是必不可少的，高性能的计算机的出现使数学建模这一方法如虎添翼似的得到了飞速的发展，掀起一个高潮。 注 数学建模将各种知识综合应用于解决实际问题中，是培养和提高同学们应用所学知识分析问题、解决问题的能力的必备手段之一。 3．数学建模的一般方法和步骤建立数学模型的方法和步骤并没有一定的模 式，但一个理想的模型应能反映系统的全部重要特征：模型的可靠性和模型的使用性 建模的一般方法： ◆机理分析◆测试分析方法 机理分析：根据对现实对象特性的认识，分析其因果关系，找出反映内部机理的规律，所建立的模型常有明确的物理或现实意义。 测试分析方法：将研究对象视为一个“黑箱”系统，内部机理无法直接寻求，通过测量系统的输入输出数据，并以此为基础运用统计分析方法，按照事先确定的准则在某一类模型中选出一个数据拟合得最好的模型。测试分析方法也叫做系统辩识。 将这两种方法结合起来使用，即用机理分析方法建立模型的结构，用系统测试方法来确定模型的参数，也是常用的建模方法。在实际过程中用那一种方法建模主要是根据我们对研究对象的了解程度和建模目的来决定。机理分析法建模的具体步骤大致可见下图。 图论算法及其MATLAB 程序代码 求赋权图G =(V ,E ,F )中任意两点间的最短路的Warshall-Floyd 算法： 设A =(a ij )n ×n 为赋权图G =(V ,E ,F )的矩阵,当v i v j ∈E 时a ij =F (v i v j ),否则取a ii =0,a ij =+∞(i ≠j ),d ij 表示从v i 到v j 点的距离,r ij 表示从v i 到v j 点的最短路中一个点的编号. ①赋初值.对所有i ,j ,d ij =a ij ,r ij =j .k =1.转向② ②更新d ij ,r ij .对所有i ,j ,若d ik +d k j ＜d ij ,则令d ij =d ik +d k j ,r ij =k ,转向③. ③终止判断.若d ii ＜0,则存在一条含有顶点v i 的负回路,终止;或者k =n 终止;否则令k =k +1,转向②. 最短路线可由r ij 得到. 例1求图6-4中任意两点间的最短路. 解：用Warshall-Floyd 算法,MATLAB 程序代码如下： n=8;A=[0281Inf Inf Inf Inf 206Inf 1Inf Inf Inf 8607512Inf 1Inf 70Inf Inf 9Inf Inf 15Inf 03Inf 8 Inf Inf 1Inf 3046 Inf Inf 29Inf 403 Inf Inf Inf Inf 8630];%MATLAB 中,Inf 表示∞ D=A;%赋初值 for (i=1:n)for (j=1:n)R(i,j)=j;end ;end %赋路径初值 for (k=1:n)for (i=1:n)for (j=1:n)if (D(i,k)+D(k,j) 数学建模中的图论方法 一、引言 我们知道，数学建模竞赛中有问题A和问题B。一般而言，问题A是连续系统中的问题，问题B是离散系统中的问题。由于我们在大学数学教育内容中，连续系统方面的知识的比例较大，而离散数学比例较小。因此很多人有这样的感觉，A题入手快，而B题不好下手。 另外，在有限元素的离散系统中，相应的数学模型又可以划分为两类，一类是存在有效算法的所谓P类问题，即多项式时间内可以解决的问题。但是这类问题在MCM中非常少见，事实上，由于竞赛是开卷的，参考相关文献，使用现成的算法解决一个P类问题，不能显示参赛者的建模及解决实际问题能力之大小；还有一类所谓的NP问题，这种问题每一个都尚未建立有效的算法，也许真的就不可能有有效算法来解决。命题往往以这种NPC问题为数学背景，找一个具体的实际模型来考验参赛者。这样增加了建立数学模型的难度。但是这也并不是说无法求解。一般来说，由于问题是具体的实例，我们可以找到特殊的解法，或者可以给出一个近似解。 图论作为离散数学的一个重要分支，在工程技术、自然科学和经济管理中的许多方面都能提供有力的数学模型来解决实际问题，所以吸引了很多研究人员去研究图论中的方法和算法。应该说，我们对图论中的经典例子或多或少还是有一些了解的，比如，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。图论方法已经成为数学模型中的重要方法。许多难题由于归结为图论问题被巧妙地解决。而且，从历年的数学建模竞赛看，出现图论模型的频率极大，比如： AMCM90B－扫雪问题； AMCM91B－寻找最优Steiner树； AMCM92B－紧急修复系统的研制(最小生成树) AMCM94B－计算机传输数据的最小时间(边染色问题) CMCM93B－足球队排名(特征向量法) CMCM94B－锁具装箱问题(最大独立顶点集、最小覆盖等用来证明最优性) CMCM98B－灾情巡视路线(最优回路) 等等。这里面都直接或是间接用到图论方面的知识。要说明的是，这里图论只是解决问题的一种方法，而不是唯一的方法。 本文将从图论的角度来说明如何将一个工程问题转化为合理而且可求解的数学模型，着重介绍图论中的典型算法。这里只是一些基础、简单的介绍，目的在于了解这方面的知识和应用，拓宽大家的思路，希望起到抛砖引玉的作用，要掌握更多还需要我们进一步的学习和实践。 图论学习整理 图论程序整理出来 程序中图可以用邻接矩阵 Dijkstra算法 Floyd算法 Kruskal算法 Prim算法 算法类型：最短路，网络流，二分图算法。 解释： 最短路问题：（Dijkstra，Floyd算法） 最小生成树问题：连接多个节点费用最低（Prim，Kruskal算法）图的匹配问题：（匈牙利算法） 遍历性问题 最大流问题 运输问题：完成运输问题，并寻求运输费用最小方案 Matlab程序： n=8;A=[0 2 8 1 Inf Inf Inf Inf 2 0 6 Inf 1 Inf Inf Inf 8 6 0 7 5 1 2 Inf 1 Inf 7 0 Inf Inf 9 Inf Inf 1 5 Inf 0 3 Inf 8 Inf Inf 1 Inf 3 0 4 6 Inf Inf 2 9 Inf 4 0 3 Inf Inf Inf Inf 8 6 3 0]; % MATLAB 中, Inf 表示∞ D=A; %赋初值 for(i=1:n)for(j=1:n)R(i,j)=j;end;end %赋路径初值 for(k=1:n)for(i=1:n)for(j=1:n)if(D(i,k)+D(k,j) if(pd)break;end %存在一条负回路, 终止程序 end %程序结束 求最小费用最大流matlab代码 n=5;C=[0 15 16 0 0 0 0 0 13 14 0 11 0 17 0 0 0 0 0 8 0 0 0 0 0]; %弧容量 b=[0 4 1 0 0 0 0 0 6 1 0 2 0 3 0 0 0 0 0 2 0 0 0 0 0]; %弧上单位流量的费用 wf=0;wf0=Inf; %wf 表示最大流量, wf0 表示预定的流量值 for(i=1:n)for(j=1:n)f(i,j)=0;end;end %取初始可行流f 为零流 while(1) for(i=1:n)for(j=1:n)if(j~=i)a(i,j)=Inf;end;end;end%构造有向赋权图 for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j); elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j); elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;end for(i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值 for(k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路 for(i=2:n)for(j=1:n)if(p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end;end;end if(pd)break;end;end %求最短路的Ford 算法结束 if(p(n)==Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有dvt=Inf;t=n; %进入调整过程, dvt 表示调整量 while(1) %计算调整量 if(a(s(t),t)>0)dvtt=C(s(t),t)-f(s(t),t); %前向弧调整量 elseif(a(s(t),t)<0)dvtt=f(t,s(t));end %后向弧调整量 if(dvt>dvtt)dvt=dvtt;end if(s(t)==1)break;end %当t 的标号为vs 时, 终止计算调整量 t=s(t);end %继续调整前一段弧上的流f pd=0;if(wf+dvt>=wf0)dvt=wf0-wf;pd=1;end%如果最大流量大于或等于预定的流量值 t=n;while(1) %调整过程 if(a(s(t),t)>0)f(s(t),t)=f(s(t),t)+dvt; %前向弧调整 elseif(a(s(t),t)<0)f(t,s(t))=f(t,s(t))-dvt;end %后向弧调整 if(s(t)==1)break;end %当t 的标号为vs 时, 终止调整过程 t=s(t);end if(pd)break;end%如果最大流量达到预定的流量值 wf=0; for(j=1:n)wf=wf+f(1,j);end;end %计算最大流量 zwf=0;for(i=1:n)for(j=1:n)zwf=zwf+b(i,j)*f(i,j);end;end%计算最小费用 离散数学图论部分综合练习 一、单项选择题 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 ＝ 图三 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 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 的度序列，该度序列是一个图序列吗？。 介绍几个图论和复杂网络的程序库 刚加入复杂网络圈子，暂时还没有成熟的研究内容，先发个资料性的东西占坑：） 作复杂网络研究离不开对各种实际或模拟网络的统计、计算、绘图等工作。对于一般性的工作，我们可以用Pajek、Netdraw和Ucinet等软件完成。但对一些特殊应用（比如自己开发了一个新模型），现有的软件不能提供相应的建模或计算功能，这时就必须要通过编程的办法来解决问题了。 在这篇文章中，向大家介绍我使用过的4个面向图论及复杂网络分析的程序库，它们可以（分别或同时）用C、C++、C#和Python等语言调用。同时这些库都是开源的，可以通过研读它们的源代码提高编程水平。 好，下边开始介绍，第一位出场的是： 一、Boost Graph Library ——“准”C++标准库 Boost Graph Library（BGL）是C++ Boost库的成员之一。Boost是一个经过千锤百炼的C++库，作为标准模板库STL的后备，是C++标准化进程的发动机之一。Boost库由C++标准委员会库工作组成员发起，在C++社区中影响甚大，是不折不扣的“准”标准库。 BGL的特点是灵活性和高运行效率。BGL是以模板的形式提供的，这意味着你可以在模板的基础上创建自己的类型，比如自定义的节点类。BGL的开发者是世界上最顶尖的C++专家，这个库中实现的各种图算法具有非常高的执行效率，而且BGL本身具有工业强度，你可以放心的使用它。此外，BGL的代码结构良好，是非常值得研读的精品，对于学习算法与数据结构会有很大的帮助。 从我的角度来看，BGL的缺点是没有提供复杂网络分析的算法，所以在实际中我使用的还不多。建议对于分析大规模的网络问题时使用这个库，利用它良好的图数据结构，开发自己的复杂网络分析算法，将会获得很高的执行效率。 参考资源： BGL官方网站：https://www.sodocs.net/doc/d817706727.html,/doc/libs/1_42_0/libs/graph/ 技术书籍《The Boost Graph Library》，作者: Jeremy G. Siek，Lie-Quan Lee，Andrew Lumsdaine，见：https://www.sodocs.net/doc/d817706727.html,/subject/1463103/ 《使用Boost Graph library》，一个简短的BGL使用介绍，适合快速上手，见：https://www.sodocs.net/doc/d817706727.html,/2009/0408/100.html 《Boost Graph Library 学习笔记》，讨论学习BGL中遇到的问题，见：https://www.sodocs.net/doc/d817706727.html,/magicblue/archive/2009/05/22/4208976.aspx 二、QuickGraph —— .NET平台下的BGL QuickGraph是一个用C#语言编写的.NET组件库，所提供的算法与BGL类似，可以看作是Boost Graph Library在.NET平台下的实现。目前QuickGraph的最高版本是3.3，支 图论实验三个案例 单源最短路径问题 Dijkstra 算法 Dijkstra 算法是解单源最短路径问题的一个贪心算法。其基本思想是，设置一个顶点集合S 并不断地作贪心选择来扩充这个集合。一个顶点属于集合S 当且仅当从源到该顶点的最短路径长度已知。设v 是图中的一个顶点，记()l v 为顶点 v 到源点v 1的最短距离， ,i j v v V ?∈，若 (,)i j v v E ?，记i v 到j v 的权ij w =∞。 Dijkstra 算法： ① 1{}S v =,1()0l v =；1{}v V v ??-,()l v =∞,1i =,1{}S V v =-； ② S φ=，停止，否则转③； ③ ()min{(),(,)} j l v l v d v v =， j v S ∈，v S ?∈； ④ 存在 1 i v +，使 1()min{()} i l v l v +=，v S ∈； ⑤ 1{} i S S v +=， 1{} i S S v +=-，1i i =+，转②； 实际上，Dijkstra 算法也是最优化原理的应用：如果12 1n n v v v v -是从1v 到 n v 的最短路径，则 12 1 n v v v -也必然是从1v 到 1 n v -的最优路径。 在下面的MATLAB 实现代码中，我们用到了距离矩阵，矩阵第i 行第j 行元 素表示顶点i v 到j v 的权ij w ，若i v 到j v 无边，则realmax ij w =，其中realmax 是 MATLAB 常量，表示最大的实数+308)。 function re=Dijkstra(ma) 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。 251 图论模型 图论是运筹学的一个经典和重要分支，专门研究图与网络模型的特点、性质以及求解方法。许多优化问题，可以利用图与网络的固有特性而形成的特定方法来解决，比用数学规划等其他模型来求解往往要简单且有效得多。 图论起源于1736年欧拉对柯尼斯堡七桥问题的抽象和论证。1936年，匈牙利数学家柯尼希（D. K?nig ）出版的第一部图论专著《有限图与无限图理论》，树立了图论发展的第一座里程碑。近几十年来，计算机科学和技术的飞速发展，大大地促进了图论研究和应用，其理论和方法已经渗透到物理、化学、计算机科学、通信科学、建筑学、生物遗传学、心理学、经济学、社会学各个学科中。 9.1 图的基础理论 9.1.1 图的基本概念 所谓图，概括地讲就是由一些点和这些点之间的连线组成的。定义为(,)G V E =，V 是顶点的非空有限集合，称为顶点集。E 是边的集合，称为边集。边一般用(,)i j v v 表示，其中 ,i j v v 属于顶点集V 。 以下用V 表示图(,)G V E =中顶点的个数，E 表示边的条数。 如图9.1是几个图的示例，其中图9.1 (a)共有3个顶点、2条边，将其表示为 (,)G V E =，123{,,}V v v v =，1213{(,),(,)}E v v v v =. 2 3 v 45 v 3 4 (a) (c) 图9.1 图的示意图 1.无向图和有向图 如果图的边是没有方向的，则称此图为无向图（简称为图），无向图的边称为无向边（简称边）。如图9.1 (a)和(b)都是无向图。连接两顶点i v 和j v 的无向边记为(,)i j v v 或(,)j i v v 。 如果图的边是有方向（带箭头）的，则称此图为有向图，有向图的边称为弧（或有向边），如图9.1 (c)是一个有向图。连接两顶点i v 和j v 的弧记为,i j v v ??，其中i v 称为起点，j v 称为终点。显然此时弧,i j v v ??与弧,j i v v ??是不同的两条有向边。有向图的弧的起点称为弧头，弧的终点称为弧尾。有向图一般记为(,)D V A =，其中V 为顶点集，A 为弧集。 例如图9.1 (C)可以表示为(,)D V A =，顶点集1234{,,,}V v v v v =，弧集为1223{,,,, A v v v v =????243441,,,,,}v v v v v v ??????。 对于图除非指明是有向图，一般地，所谓的图都是指无向图。有向图也可以用G 表示。 例9.1 设12345{,,,,}V v v v v v =，12345{,,,,}E e e e e e =，其中 题目：最小生成树在城市交通建设中的应用 姓名： 学号： 指导老师： 专业：机械工程 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 (图论)matlab模板程序 第一讲：图论模型 程序一：可达矩阵算法 %根据邻接矩阵A（有向图）求可达矩阵P（有向图） function P=dgraf(A) n=size(A,1); P=A; for i=2:n P=P+A^i; end P(P~=0)=1; %将不为0的元素变为1 P; 程序二：无向图关联矩阵和邻接矩阵互换算法F表示所给出的图的相应矩阵 W表示程序运行结束后的结果 f=0表示把邻接矩阵转换为关联矩阵 f=1表示把关联矩阵转换为邻接矩阵 %无向图的关联矩阵和邻接矩阵的相互转换 function W=incandadf(F,f) if f==0 %邻接矩阵转换为关联矩阵 m=sum(sum(F))/2; %计算图的边数 n=size(F,1); W=zeros(n,m); k=1; for i=1:n for j=i:n if F(i,j)~=0 W(i,k)=1; %给边的始点赋值为1 W(j,k)=1; %给边的终点赋值为1 k=k+1; end end end elseif f==1 %关联矩阵转换为邻接矩阵 m=size(F,2); n=size(F,1); W=zeros(n,n); for i=1:m a=find(F(:,i)~=0); W(a(1),a(2))=1; %存在边，则邻接矩阵的对应值为1 W(a(2),a(1))=1; end else fprint('Please imput the right value of f'); end W; 程序三：有向图关联矩阵和邻接矩阵互换算法 %有向图的关联矩阵和邻接矩阵的转换 function W=mattransf(F,f) if f==0 %邻接矩阵转换为关联矩阵 m=sum(sum(F)); n=size(F,1); W=zeros(n,m); k=1; for i=1:n for j=i:n if F(i,j)~=0 %由i发出的边，有向边的始点 W(i,k)=1; %关联矩阵始点值为1 W(j,k)=-1; %关联矩阵终点值为-1 k=k+1; end end end elseif f==1 %关联矩阵转换为邻接矩阵 m=size(F,2); n=size(F,1); W=zeros(n,n); for i=1:m a=find(F(:,i)~=0); %有向边的两个顶点 if F(a(1),i)==1 W(a(1),a(2))=1; %有向边由a(1)指向a(2) else W(a(2),a(1))=1; %有向边由a(2)指向a(1) end end else fprint('Please imput the right value of f'); end W; 精心整理 图论算法matlab实现 求最小费用最大流算法的 MATLAB 程序代码如下： n=5;C=[0 15 16 0 0 0 0 0 13 14 for while for for(i=1:n)for(j=1:n)if(C(i,j)>0&f(i,j)==0)a(i,j)=b(i,j); elseif(C(i,j)>0&f(i,j)==C(i,j))a(j,i)=-b(i,j); elseif(C(i,j)>0)a(i,j)=b(i,j);a(j,i)=-b(i,j);end;end;end for(i=2:n)p(i)=Inf;s(i)=i;end %用Ford 算法求最短路, 赋初值 for(k=1:n)pd=1; %求有向赋权图中vs 到vt 的最短路 for(i=2:n)for(j=1:n)if(p(i)>p(j)+a(j,i))p(i)=p(j)+a(j,i);s(i)=j;pd=0;end ;end;end if(pd)break;end;end %求最短路的Ford 算法结束 if(p(n)==Inf)break;end %不存在vs 到vt 的最短路, 算法终止. 注意在求最小费用最大流时构造有 while if elseif if if pd=0; 值 t=n; if elseif if(s(t)==1)break;end %当t 的标号为vs 时, 终止调整过程 t=s(t);end if(pd)break;end%如果最大流量达到预定的流量值 wf=0; for(j=1:n)wf=wf+f(1,j);end;end %计算最大流量 zwf=0;for(i=1:n)for(j=1:n)zwf=zwf+b(i,j)*f(i,j);end;end%计算最小费用 电子科技大学研究生试题图论及其应用参考答 案 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图论算法详解(C++版)
电子科技大学研究生试题《图论及其应用》(参考答案)
第5-6章：如何建立数学模型及实例
图论算法及其MATLAB程序代码
数学建模中的图论方法
图论学习的整理笔记
离散数学图论部分经典试题及答案
电子科技大学2017年图论期末试卷
介绍几个图论和复杂网络的程序库
图论算法及matlab程序的三个案例
2015电子科技大学_图论期末考试复习题
图论 模型
图论应用案例
(图论)matlab模板程序
matlab图论程序算法大全
电子科技大学研究生试题图论及其应用参考答案完整版