（计算数学专业论文）等周图像分割算法的加速改进及其中的优化问题.pdf

中文摘要 数字图像处理是计算数学研究的一个领域，图像分割是图像处理中- - i 1 基础而重要 的技术。数字图像的分割与目标的提取是数字图像处理和计算机视觉领域中一个备受关 注的研究分支。 经典的基于图理论的图像分割算法( 如归一化分割算法) ，对于大尺度的图像而言其 计算速度太慢复杂性太高，并且分割的稳定性极大程度地依赖于参数的选取，使其实际 应用性大大降低，等周图像分割算法虽然避免了这个缺陷，但是却不能最大限度地充分 利用求解线性方程组所得到的状态向量，且对于多目标的图像进行处理时所采用的二分 迭代会产生较大计算量，本文通过对多目标图像的状态向量和等周率进行分析，设计了 一种加速改进的k + 1 分迭代方式，经分析和实验表明改进后方法比原分割算法在计算次 数和计算时间上效率更高。 在对等周图像分割算法进行学习时，出现了最优化问题一一个2 进制的极小化问题， 于是对二进制编码的遗传算法进行了学习并尝试将遗传算法用于求解该极小化问题，虽 然结果不理想可是却是具有启发性的。 关键词 图像分割，等周算法，图论，k + 1 分迭代，状态向量，等周率 a b s t r a c t d i g i t a li m a g ep r o c e s s i n g i sab r a n c ho f c o m p u t a t i o n a lm a t h e m a t i c s ，a n di m a g e s e g m e n t a t i o ni so n eb a s i ca n di m p o r t a n tt e c h n o l o g yi nt h et h ef i e l do fi m a g ep r o c e s s i n g o b j e c ts e g m e n t a t i o na n d t h ee x t r a c t i o no ft a r g e ta r et h em o s td i s c u s s e da n da n t i c i p a t e db r a n c h i nd i g i t a li m a g ep r o c e s s i n ga n dc o m p u t e rv i s i o na r e a s t h ec o m p l e x i t yo fc l a s s i ci m a g es e g m e n t a t i o na l g o r i t h m sb a s e do ng r a p ht h e o r y ( s u c ha s n o r m a l i z e ds e g m e n t a t i o na l g o r i t h m ) i ss oh i g ht h a tt h es p e e do fc o m p u t i n gi sv e r ys l o wf o r l a r g es c a l ei m a g e t h es t a b i l i t yo ft h i sa l g o r i t h m sd e p e n d so nt h es e l e c t i o no ft h ep a r a m e t e rt o ag r e a te x t e n t ，s oi tc a nb eh a r db ea p p l i e dt oa p p l i c a t i o n b e c a u s eo ft h ed r a w b a c k so ft h e i s o p e r i m e t r i ca l g o r i t h ma p p l i e di ni m a g es e g m e n t a t i o n ，s u c ha sn o tm a k i n gf u l lu s eo ft h e s t a t ev e c t o rf r o ms o l v i n gl i n e a re q u a t i o n sa n dt h el a r g ea m o u n to fc a l c u l a t i o n sp r o d u c e db y s e c o n di t e r a t i o n ，t h e p a p e rp r e s e n t s t h ea c c e l e r a t e di m p r o v e m e n t ，t h ek + li t e r a t i v e m e t h o d ，a f t e ra n a l y s i n gt h e s t a t ev e c t o ra n dt h ei s o p e r i m e t r i cr a t i oa b o u ti m a g e so f m u l t i o b j e c t i v e a n a l y s i sa n de x p e r i m e n t ss h o wt h a tt h ei m p r o v e dm e t h o dt h a nt h eo r i g i n a l s e g m e n t a t i o na l g o r i t h mm o r ee f f i c i e n ti ni t e r a t i v en u m b e r sa n dt i m e w h e nt h ei m a g es e g m e n t a t i o na l g o r i t h ml e a r n t ，if o u n dt h a tt h e r ew a so n e o p t i m i z a t i o n p r o b l e m o n eo ft w ob i n a r ym i n i m i z a t i o np r o b l e m ，s ois t a r t e dt os t u d yg e n e t i ca l g o r i t h m s w i t hp a k so fb i n a r y - c o d e dt os o l v et h ev e r ys m a l lt h ei s s u e t h er e s u l t sa r en o ts a t i s f y i n g ，b u t i ti si n s t r u c t i v e k e yw o r d i m a g es e g m e n t a t i o n ，i s o p e r i m e t r i ca l g o r i t h m ，g r a p ht h e o r y ，k + ls u b - i t e r a t i o n ， s t a t ev e c t o r ，i s o p e r i m e t r i cr a t i o 西北大学学位论文知识产权声明书 本人完全了解西北大学关于收集、保存、使用学位论文的规定。学校 有权保留并向国家有关部门或机构送交论文的复印件和电子版。本人允许 论文被查阅和借阅。本人授权西北大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。同时授权中国科学技术信息研究所等机构将本学位论 文收录到中国学位论文全文数据库或其它相关数据库。 保密论文待解密后适用本声明。 学位论文作者签名：望鱼指导教师签名 如b 年只f ob 西北大学学位论文独创性声明 本人声明：所呈交的学位论文是本人在导师指导下进行的研究工作 及取得的研究成果。据我所知，除了文中特别加以标注和致谢的地方外， 本论文不包含其他人已经发表或撰写过的研究成果，也不包含为获得西 北大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的 同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢 = f 己 思。 学位论文作者签名：司琦 知知年告髓ob 日北大学顶学位论土 第一章引言 1 1 数字图像与数字图像处理 1 1 1 数字图像 任给一幅图片nr 都可以用一个二维矩阵g 来表示( 其中x 和y 表示空间二维坐标) ， 坐标为( x ，y ) 的函数值g 叫做对应点的扶度值( 伊a y l e v e l ) 。如果x 、y 和g 都是离散并且 有限的数值时，那么这幅图片称为数字图像”。 生活中的模拟图像是随处可见的，像照片、图片、海报、广告画等等。模拟图像经 过数字化处理之后可以得到数字图像。目前最常见的设备是扫描仪，当然也可以利用数 码照相机对摄模拟图像直接拍得到数字图像。模拟图像经扫描仪进行数字化或由数码照 相机拍摄所产生的数字图像，都是以数字格式存储在数字存储设备中的。这样，计算机 可以很方便地对这些数字信息直接进行各种处理，从而使数字图像达到特殊的视觉效 果。 gt 占1 l 占1 2 g2 1g2 2 g i g2 n g m lg m2g w 图1 田像矩阵表示 在计算机中，数字图像被分割成图1 所示的像素，各像素的扶度值用整数表示。 对于一幅像素大小为m x n 的数字图像。它的像素灰度值可以用一个m 行、n 列的矩阵 g 表示： 一( f - - d 黼e 三h 图2 图像与矩阵对应关系 图像处理在人们同常生活中已经越来越多得到广泛应用。像电视殊效制作电脑人 像拍摄艺术，邮政编码的机器识别以及身份识别( 指纹、虹膜、面部等特征的身份识别) 第一章引言 等等。医学领域很早就采用显微镜照片、x 射线透视等来进行诊断疾病。目前，医学影 像处理已经成为图像处理中很重要的一个应用分支，它已经成为现代医学诊断的重要手 段之一，即使对于一般摄影方法不能获取的身体内部的信息这个缺点，也可以利用特殊 的图像处理装置获取，其中最典型的就是x 射线c t ( 计算机断层摄像) 成像。 1 1 2 数字图像处理的主要内容 不论出于何种目的对数字图像进行处理，都需要通过图像处理系统把图像数据进行 输入、加工和输出。数字图像处理主要包括以下几个内容n i 。 1 图像获取、显示及表现 是指将模拟图像信息转化为能被计算机进行处理的数字信息，并通过一些处理设备 把数字图像显示和表现出来。该过程主要包含图像的摄取、光电转换和数字化等等若干 个步骤。 2 图像复原 由于某己知原因图像退化( 品质下降) 时，图像复原技术可以对此图像进行校正。 复原技术的核心步骤是针对具体退化原因退化建立一个合理的数学模型。消除退化产生 的影响是基于数学模型和数据的复原技术的最终目的。 3 图像增强 以改善图像视感质量为目的图像增强技术与图像复原不同，因为在处理过程中对图 像退化的定量信息一无所知，很难确定一种对所有图像都适用的方法，一般都主观采用 图像增强技术来改善图像的质量，其中常见的方法像去噪、增加对比度和修正几何畸变 等等。 4 图像分割 图像分割是指把图像分成若干不相交区域的过程，这些区域一般代表被成像的一个 物体( 或部分) 。为了使图像达到识别和理解的目的，对图像必须遵照一定的规则进行 分割。 5 图像重建 图像复原和图像增强的输入前后结果都是图像，与它们不同图像重建技术是一个从 数据到图像的处理过程，即输入的是数据信息，处理后得到的是图像，其中最典型应用 实例就是c t 图像重建。 6 图像压缩 庞大的数据量是数字图像的最大特点之一。图像压缩的目的就是压缩数据量。尽管 2 两北大学硕，t - 学位论文 现在的存贮器容量很大，可是依旧不能满足对庞大数据量图像( 动态图像或高分辨率图 像) 处理的需要，所以在实际应用中图像压缩是很重要的- - i q 技术。如果对大数据图像 不进行压缩，那么在存储和传输中就会因为占据很大的资源导致成本增加和不必要的浪 费。 1 2 图像分割 1 2 1 研究背景 图像分割是图像分析领域中一门重要的处理技术，是数字图像处理和计算机视觉领 域中一个备受关注的研究分支。伴随着这一分支的不断深入研究必将推动模式识别、人 工智能、计算机视觉等计算机科学分支的发展。图像分割问题在近二十年中引起了广泛 的关注并取得了长足的发展，国内外很多学者和研究人员针对此问题提出了很多不同方 法，为不同领域的研究提供了很大的帮助。但是是否可以寻找到一种能够普遍适用于各 种复杂情况并且准确率很高的分割算法，还有非常大的探索空间。 所有图像处理技术中，图像的自动分割是最困难的问题之一。动物视觉系统之所以 优越，最关键的一点是动物能够将所观察的目标从复杂背景中单独剥离出来，计算机却 很难做到这一点。目前，大部分数字图像的自动分割都需要人工辅助，只有其中一小部 分领域不需要人工辅助( 像指纹识别、印刷字符自动识别等) 。所以解决与分割相关的 问题是实现特定领域中图像分析实用化非常关键的一步，故而图像分割的热点研究方法 之一就是融合多种分割算法并利用知识来提高处理过程的有效性和可靠性。 1 2 2 数字图像分割 任何一幅数字图像都包含目标和背景，不同目标和区域的空间纹理、亮度、几何形 状等特征都会有所差异，图像分割的就是根据这些差异将图像分解为一系列有意义的区 域，使得同一区域内的特征在表现出一致性或相似性，不同区域间表现出明显的不同”，。 形象的看，图像分割是将图像划分成若干个互不相交区域的过程，这些区域是某种意义 下具有共同属性像素的连通集合。图像分割可以形象化定义如下【2 l ： 令有序集合r 表示图像区域( 像点集) ，对r 分割是将r 分解成满足下面5 个条件 的非空有序子集r ，r ：，r 。： n ( 1 ) u r , = r ： i - 1 分割是彻底的，图像中任一个像点都属于某一子区域； 3 第一章引言 ( 2 ) r n 马= 彩，v i ，ji j ； 区域不能重叠，一个像点不能同时属于两个区域； ( 3 ) p ( r i ) ：t r u e ，v i ； 同一区域内各像点属性或特征是相近的； ( 4 ) p ( 弓u r , ) = f a l s e ，i # j 且r - - l jr ，相邻； 相异的两个区域属性或特征是不同的； ( 5 ) 足是连通的区域，v i ； 同一区域中的像点是连通的； 图像分割方法有多种多样，据其主要特征大致上可以分为三组：第一组是有关图像 的全局知识，这种知识一般由图像特征的直方图来表达；第二组是通过确定区域间的边 界来实现图像分割的方法；图像边缘存在于像素灰度值有阶变化或屋顶变化的那些像素 集。反映在数学中边缘位置应该在导数值较大处，所以对图像进行求导是边缘检测一个 最简单的方法，该检测算法中最具代表性的算子有：r o b e r t s 3 1 、p r e w i t t 4 1 、k i r s c h 5 1 、 r o b i n s o n 6 1 以及c a n n y 7 】算子。针对边缘是某些特定形状的曲线( 如圆，直线等) 这种情 况，霍夫【8 1 于1 9 6 2 年提出的霍夫变换的检测效果非常好。第三组是基于区域的分割， 这类方法主要是利用特定区域与其它区域特性上的差异来进行图像分割的，典型的如 h a d d o n 和b o y c e 9 1 算子、p a v l i d i s 和l i o w 1 0 1 算子等。 图像分割是图像处理与计算机视觉领域中最为基础并且也是最重要的领域之一，它 是对图像进行视觉分析和模式识别的前提和基础，同时也是一个经典难题，迄今为止， 既不存在一种通用的图像分割方法，也没有一种判断是否分割成功的客观标准。 近年来，涌现出许多新的图像分割方法，如基于数学形态学、模糊理论、小波分析、 神经网络、粗糙集理论、遗传算法、粒子群算法等等新的图像分割技术【1 1 】。 基于图论的图像分割方法由于可以获得精确的结果，近些年越来越受到人们的重 视，尤其是最小割法、归一化最小割法和等周算法是基于图论图像分割方法中的典型方 法【1 2 l 。 1 2 3 图论在图像分割算法中的应用 图论 1 3 1 是以图为研究对象的，它是离散数学的一个分支。图论中的图是由若干给定 的顶点和边所构成的，它通常用来描述事物之间的某些特定关系( 顶点表示事物，边表 示事物间的某种联系) 。图论的最早可以追溯到1 8 世纪的柯尼斯堡七桥问题【1 4 】，这与 4 两北人学硕一 ：学位论文 2 0 世纪5 0 年代计算机信息和网络传播行业的快速发展是分不开的。此外，图论在物理 学、信息论、运筹学、经济管理、金融学等各方面都有广泛的应用。相信伴随着信息时 代的发展，图论在各个行业正日益显现出其强大的生命力。 把图理论运用到图像分割已经有比较长的历史了，根据图理论过去3 0 年的研究成 果，很多关于图像分割的新算法被提出来，典型的有最小生成树分割算法【1 s l ，基于图割 理论【1 6 i 以及图的频谱理论【1 7 l 等图像分割算法。 以图理论为基础的图像分割算法一般先把图像的分割问题转化为图的分割问题然 后再进行处理。z a l m 曾经提出了一种以图论为基础的最小生成树( m s t ) 的分割算法，该 方法利用图中权值最小( 对应的图像像素灰度差别最大) 的边来构造子图，从而达到分割 的目的，然而这种简单的割断最小权值边的方法存在比较大的缺陷。一幅图像灰度剧烈 变化区域的像素间的灰度差别往往很大，如果仅仅简单得通过设置某个阈值来割断这些 边，就很有可能产生错误。u r q u h a r t 1 8 1 针对此缺点提出了一种解决办法，然而效果并不 是很理想。 新近出现的一种以图论为基础的图像分割算法是基于直接寻找图中的最小割的最 优化方法，该算法的划分原则就是要使所划分的子图间的相似性最小。根据这个原则 w h 和l e a h y t l 9 1 提出了一种划分方法，但是他们的划分方法偏向过于明显，通常会将一 个大的图划分为一个极小的子图和另一个很大的图。造成这个问题的原因在于没有考虑 到所分子区域内的自相似性，于是s h i 和m a l i k t 加1 采用了“归一化 的方法，大大改善 了算法的分割效果。早期的图论分割方法比较重视局部特征，与之相比较近些年提出的 基于割的图像分割方法更加倾向于把握图像的全局性质。但是归一化割方法是一个高计 算复杂度的n p 完全问题，不便于实际应用。针对高计算复杂度这个问题，s h i 和m a l i k 提出了一种近似计算方法，但是考虑到高像素大分辨率动态图像和实际计算机的计算能 力，该近似计算方法在实际应用中也是很难得到应用的，那么这个算法只能用来计算小 尺寸图片，或者应用在高性能计算设备上。 1 3 本文研究问题 以图理论为基础的经典图像分割算法( 如归一化割方法) 对于大尺度的图像而言 其计算速度太慢复杂性太高，而且划分的稳定性极大地依赖于参数的选择，很难应用于 实际，而等周图像分割算法却不能充分利用求解线性方程组所得到的状态向量，且对于 多目标的图像进行处理时所采用的二分迭代会产生庞大的计算量，本文通过对多目标图 5 第一章引言 像的状态向量和等周率进行分析，在第三章提出了一种加速改进的k + 1 分迭代方式，经 分析和实验表明改进后方法比原算法分割在计算次数和计算时间上效率更高。在对等周 图像分割算法进行学习时，发现其中出现了最优化问题一一个2 进制的极小化问题，于 是对二进制编码的遗传算法进行了学习并尝试将遗传算法用于求解该极小化问题，虽然 结果不理想可是却是具有启发性的。 1 4 本章小结 本章首先简要介绍了图像及数字图像处理的主要目的与内容，然后对图像处理中图 像分割的研究背景和基于图理论的图像分割算法的研究现状做了简略的描述，最后提出 了本文所要研究的内容。 6 西北大学硕 ：学位论文 第二章图论及图的分割 以图为研究对象的图论发展始于2 0 世纪5 0 年代，是数学的一个分支，历史上图论 曾经被好多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉1 7 3 6 年 的论著中，他所考虑的原始问题有很强的实际背景。图论中的图是由一些给定的表示特 定事物的点以及连接某两点的线所构成的图形，其中某两点间的线表示相应两事物间某 种特定关系。 2 1 图的基本概念 2 1 1 图的起源 图论起源于著名的柯尼斯堡七桥问题【1 4 l 。该问题来自一个现实生活中的事例：当时 东普鲁士柯尼斯堡( 今俄罗斯加里宁格勒) 市区跨普列戈利亚河两岸，在河中心有两个 小岛，它们通过七条桥与两岸连接。在所有桥都只走一遍的前提下，如何把所有的桥都 走一遍? a h 图1 七桥问题示意图 莱昂哈德欧拉( l e o n h a r de u l e r ) 于1 7 3 5 年在圣彼得堡科学院发表了图论史上第 一篇重要文献，圆满地解决了这一问题，证明这种方法并不存在，也顺带解决了一笔画 问题。欧拉将实际的抽象问题简化为平面上的点与线的组合( 用一条线代表一座桥，用 点代表桥所连接的地区) ，如果从某点出发后最后再回到这点，那么这一点的线的数目 必须是偶数。 2 1 2 图的定义 图是一种拓扑结构图形，由若干代表某种事物的点和连接这两点的边构成，边通常 用来描述相应两事物间的一种特定的相互关系。 图g 是由集合v 和e 所构成的一种拓扑结构，记做：g = ( v ，e ) ；其中，v 是所有 顶点组成的非空有限集，e 是由边组成的有限集合。一对顶点由一条边相连，即 ecv v 。 7 第二二章图论及图的分割 下面给出了一个简单的图，图中的点来表示顶点，边由点间的连线表示。 j 一个简单图 图g 有以下几部分组成： ( 1 ) 顶点集 图的基本元素是顶点，代表图中相互关联的个体。如图2 中的i ，j 两个顶点，一般 习惯上用q ， ，j 表示，那么y ( g ) = 似，屹，坼，。v 1 ，k 】就表示顶点集，疗：i v l 表示顶点 个数。 ( 2 ) 边集 边也是图的基本元素，它是两个顶点问的关联，如图2 中，连接i ，j 两顶点的边 可表示为e j | = 化，v ，) ，表示顶点u 与v ，之间的联系。e ( g ) = 偏，e ：，) 是图g 所有边 组成的集合。m = l e i 即边的个数。有限图的边的数目也是有限的，无限图的边的个数是 无限的。 ( 3 ) 权 权代表了对应两个顶点间关系的紧密程度，用一个数值表示。如图2 中，表示 连接i ，j 两个顶点的边的对应的权值。任意一个有权图可以表示为g = v ，e ，w ) ， ( w 为图g 的权值矩阵) ，无权图是一种特殊的( 权值为1 ) 有权图。 2 1 3 图的几个基本概念 ( 1 ) 顶点的度 顶点的度是指与该顶点相关联所有边的个数。顶点u 的度用盔= w ( 勺) 表示。顶 ， 点度的大小反映了顶点与其它相邻顶点联系的紧密程度，度值较大的顶点往往是图的 “关键点 ，度值等于零的顶点被称为孤立点。权和度是图像分割中非常关键的两个参 考量，大度值对应边连接的两个顶点一般属于同一类，而小度值对应的顶点或者孤立点 则属于一类。 ( 2 ) 连通图和图的直径 8 图 两北大学硕 j 学位论文 在一个图中，如果存在一条从顶点u 到k 的有限顶点和边交替的序列 v l e l v ：e ：以一 一。屹，则称这是一个从u 到屹的途径。所有顶点都不重复的途径称为道路。 图中两个顶点是连通的是指这两个顶点间至少存在一条道路。一个图是连通的是指这个 图中任意一对顶点之间都至少有一条道路。图的连通性反映了图中各区域间的关联程 度。顶点h 到k 的所有道路的最小长度称为u 到的距离。所有顶点间距离的最大值称 为这个图的直径。图的直径是图的松散程度上限的一种表示。 ( 3 ) 图的阶和容量 图的阶是指图中顶点的个数，图内所有边的权值之和则被称之为图的容量。例如图 3 中子图g 1 的容量为v o l ( g ) = 画d l 。他们都是用来描述图的一种度量尺度。 ( 4 ) 子图和割 对于图g = v ，e ) ，g 1 一彤，巨) ，如果k v ，巨e ，则称g l 是g 的一个子图， 记做g l g 。 在下图中，图g 1 和图g 2 都是图g 的子图。 图3 对于子图g 1 。彤，巨，和g 2 一 屹，易 ， 补图。 子图 如果k 【j k v ，那么称图g 和图g ，互为 、一， 对于互补的子图，连接两个子图的边的集合被称做割集。割集s 是这样定义的：如 果把图g 中所有属于s 中的边去掉，g 就变成具有二分支的分离图，如果只去掉s 中 的部分边，图依旧是连通的。在图3 中，子图g | ，g 2 之间的虚线就是一个割集。割集 中所有边对应的权值之和称作割： c u t ( g 1 g 2 ) 2 矾若。6 2 ) 略 ( 2 1 ) 2 1 4 图的矩阵表示 任意一个图的顶点与边间的关联属性都可以用一个矩阵来表示，于是通过讨论这些 9 第一二章图论及图的分割 矩阵的属性，可以得到图的相关性质，最重要的是，对图的某些处理方法可以转化为对 矩阵的计算问题。 任意一个图g = v ，e ) ( 其中v = ，匕) ，e = 编，e ：，e r n ) 都可以用一个n n 阶矩阵a ( g ) 来表示。其第i 行第j 列的元素为： f 1 如果v ：与v i 邻接 o如果、| 与t 不邻接 ( 2 2 ) 如果图中的边带有权值，我们则用一个，l ，l 阶的矩阵w 来表示带权值的图，矩阵 元素的定义为： w 盯丁呱e i i 絮詈皂篓萋掉 ( 2 3 ) ”1 0如果v ：与v i 不邻接 r 7 图4 是由五个顶点组成的一个权值为1 的图，可以看出它对应的邻接矩阵是一个主 对角线元素为o 的对称矩阵，任一行或列的元素和等于相应顶点的度。对应的，若给定 一个主对角线上的元素为0 的对称矩阵a ，则有唯一的以a 为其邻接矩阵的图g 被确 定。 图4 五顶点图 可以看出图4 的邻接矩阵写法如下： ， v ， 二 a ( g ) = 匕 么 矿2 台矿4 台 01101 10 011 10 o11 011o1 11110 4 2 1 5 图的几个算法 下面是图理论的几个重要算法，是图分割的基础。 ( 1 ) d i j k s t r a 最短路径算法 1 0 ( 2 4 ) 两北人学硕i ：学位论文 著名的最短路径算法是d i j k s t r a 于1 9 5 9 年提出来的。在图理论中，经常需要寻找出 加权图中两个给定顶点之间长度最小的道路，称为最短路径问题。在图5 中，虚线部分 就是从顶点u 到顶点的一条最短路径( 长度为1 3 ) 。 图5 最短路径示意图 ( 2 ) 最小生成树算法 对于1 1 个顶点的图g = v ，e ，只需要n 1 条边就可以把图中全部顶点连接起来， 这样一个连通子图被称为生成树。在所有的生成树中，各边权值之和最小生成树称为最 小生成树。p r i m 算法和k r u s k a l 算法是所有构造最小生成树的算法中最著名的。图6 表 示的就是个带权值的图和它对应的一个最小生成树。 图6 生成树示惫图 ( 3 ) 图的割和最大流最小割算法 把图中所有顶点划分成两个集合，连接这两个集合的边集称作这个图的割，图7 中 的虚线就表示了这样的一个割。如果这两个子图分别包含一个源点( b ) 和一个汇点( d ) ， 则称这是个从源点( b ) 到汇点( d ) 的割。所有这些割中权值最小的称为最小割。 解决最小割问题一个基本方法就是寻找从源点( b ) 到汇点( d ) 的最小流。把连 接两个顶点的边看作是一根“水管”，这根“水管”的容量就由对应边的权值表示，最 大流就是从源点( b ) 到汇点( d ) 所能通过的最大的“水流量”。f o r d 和f u l k e r s o n l 2 1 1 指 出当“水流 流量达到最大极限时，那些充满了的“水管就是从源点( b ) 到汇点( d ) 的最小割。在所有解决最小割最大流的算法【1 4 】中最常见的是基于扩充路径的算法和1 3 0 1 第二章图论及图的分割 标记法。 图7 最大流最小割示意图 2 2 图的分割方法 把一个图分割成子图的方法很多，准则不同，那么得到的子图就可能有比较大的差 异。把一个图分割成若干个子图，对子图仍然可以进一步分割，最终得到一个由子图和 子图的子图构成的树状结构，那么何时终结，何时是我们需要的结果呢? 因此在对图进 行分割，首先要确定这个分割的终止条件，余下的就是一个最优化问题( 如何更高效的 结束分割) 。 在任意图g 中，连接两顶点的边的权值是衡量两顶点之间关系紧密程度一个很重要 参数。在图g 中，如果把所有顶点分割成l 个子集k ，k ，圪，那么该分割应