图论学习报告.docx

《图论学习报告.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论学习报告报告内容:一．基本概念：1.叙述图：所谓图G是一个三元组，记做G=,其中V(G)={v1,v2,v3,…,vn},V(G)≠∅，称为图G的结点集合；E（G）=（e1，e2,…,en），是G的边的集合。ψ(G)称为关联函数。2.有向图：每一条边都是有向边的图称为有向图。3.无向图：每一条边都是无向边的图称为有向图。4.欧拉图：含欧拉回路的无向连通图与含有有向欧拉回路的弱连通有向图统称为欧拉图。5.哈密顿图：具有哈密顿回路的无向图，与具有哈密顿有向回路的有向图统称为哈密顿图。6.最短路径：在加权图中找出二个指定点之间的最短

2、路叫做最短路径。7.树：无圈连通无向图叫做树。8.二叉树：每个节点最多只有二个子树的树叫做二叉树。9.最小支撑树：连通加权图里权和最小的支撑树称为最小支撑树。10.最优二叉树：在所有的带权w1,w2,w3,…,wt的二叉树中，带权最小的二叉树称为最优二叉树。11.平面图：如果图G能够示画在曲面S上，且使得它的边近在断点处相交，则称G可嵌入曲面S。如果图G可以嵌入平面上，则称G是可平面图，已经嵌入平面上的图g称为G的平面表示。G与g都简称为平面图。二．算法设计1：写出Dijkstra算法{G带有顶点a=v0,v1,…,vn=z和权w（vi，vj），若{vi，vj}

3、不是G中的边，则w(vi,vj)=∞}Fori:=1tonL(vi):∞L(a):=0S:=¢{初始化标记，a的标记为0，其余结点标记为∞，S是空集}Whilez∉SBeginu:=不属于S的L（u）最小的一个顶点S：=S∪{u}For所有不属于S的顶点vIfL(u)+w(u,v)

4、值。　　定义一个矩阵D用来记录所插入点的信息，D[i,j]表示从Vi到Vj需要经过的点，初始化D[i,j]=j。　　把各个顶点插入图中，比较插点后的距离与原来的距离，G[i,j]=min(G[i,j],G[i,k]+G[k,j])，如果G[i,j]的值变小，则D[i,j]=k。　　在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为{V5,V3,V1}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。3：写出

5、求最小支撑树的算法普林算法：(G:带n个顶点的连通无向图)T：=权最小的边Fori:=1ton-2Begine:=与T里顶点相关联的权最小的边，并且若添加到T里则不形成圈T：=添加e之后的TEnd{T是G的最小支撑树}普林算法的另一种形式（G：加权连通图）Forj:=1tondobeginLj:=w(s,j){临时标号}B（j）：=s；EndLs:=0设置Ls为固定的While遗留临时标号doBegin选择最小临时标号Li设置Li为固定的边{i，B（i）}加入T结点i加入Tfor每个临时标号LkdoIfw（i，k）＜LkthenBeginLk：=w（i，k）B（

6、k）：=iEndEndReturnEnd{T为G的最小支撑树}克鲁斯卡尔算法（G：n个顶点的连通加权无向图）T：=空图Fori：=1ton-1Begine：=当添加到T里时不形成圈的G里权最小的边T：=添加e之后的TEnd{T是G的最小支撑树}三：程序实现1：写出Warshall算法的C语言程序#include#includeVoidmian(){IntA[10][10];Intn,I,j,k;Printf(“输入关系矩阵的维数n（n<10）”);Scanf(“%d”,&n);Printf(“输入n*n个数据（0or1）

7、”);For(i=1;i<=n;i++){For(j=1;j<=n;j++){Scanf(“%d”,&A[i][j]);If(A[i][j]!=1&&A[i][j])Printf(“thereisaerror”);}}For(i=1;i<=n;i++){For(j=1;j<=n;j++){For(k=1;k<=n;k++){If(A[i][j]&&(A[i][k]

8、

9、A[j][k]))A[i][k]=1;}}}Printf(“传递闭包的关系矩阵：”);For(i=1;i<=n;i++){For(j=1;j<=n;j++)Printf(“%2d”,A[i][j

10、]);Printf(“