搜档网
当前位置:搜档网 › 图的连通性

图的连通性

图的连通性
图的连通性

图论讲义第2章-连通性

第二章 图的连通性 在第一章中已经定义连通图是任二顶点间都有路相连的图。对于连通图,其连通的程度也有高有低。例如,下列三个图都是连通图。对于图G 1,删除一条边或一个顶点便可使其变得不连通;而对于图G 2,至少需要删除两条边才能使其不连通,也可以删除一个顶点使其不连通;对于图G 3,要破坏其连通性,则至少需要删除三条边或三个顶点。 本章主要讨论如何通过图的顶点集、边集和不交的路集合的结构性质来获知图的连通性程度。通过研究割边和割点来刻画1连通图的特性;定义连通度和边连通度来度量连通图连通程度的高低;通过不交路结构和元素的共圈性质来反映图的2连通和k 连通性。 §2.1 割点和割边 定义2.1.1 设)(G V v ∈,如果)()(G w v G w >?,则称v 为G 的一个割点。 (注:该定义与某些著作中的定义有所不同,主要是在环边的顶点是否算作割点上有区别)。 例如,下图中u , v 两点是其割点。 定理2.1.1 如果点v 是简单图G 的一个割点,则边集E (G)可划分为两个非空子集1E 和2E ,使得][1E G 和][2E G 恰好有一个公共顶点v 。 证明留作习题。 推论2.1.1 对连通图G ,顶点v 是G 的割点当且仅当v G ?不连通。 定理2.1.2 设v 是树T 的顶点,则v 是T 的割点当且仅当1)(>v d 。 证明:必要性:设v 是T 的割点,下面用反证法证明1)(>v d 。 若0)(=v d ,则1K T ?,显然v 不是割点。 若1)(=v d ,则v T ?是有1)(??v T ν条边的无圈图,故是树。从而)(1)(T w v T w ==?。因此v 不是割点。 以上均与条件矛盾。 充分性:设1)(>v d ,则v 至少有两个邻点u ,w 。路uvw 是T 中一条),(w u 路。因T 是树,uvw 是T 中唯一的),(w u 路,从而)(1)(T w v T w =>?。故v 是割点。证毕。

图的连通性总结

图的连通性总结 boboo 目录 1.图的遍历及应用 1.1.DFS遍历 1.2.DFS树的边分类 1.3.DFS树的性质 1.4.拓补排序 1.5.欧拉回路 2.无向图相关 2.1求割顶 2.2求图的桥 2.3求图的块 3.有向图相关 3.1求强连通分量(SCC划分) 3.2求传递闭包 4.最小环问题

一、图的遍历及应用 1.1 DFS遍历 DFS是求割顶、桥、强连通分量等问题的基础。 DFS对图进行染色, 白色:未访问; 灰色:访问中(正在访问它的后代); 黑色:访问完毕 一般在具体实现时不必对图的顶点进行染色,只需进行访问开始时间和访问结束时间的记录即可,这样就可以得出需要的信息了。 -发现时间D[v]:变灰的时间 -结束时间f[v]:变黑的时间 -1<=d[v]

matlab判别图的连通性

《数学文化》课程报告 题目:MATLAB判别图的连通性 2016年 11月26日

MATLAB判别图的连通性 摘要 图论中,在无向图G中,结点u和v之间若存在一条路,则称结点u和结点v是连通的。若图G只有一个连通分支,则称G是连通图。 如果两点相邻接,则在矩阵中记为1,否则记为0,形成的矩阵称为邻接矩阵。若两点相互连通,则记为1,否则记为0,形成的矩阵称为可达性矩阵。 用矩阵表示图,可以在matlab中进行计算 关键词:连通性;matlab;矩阵;可达性

实验目的 给定n个结点的有向图,判断图的连通性,如果是连通图,判断是强连通图、弱连通图还是单侧联通图 实验原理与数学模型 对于给定的邻接矩阵A,求出A所表示的图的可达矩阵P。对于可达矩阵P 来说,如果P的所有元素均为1,则所给的有向图是强连通的;对于P的所有元素(除主对角线元素外)Pij来说,均有:Pij+Pji>0,则所给有向图是单向连通的。当所给有向图既不是强连通的,又不是单向连通的时候,我们改造邻接矩阵为:对于矩阵A中所有的元素(除主对角线的元素外)aij,若aij=1或aji=1,则1?aij且1?aji。对于这样改造之后所得到的新的矩阵A’(A’相当于原有向图忽略方向之后所得到的无向图的邻接矩阵),再用前面所述的方法进行判断,当P’的所有元素(除主对角线的元素外)均为1时,原有向图是弱连通图;否则,原有向图是不连通的。 实验内容(要点) 1.通过图的邻接矩阵计算可达性矩阵 2.通过可达性矩阵判断图的连通性 3.如果是连通图,判断图是强连通图、弱连通图还是单侧连通图 实验过程记录 计算可达性矩阵函数 function P=canget(A) n=length(A); P=A; for i=2:n P=P+A^i; end P=(P~=0); 主程序 clear A=input('Enter an Adjacency Matrix:'); P=canget(A);

图的连通性判断

基于MATLAB的实现,此方法可以知道有几个连通域,并且知道各个顶点的归属。Branches中显示各个节点的归属,同一行的为同一连通分支中的节点。其第一列为它的分类数。 例如下图,有五个连通分支,1、2、3在同一个连通分支中。 这是上图的邻接矩阵,同一节点间为0。 Branches中的显示内容,第一列为连通分支数,后边跟着的是给连通分支中的节点。第一行就表示1、2、3为一个连通分支,4自己在一个连通分支中等等。 function [Branches,numBranch]=Net_Branches(ConnectMatrix) % ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ % This program is designed to count the calculate connected components in networks. % Usage [Cp_Average, Cp_Nodal] = Net_ClusteringCoefficients(ConnectMatrix,Type) % Input: % ConnectMatrix --- The connect matrix without self-edges. % Output: % Branches --- A matrix, each rows of which represents the

% different connected components. % numBranch --- The numbers of connected components in network % % +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ % Refer: % Ulrik Barandes % Written by Hu Yong, Nov,2010 % E-mail: carrot.hy2010@https://www.sodocs.net/doc/579500660.html, % based on Matlab 2008a % Version (1.0),Copywrite (c) 2010 % Input check-------------------------------------------------------------% [numNode,I] = size(ConnectMatrix); if numNode ~= I error('Pls check your connect matrix'); end % End check---------------------------------------------------------------% Node = [1:numNode]; Branches = []; while any(Node) Quence = find(Node,1); %find a non-zero number in Node set subField=[]; %one component % start search while ~isempty(Quence) currentNode = Quence(1); Quence(1) = []; %dequeue subField=[subField,currentNode]; Node(currentNode)=0; neighborNode=find(ConnectMatrix(currentNode,:)); for i=neighborNode if Node(i) ~= 0 %first found Quence=[Quence,i]; Node(i)=0; end end end subField = [subField,zeros(1,numNode-length(subField))]; Branches = [Branches;subField]; %save end numBranch = size(Branches,1);

图的连通性

图的连通性 图的连通性2010-07-23 21 :02 图的连通性 第十三章图的基本概念 第三节图的连通性 一.连通性概念 图中两点的连通:如果在图G中u、v 两点有路相通,则称顶点u、v 在图G中连通。 连通图(connected graph) :图G中任二顶点都连通。 图的连通分支(connected brch,component) :若图G 的顶点集 V(G)可划分为若干非空子集V 1,V 2, ?,V w, 使得两顶点属于同一子集当且仅当它们在G 中连通,则称每个子图G为图G的一个连通分支(i=1,2, ?,w) 。 注:(1) 图G的连通分支是G的一个极大连通子图。 (2)图G连通当且仅当w=1。 例13.5 设有2n 个电话交换台,每个台与至少n 个台有直通线路,则该交换系统中任二台均可实现通话。 证明:构造图G如下:以交换台作为顶点,两顶点间连边当且仅当对应的两台间有直通线路。问题化为:已知图G有2n 个顶点,且 δ(G) ≥n,求证G连通。 事实上,假如G不连通,则至少有一个连通分支的顶点数不超过n。在此连通分支中,顶点的度至多是n–1。这与δ(G)≥n 矛盾。 证毕

例13.6 若图中只有两个奇度顶点,则它们必连通。 证明:用反证法。假如u与v 不连通,则它们必分属于不同的连通分支。将每个分支看成一个图时,其中只有一个奇度顶点。这与推论13.1 矛盾。证毕 在连通图中,连通的程度也有高有低。 例如 后面将定义一种参数来度量连通图连通程度的高低。 二.割点 定义13.2 设v∈V(G),如果w(G–v)w(G) ,则称v 为G的一个割点。( 该定义与某些著作有所不同,主要是在有环边的顶点是否算作割点上有区别) 。 例如 定理13.3 如果点v 是图G的一个割点,则边集E(G)可划分为两个非空子集E 1和E 2,使得G[E 1]和G[E 2]恰好有一个公共顶点 v。 推论13.2 对连通图G,顶点v 是G的割点当且仅当G–v 不连通。 以上两个结论的证明留作习题。 三.顶点割集 定义13.3 对图G,若V(G)的子集V' 使得 w(G–V')w(G), 则称V'为图G的一个顶点割集。含有k 个顶点的顶点割集称为k-顶点割集

图论讲义2连通性

第二章 图的连通性 连通图:任二顶点间有路相连。 例 可见在连通图中,连通的程度也是有高有低。 本章的目的就是定义一种参数来度量连通图连通程度的高低。 §2.1 割边、割点与连通度 一、割点: 定义2.1.1 设)(G V v ∈,如果)()(G w v G w >?,则称v 为G 的一个割点。(该定义与某些著作有所不同,主要是在有环边的顶点是否算作割点上有区别)。 例 定理2.1.1 如果点v 是图G 的一个割点,则边集E (G)可划分为两个非空子集1E 和2E ,使得 ][1E G 和][2E G 恰好有一个公共顶点v 。 推论2.1.1 对连通图G ,顶点v 是G 的割点当且仅当v G ?不连通。 以上两个结论的证明留作习题。 定理2.1.2 设v 是树T 的顶点,则v 是T 的割点当且仅当1)(>v d 。 证明:必要性:设v 是T 的割点,下面用反证法证明1)(>v d 。 若0)(=v d ,则1K T ?,显然v 不是割点。 若1)(=v d ,则v T ?是有1)(??v T ν条边的无圈图,故是树。从而)(1)(T w v T w ==?。因此v 不是割点。 以上均与条件矛盾。 充分性:设1)(>v d ,则v 至少有两个邻点u ,w 。路uvw 是T 中一条),(w u 路。因T 是树,uvw 是T 中唯一的),(w u 路,从而)(1)(T w v T w =>?。故v 是割点。证毕。 推论2.1.2 每个非平凡无环连通图至少有两个顶点不是割点。 证明:设T 是G 的生成树,则T 至少有两个叶子u ,v ,由上一定理知,u ,v 都不是T 的割点,即1)()(==?T w u T w 。由于u T ?是图u G ?的生成树,故 )(1)()()(G w T w u T w u G w ===?=?,

实验2划分子网与连通性测试

实验2 划分子网与连通性测试 实验学时:2 一、实验目的 掌握IP地址的分配和划分子网的方法。 二、实验环境 用以太网交换机连接起来的Win2003操作系统计算机和Boson NetSim模拟器。 三、实验内容及步骤 1、IP地址分配 2、划分子网 3、模拟器应用 四、预备知识 1. 常见的网络设备 1.1 集线器 集线器的英文称为“Hub”。“Hub”是“中心”的意思,集线器的主要功能是对接收到的信号进行再生整形放大,以扩大网络的传输距离,同时把所有节点集中在以它为中心的节点上。它工作于OSI(开放系统互联参考模型)参考模型第一层,即“物理层”。集线器与网卡、网线等传输介质一样,属于局域网中的基础设备,采用CSMA/CD(一种检测协议)访问方式。 集线器属于纯硬件网络底层设备,基本上不具有类似于交换机的"智能记忆"能力和"学习"能力。它也不具备交换机所具有的MAC地址表,所以它发送数据时都是没有针对性的,而是采用广播方式发送。也就是说当它要向某节点发送数据时,不是直接把数据发送到目的节点,而是把数据包发送到与集线器相连的所有节点,如图1所示。 图1-1 集线器部署图

图1-2 集线器hub 1.2 网桥 网桥(Bridge)也称桥接器,是连接两个局域网的存储转发设备,用它可以完成具有相同或相似体系结构网络系统的连接。一般情况下,被连接的网络系统都具有相同的逻辑链路控制规程(LLC),但媒体访问控制协议(MAC)可以不同。网桥是数据链路层的连接设备,准确他说它工作在MAC子层上。网桥在两个局域网的数据链路层(DDL)间接帧传送信息,起桥接的作用。 图1-3 网桥 1.3 交换机 交换机(Switch)也叫交换式集线器,是一种工作在OSI第二层(数据链路层),基于MAC (网卡的介质访问控制地址)识别、能完成封装转发数据包功能的网络设备。它通过对信息进行重新生成,并经过内部处理后转发至指定端口,具备自动寻址能力和交换作用。 交换机不懂得IP地址,但它可以“自学习”源主机的MAC地址,并把其存放在内部地

判断图的强连通性

判断图的强连通性 一、判断一个n阶图的强连通性分以下3步骤: <1>根据图写出图的邻接矩阵(n * n)。 <2>依次计算邻接矩阵的2至(n-1)次方。 <3>观察得到的矩阵,若存在一点在每一个矩阵中都是0,则该点对应的两个顶点不存在通路,可得该图不是强连通图。若任一点在这些图中存在至少一个不为0,则任意两点总存在通路,可得该图是强连通图。(程序中将得到每个矩阵相加得到d矩阵,将d矩阵中所有不为“0”的元素置为“1”,再由顶点到顶点是连通的性质得到可达矩阵)。 二、用程序实现<2><3>两个步骤: 源代码如下: #include int main(){ int x,i,j,k; printf("请输入图的顶点数:"); scanf("%d",&x); int a[x][x],b[x][x],c[x][x],d[x][x];//a是图的邻接矩阵由d得出图的可达矩阵printf("请依次输入每行数据:\n"); for(i = 0 ; i < x ; i++){ for(j = 0 ; j < x ; j++){ scanf("%d",&a[i][j]); b[i][j] = a[i][j]; c[i][j] = a[i][j]; d[i][j] = a[i][j]; } getchar(); } //依次求出a的2至x-1次方 int t = 2;

while(t < x){ printf("A的%d次方:\n",t++); for(i = 0 ; i < x ; i++){ for(j = 0 ; j < x ; j++){ int sum = 0; for(k = 0 ;k < x ; k++){ sum = sum + b[i][k] * a[k][j]; } c[i][j] = sum; d[i][j] += c[i][j]; printf("%d\t",c[i][j]); } printf("\n"); } for(i= 0 ; i < x ; i ++) for(j = 0 ; j < x ; j++) b[i][j] = c[i][j]; } //输出可达矩阵并判断是否为强连通图 int flag = 1; printf("可达矩阵为:\n"); for(i= 0 ; i < x ; i ++){ for(j = 0 ; j < x ; j++){ if(d[i][j] > 0 || i == j) printf("1\t"); else{ printf("0\t"); flag = 0; } } printf("\n"); } if(flag == 1) printf("由可达矩阵知此图是强连通图!\n"); else printf("由可达矩阵知此图不是强连通图!\n"); return 0; } 实例测试: 教材p127图5-13

(完整版)图的连通性判断matlab实验报告

实验三:图的连通性判断 一、实验目的 用计算机语言编写图的连通性判断算法,可输入图的邻接矩阵,判断图是否连通以及确定连通分支的个数,掌握Warshell 算法或矩阵幂算法的实现方法。 二、实验原理 1、Warshell 算法 Warshell 算法可解决图是否连通的问题, 而且效率很高。在该算法中,矩阵P 是判断矩阵,1=ij p 表示从i 到j 连通,0=ij p 表示从i 到j 不连通。 (1)置新矩阵 P:= C ; (2)置 i = 1; (3)对所有的j ,若1),(=i j p , 则对k=1,2,…,n , 有),(),(:),(k i p k j p k j p ∨=; (4) 1+=i i ; (5) 如i n ≥转向步骤(3), 否则停止。 2、矩阵幂算法 由于邻接阵包含了图的所有信息,和关联阵一样,是图的等价表示。可以通过对邻接阵C 做一些计算,得到图G 的一些性质。例如考虑3C 中的),(j i 的元素 )3(,j i c ,如果它不为零,由于∑∑=k j l l k k i j i c c c c l ,,,)3(,,则至少存在一组1 ,,,===j l l k k i c c c 或一个长度为3的链使端i 和端j 相连。从而,通过计算C 的各阶幂次可得到关于图是否连通的信息。 三、实验内容 1.利用MATLAB 等语言实现图的连通性判断算法,可对输入的邻接阵进行连通性以及连通分支数的判断。 2.比较Warshell 算法和矩阵幂算法在算法正确性和算法复杂度上的区别。 3.对算法进行优化。 四、采用的语言 MatLab 源代码: clear,clc; %输入邻接矩阵

离散数学图论作业3-图的连通性

离散数学图论作业3-图的连通性 Problem1 判断下列各图是否是强连通的,如果不是,再判断是否是弱连通的。 (1)(2)(3) Problem2 证明:简单图G是二部图(bipartite graph),当且仅当G没有包含奇数条边的回路。 Problem3 a)证明或反驳:存在函数f:N→N使得对于所有k∈N,最小度至少为f(k)的图一定是k-连通的。 b)证明或反驳:存在函数f:N→N使得对于所有k∈N,边连通度至少为f(k)的图一定是k-连通的。Problem4 。(λ(G)表示G的边连通度) 证明:κ(G)=1的r-正则图G,若r>1,总满足λ(G)≤r 2

Problem5 证明:G是2-边连通图当且仅当G中任意两个顶点之间至少有两条不含公共边的通路。 (提示:证明过程中可使用Whitney定理,但需注意和本题的差异) Problem6 证明:若G是k?边连通图,从G中任意删除k条边,最多得到2个连通分支。 Problem7 对于任意的简单连通图G, 1.证明V(G)=E(G)时,G中有且仅有1个简单回路。(可直接使用V(G)=E(G)?1时图G中无简单 回路的结论) 2.该结论能否推广为E(G)≥V(G)时G中有且仅有E(G)?V(G)+1个简单回路? *题中简单回路不存在重复的边,可能存在大于1个重复顶点(见P573定义1) Problem8 证明:若简单图G是不连通的,则G的补图是连通图。 Problem9 证明:任意简单连通图G包含一条长度至少为min{2δ(G),|V(G)|?1}的顶点和边均不重复的通路。 (提示:证明过程中可以考虑图G中最长的[顶点和边均不重复的]通路)

中间P_2-图的边连通性

中间P_2-图的边连通性 图论中边连通度是用来研究网络可靠性的一个参数,它能比较准确的刻画小规模网络的容错性,其相关结论是研究互联网的拓扑结构的有利工具.为了更好的研究图的边连通度,1932年Whitney[1]提出了线图的概念.关于线图已有很多好的结论.后来,Broersmn和Hoede [2]把线图推广,提出了路图的概念.图G的Pk-路图Pk(G)其顶点集是G中所有k长路,其中两点相邻当且仅当在G中它们公共部分是k-1长路且它们的并是k+1长路或圈.显然,k=1时,P1(G)就是图G的线图.图G的中间图M(G)的定义为[15]:顶点集是V(G)∪E(G),其中两点x与y相邻当且仅当{x,y)n E(G)≠φ且x,y在G中相邻或关联.本文中,我们把中间图M(G)的概念推广,给出中间Pk-图Mk(G)的概念.图G的中间Pk-图Mk(G)的定义为:顶点集是V(G)∪V,(Pk(G)),边集是E(Pk(G))∪Ek,其中Ek={(v,p):p∈V(Pk(G)),v 是p的一个端点.}由上面定义,我们有:k=1时,M1(G)=M(G),k=2时,M2(G)=(V(G)∪V{P2(G),E(P2(G))∪E2).如果图G中含有一个包含所有边的闭迹,称图G是欧拉图.所有顶点度数是偶数的图称为偶图;所有顶点度数是奇数的图称为奇图.本文主要证明了:(1)顶点数|V(G)|≥3的连通图G,若6(G)≥2,则P2(G)连 通,M2(G)连通,且入(M2(G))≥2.(2)设G是连通图,如果δ(G)≥3,则λ(M2(G))≥2δ(G).(3)设G是连通图,若G是欧拉图,则M2(G)也是欧拉图.(4)设G和M2(G)都是连通图,若M2(G)是欧拉图,则G是偶图或奇图.

数据结构课程设计题4: 判断有向图的连通性(4)

#include #include #include using namespace std; const int MaxSize=20; //×??à?????úμ? int i,j,k; struct ArcNode //±?±í?úμ? { int adjivex; ArcNode * next; }; struct VertexNode //?¥μ?±í?úμ? { int data; ArcNode * firstedge; ArcNode * nfirstedge; } ; struct ArcNode* s; //±?±í?úμ?1¤×÷???? class Graph { public: Graph(int data[],int v,int a); //3?ê??ˉí?±í ~Graph(); //é?3yí?±í void PrintGraph(); //í?μ???ê? void InsertArc(int v1,int v2); void InsertArc(int n); //2?è?±? void InsertVertex(int v,int data); void InsertVertex(int data); //2?è??úμ? bool DeleteArc(int v1,int v2); //é?3y±? void DeleteVertex(); //é?3y?úμ? bool Isconect(); //é??èó??è±éàúó?á?í¨D?μ??D?¨ void Scprint(); //??á?í¨·?á? void DFS(int v,int a[]); void DFS1(int v,int a[],int b[]); void NDFS(int i,int visited[],int b[]); void scPrint(int b[]); void BFS(int v,int visisted[]); void BFS(); //è?í?1??èó??è±éàú

数据结构——图的连通性

稀疏图、稠密 8.4 图的连通性 判定一个图的连通性是图的一个应用问题,我们可以利用图的遍历算法来求解这一问题。本节将重点讨论无向图的连通性、有向图的连通性、由图得到其生成树或生成森林以及连通图中是否有关节点等几个有关图的连通性的问题。 8.4.1 无向图的连通性 在对无向图进行遍历时,对于连通图,仅需从图中任一顶点出发,进行深度优先搜索或广度优先搜索,便可访问到图中所有顶点。对非连通图,则需从多个顶点出发进行搜索,而每一次从一个新的起始点出发进行搜索过程中得到的顶点访问序列恰为其各个连通分量中的顶点集。例如,图8.5 (a)是一个非连通图G3,按照图8.18 所示G3 的邻接表进行深度优先搜索遍历,需由算法8.5调用两次DFS(即分别从顶点A 和D出发),得到的顶点访问序列分别为: A B F E C E 这两个顶点集分别加上所有依附于这些顶点的边,便构成了非连通图G3的两个连通分量,如图8.5(b) 所示。 因此,要想判定一个无向图是否为连通图,或有几个连通分量,就可设一个计数变量count,初始时取值为0,在算法8.5的第二个for循环中,每调用一次DFS,就给count增1。这样,当整个算法结束时,依据count的值,就可确定图的连通性了。 序号 图8.18 G3的邻接表 8.4.3 生成树和生成森林 在这一小节里,我们将给出通过对图的遍历,得到图的生成树或生成森林的算法。 设E(G)为连通图G中所有边的集合,则从图中任一顶点出发遍历图时,必定将E(G)分成两个集合T(G)和B(G),其中T(G)是遍历图过程中历经的边的集合;B(G)是剩余的边的

集合。显然,T(G)和图G 中所有顶点一起构成连通图G 的极小连通子图。按照8.1.2节的定义,它是连通图的一棵生成树,并且由深度优先搜索得到的为深度优先生成树;由广度优先搜索得到的为广度优先生成树。例如,图8.17(a)和(b)所示分别为连通图G5的深度优先生成树和广度优先生成树。图中虚线为集合B(G) 中的边,实线为集合T(G)中的边。 (a)G5的深度优先生成树 (b) G5的广度优先生成树 图8.19 由图8.17G5得到的生成树 (a) 一个非连通图无向图G6 (b) G6的深度优先生成树林 图8.20 非连通图G6及其生成树林 对于非连通图,通过这样的遍历,将得到的是生成森林。例如,图8.20 (b) 所示为图8.20 (a)的深度优先生成森林,它由三棵深度优先生成树组成。 假设以孩子兄弟链表作生成森林的存储结构,则算法8.10 生成非连通图的深度优先生成森林,其中DFSTree 函数如算法8.11 所示。显然,算法8.10 的时间复杂度和遍历相同。 void DESForest(Graph G , CSTree *T) { /*建立无向图G 的深度优先生成森林的孩子兄弟链表T*/ T=NULL; for (v=0;v

求图的连通性8

“离散数学”实验报告 (求图的连通性) 专业网络工程 班级1202班 学号12407442 姓名张敏慧 2013.12.14

目录 一.实验目的 (3) 二.实验原理 (3) 1. Warshell算法 (3) 2. 矩阵幂算法 (3) 三.实验环境 (3) 四. 实验流程图 (3) 1.实验内容 (3) 2.实验流程图 (4) 五.实验代码 (5) 1.MATLAB语言 (5) 2.C语言 (7) 六. 实验结果 (8) 七. 实验总结 (9)

一、实验目的 用计算机语言编写图的连通性判断算法,可输入图的邻接矩阵,判断图是否连通以及确定连通分支的个数,掌握Warshell 算法或矩阵幂算法的实现方法。 二、实验原理 1、Warshell 算法 Warshell 算法可解决图是否连通的问题, 而且效率很高。在该算法中,矩阵P 是判断矩阵,1=ij p 表示从i 到j 连通,0=ij p 表示从i 到j 不连通。 (1)置新矩阵 P:= C ; (2)置 i = 1; (3)对所有的j ,若1),(=i j p , 则对k=1,2,…,n , 有),(),(:),(k i p k j p k j p ∨=; (4) 1+=i i ; (5) 如i n ≥转向步骤(3), 否则停止。 2、矩阵幂算法 由于邻接阵包含了图的所有信息,和关联阵一样,是图的等价表示。可以通过对邻接阵C 做一些计算,得到图G 的一些性质。例如考虑3C 中的),(j i 的元素 )3(,j i c ,如果它不为零,由于∑∑=k j l l k k i j i c c c c l ,,,)3(,,则至少存在一组1 ,,,===j l l k k i c c c 或一个长度为3的链使端i 和端j 相连。从而,通过计算C 的各阶幂次可得到关于图是否连通的信息。 三、实验环境 使用visual C++6.0为编程软件,采用C 语言为编程语言实现。 使用MATLAB 等语言实现图的连通性判断算法。 四、实验流程图 实验内容: 利用MATLAB 等语言实现图的连通性判断算法,可对输入的邻接阵进行连通性以及连通分支数的判断。

相关主题