人工神经网络图论.pptVIP

4．最小生成树及算法1)树的定义与树的特征定义连通且不含圈的无向图称为树．常用T表示.树中的边称为树枝.树中度为1的顶点称为树叶.孤立顶点称为平凡树.平凡树定理2设G是具有n个顶点的图，则下述命题等价：1)G是树（G无圈且连通）；2)G无圈，且有n-1条边；3)G连通，且有n-1条边；4)G无圈，但添加任一条新边恰好产生一个圈;5)G连通，且删去一条边就不连通了（即G为最最小连通图）；6)G中任意两顶点间有唯一一条路.2）图的生成树定义若T是包含图G的全部顶点的子图,它又是树,则称T是G的生成树.图G中不在生成树的边叫做弦.定理3图G=(V,E)有生成树的充要条件是图G是连通的.证明必要性是显然的.（II）找图中生成树的方法可分为两种：避圈法和破圈法A避圈法:深探法和广探法B破圈法A避圈法定理3的充分性的证明提供了一种构造图的生成树的方法.这种方法就是在已给的图G中，每步选出一条边使它与已选边不构成圈，直到选够n-1条边为止.这种方法可称为“避圈法”或“加边法”在避圈法中，按照边的选法不同，找图中生成树的方法可分为两种：深探法和广探法.a)深探法若这样的边的另一端均已有标号，就退到标号为步骤如下：i)在点集V中任取一点u,ii)若某点v已得标号，检端是否均已标号.若有边vw之w未标号,则给w代v，重复ii).i-1的r点,以r代v,重复ii),直到全部点得到标号为止.给以标号0.查一端点为v的各边，另一w以标号i+1，记下边vw.令例用深探法求出下图10的一棵生成树图1001234567891011121313a)深探法图100123456789101112步骤如下：若这样的边的另一端均已有标号，就退到标号为i)在点集V中任取一点u,ii)若某点v已得标号，检端是否均已标号.若有边vw之w未标号,则给w代v，重复ii).i-1的r点,以r代v,重复ii),直到全部点得到标号为止.给u以标号0.查一端点为v的各边，另一w以标号i+1，记下边vw.令例用深探法求出下图10的一棵生成树3b)广探法步骤如下：i)在点集V中任取一点u,ii)令所有标号i的点集为是否均已标号.对所有未标号之点均标以i+1,记下这些iii)对标号i+1的点重复步步骤ii)，直到全部点得到给u以标号0.Vi,检查[Vi,V\Vi]中的边端点边.例用广探法求出下图10的一棵生成树图101012213212234标号为止.图10Dijkstra算法:求G中从顶点u0到其余顶点的最短路.1)置，对，，且.2)对每个，用代替，计算，并把达到这个最小值的一个顶点记为，置3)若，则停止；若，则用i+1代替i，并转2).Dijkstra算法:求G中从顶点u0到其余顶点的最短路.1)置，对，，且.2)对每个，用代替，计算，并把达到这个最小值的一个顶点记为，置3)若，则停止；若，则用i+1代替i，并转2).Dijkstra算法:求G中从顶点u0到其余顶点的最短路.1)置，对，，且.2)对每个，用代替，计算，并把达到这个最小值的一个顶点记为，置3)若，则停止；若，则用i+1代替i，并转2).Dijkstra算法:求G中从顶点u0到其余顶点的最短路.1)置，对，，且