当前位置：搜档网 › 图的连通性判断MATLAB实验报告

图的连通性判断MATLAB实验报告

图的连通性总结

图的连通性总结 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的图像识别与匹配摘要图像的识别与匹配是立体视觉的一个重要分支，该项技术被广泛应用在航空测绘，星球探测机器人导航以及三维重建等领域。本文意在熟练运用图像的识别与匹配的方法，为此本文使用一个包装袋并对上面的数字进行识别与匹配。首先在包装袋上提取出来要用的数字，然后提取出该数字与包装袋上的特征点，用SIFT方法对两幅图进行识别与匹配，最终得到对应匹配数字的匹配点。仿真结果表明，该方法能够把给定数字与包装袋上的相同数字进行识别与匹配，得到了良好的实验结果，基本完成了识别与匹配的任务。

1 研究内容图像识别中的模式识别是一种从大量信息和数据出发，利用计算机和数学推理的方法对形状、模式、曲线、数字、字符格式和图形自动完成识别、评价的过程。图形辨别是图像识别技术的一个重要分支，图形辨别指通过对图形的图像采用特定算法，从而辨别图形或者数字，通过特征点检测，精确定位特征点，通过将模板与图形或数字匹配，根据匹配结果进行辨别。 2 研究意义数字图像处理在各个领域都有着非常重要的应用，随着数字时代的到来，视频领域的数字化也必将到来，视频图像处理技术也将会发生日新月异的变化。在多媒体技术的各个领域中，视频处理技术占有非常重要的地位，被广泛的使用于农业，智能交通，汽车电子，网络多媒体通信，实时监控系统等诸多方面。因此，现今对技术领域的研究已日趋活跃和繁荣。而图像识别也同样有着更重要的作用。 3 设计原理 3.1 算法选择 Harris 角点检测器对于图像尺度变化非常敏感，这在很大程度上限制了它的应用范围。对于仅存在平移、旋转以及很小尺度变换的图像，基于Harris 特征点的方法都可以得到准确的配准结果，但是对于存在大尺度变换的图像，这一类方法将无法保证正确的配准和拼接。后来，研究人员相继提出了具有尺度不变性的特征点检测方法，具有仿射不变性的特征点检测方法，局部不变性的特征检测方法等大量的基于不变量技术的特征检测方法。 David.Lowe 于2004年在上述算法的基础上，总结了现有的基于不变量技术的特征检测方法，正式提出了一种基于尺度空间的，对图像平移、旋转、缩放、甚至仿射变换保持不变性的图像局部特征，以及基于该特征的描述符。并将这种方法命名为尺度不变特征变换（Scale Invariant Feature Transform），以下简称SIFT 算法。SIFT 算法首先在尺度空间进行特征检测，并确定特征点的位置和特征点所处的尺度，然后使用特征点邻域梯度的主方向作为该特征点的方向特征，以实现算子对尺度和方向的无关性。利用SIFT 算法从图像中提取出的特征可用于同一个物体或场景的可靠匹配，对图像尺度和旋转具有不变性，对光照变化、

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实验报告(1-4)

信号与系统MATLAB第一次实验报告一、实验目的 1.熟悉MATLAB软件并会简单的使用运算和简单二维图的绘制。 2.学会运用MATLAB表示常用连续时间信号的方法 3.观察并熟悉一些信号的波形和特性。 4.学会运用MATLAB进行连续信号时移、反折和尺度变换。 5.学会运用MATLAB进行连续时间微分、积分运算。 6.学会运用MATLAB进行连续信号相加、相乘运算。 7.学会运用MATLAB进行连续信号的奇偶分解。二、实验任务将实验书中的例题和解析看懂，并在MATLAB软件中练习例题，最终将作业完成。三、实验内容 1.MATLAB软件基本运算入门。 1). MATLAB软件的数值计算：算数运算向量运算：1.向量元素要用”[ ]”括起来，元素之间可用空格、逗号分隔生成行向量，用分号分隔生成列向量。2.x=x0:step:xn.其中x0位初始值，step表示步长或者增量，xn 为结束值。矩阵运算：1.矩阵”[ ]”括起来；矩阵每一行的各个元素必须用”,”或者空格分开；矩阵的不同行之间必须用分号”;”或者ENTER分开。2.矩阵的加法或者减法运算是将矩阵的对应元素分别进行加法或者减法的运算。3.常用的点运算包括”.*”、”./”、”.\”、”.^”等等。举例：计算一个函数并绘制出在对应区间上对应的值。

2).MATLAB软件的符号运算：定义符号变量的语句格式为”syms 变量名” 2.MATLAB软件简单二维图形绘制 1).函数y=f(x)关于变量x的曲线绘制用语：>>plot(x,y) 2).输出多个图像表顺序：例如m和n表示在一个窗口中显示m行n列个图像，p表示第p个区域，表达为subplot(mnp)或者subplot(m,n,p) 3).表示输出表格横轴纵轴表达范围：axis([xmax,xmin,ymax,ymin]) 4).标上横轴纵轴的字母：xlabel(‘x’),ylabel(‘y’) 5).命名图像就在subplot写在同一行或者在下一个subplot前：title(‘……’) 6).输出：grid on 举例1：举例2：

基于MATLAB的图像处理字母识别

数字图像处理报告名称：字母识别学院：信息工程与自动化学院专业：物联网工程学号：201310410149 学生姓名：廖成武指导教师：王剑日期：2015年12月28日教务处制

目录字母识别 1.---------------------测试图像预处理及连通区域提取 2.---------------------样本库的建立采集feature 3.---------------------选择算法输入测试图像进行测试 4.---------------------总结

字母识别 1.imgPreProcess（联通区域提取）目录下 conn.m：连通区域提取分割（在原图的基础上进行了膨胀、腐蚀、膨胀的操作使截取的图像更加接近字母） %%提取数字的边界，生成新的图 clear; clc; f=imread('5.jpg'); f=imadjust(f,[0 1],[1 0]); SE=strel('square',5); %%膨胀、腐蚀、膨胀 A2=imdilate(f,SE); SE=strel('disk',3) f=imerode(A2,SE) SE=strel('square',3); f=imdilate(f,SE); gray_level=graythresh(f); f=im2bw(f,gray_level); [l,n]=bwlabel(f,8) %%8连接的连接分量标注 imshow(f) hold on for k=1:n %%分割字符子句 [r,c]=find(l==k); rbar=mean(r); cbar=mean(c); plot(cbar,rbar,'Marker','o','MarkerEdgeColor','g','MarkerFaceColor',' y','MarkerSize',10); % plot(cbar,rbar,'Marker','*','MarkerEdgecolor','w'); row=max(r)-min(r) col=max(c)-min(c) for i=1:row for j=1:col seg(i,j)=1; end

图的连通性判断

基于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/c18427869.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);