选择特殊符号
选择搜索类型
请输入搜索
由图遍历的过程中经过的边加上图的所有顶点所构成的子图。
(1)n个顶点的连通子图的生成树是一个极小连通子图,它包含图中所有顶点和n-1条边(但有n-1条边的图不一定是生成树)。
(2)生成树中任意两个顶点间的路径是唯一的。
生成树T各边的权值总和称为该树的权。
将权最小的生成树称为图的最小生成树。
Krusal算法和Prim算法是两个构造最小生成树的著名算法。
设为 N=(V,E,C)连通网,TE是N的最小支撑树的边的集合。
① 算法开始时, U= {u o }(u o ∈ V), TE= ○ ;
② 找到满足
weight(u,v)=min{weight(u 1 ,v 1 )| u 1 ∈ U, v 1 ∈ V-U }, 的边,把它并入集合
TE中,v同时并入U。
③ 反复执行② ,直至 V=U 时终止算法。
普里姆算法执行过程示例
由上述图解算法的过程知,构造的最小生成树不一定唯一,但最小生成树的权值之和一定是相同的 。
《 建筑抗震设计规范》对现浇钢筋混凝土大跨度框架的定义在其“表6.1.2 现浇钢筋混凝土房屋的抗震等级”的“注3”中规定:”大跨度框架指跨度不小于18m的框架“。《钢结构设计规范》对大跨度屋盖结构的定...
根据普通人活动的空间来确定,一字型淋浴房最小尺寸一般80cm×80cm,可以根据空间进行合理的设定,而对于淋浴房来说,这个尺寸就不能再小了,再小洗澡的空间受到了限制,活动不开。而对于半弧形的淋浴房来说...
主要是看卫生间空间的大小,一般最小的可以做到310MM的。 有330*360 550*330 6...
最小生成树与构造造价最低通讯网
如何构造造价最低的通讯网络,是信息社会面临的共同问题,本文从普里姆(prim)求解最小生成树的基本思想入手,给出了让计算机自动构造耗费最低的通讯网的方法。
粉细砂层浅埋段斜井暗挖最小支护力研究
粉细砂层中浅埋暗挖段支护应力的计算是工程施工中经常遇到的问题。将盾构施工中常用的楔形体受力模型,通过分析改进,运用于斜井井筒开凿,并推导出相应的计算公式。开挖面支护应力的大小取决于埋藏深度、土体本身强度、井筒与水平面夹角以及开挖面尺寸等多种因素。
一个网络图可以有多个生成树.记N的所有生成树的集合为:
设
则称 T * 为网络N的一棵最小树树形图,简称最小树。
求最小树的两种方法,是避圈法与破圈法 。
从网络图中任意节点开始寻找与该节点关联的权数最小的边,使之与已选边不构成为圈,直到选够n-1条边为止。
① 在网络图中寻找一个圈。若不存在圈,则已经得到最短树或网络不存在最短树;
② 去掉该圈中权数最大的边;
反复重复 ① ② 两步,直到最小树。
将图中所有边按权值从小到大排列,依次选所剩最小的边加入边集 T,只要不和前面加入的边构成回路,直到 T 中有 n-1 条边,则 T 是最小生成树。
树形图的概念
无圈且连通的无向图称为树。树一般记为T。作为树定义还可以有以下几种表述:
(1) T 连通且无圈或回路;
(2) T 无圈且有n-1条边(如果有n个结点);
(3) T 连通有n-1条边;
(4) T 无回路,但不相邻的两个结点之间联以一边,恰得一个圈;
(5) T 连通,但去掉T 的任意一条边,T 就不连通了;(亦即在点集合相同的图中,树是含边数最少的
连通图。)
(6) T 的任意两个结点之间恰有一条初等链。