树图(树图分析法)

  • A+
所属分类:疑问解答

树图分析法

树图分析法

事故树分析(AccidentTreeAnalysis,简称ATA)法又称故障树分析法(简称FTA),是安全系统工程的重要分析方法之一,是一种演绎的安全系统分析方法。
它是一种从系统到部件,再到零件,按“下降形”分析的方法。它从系统开始,通过由逻辑符号绘制出的一个逐渐展开成树状的分枝图,来分析故障事件(又称顶端事件)发生的概率。同时也可以用来分析零件、部件或子系统故障对系统故障的影响,其中包括人为因素和环境条件等在内。
它对系统故障不但可以做定性的而且还可以做定量的分析;不仅可以分析由单一构件所引起的系统故障,而且也可以分析多个构件不同模式故障而产生的系统故障情况。因为故障树分析法使用的是一个逻辑图,因此,不论是设计人员或是使用和维修人员都容易掌握和运用,并且由它可派生出其他专门用途的“树”。例如,可以绘制出专用于研究维修问题的维修树,用于研究经济效益及方案比较的决策树等。
由于故障树是一种逻辑门所构成的逻辑图,因此适合于用电子计算机来计算;而且对于复杂系统的故障树的构成和分析,也只有在应用计算机的条件下才能实现。
显然,故障树分析法也存在一些缺点。其中主要是构造故障树的多余量相当繁重,难度也较大,对分析人员的要求也较高,因而限制了它的推广和普及。在构造故障树时要运用逻辑运算,在其未被一般分析人员充分掌握的情况下,很容易发生错误和失察。例如,很有可能把重大影响系统故障的事件漏掉;同时,由于每个分析人员所取的研究范围各有不同,其所得结论的可信性也就有所不同。
定性分析
找出导致顶事件发生的所有可能的故障模式,既求出故障的所有最小割集(MCS)。
定量分析
主要有两方面的内容:一是由输入系统各单元(底事件)的失效概率求出系统的失效概率;二是求出各单元(底事件)的结构重要度,概率重要度和关键重要度,最后可根据关键重要度的大小排序出最佳故障诊断和修理顺序,同时也可作为首先改善相对不大可靠的单元的数据。

树图区块链

树图区块链

树图又称

树图又称

树图的运用

树图的运用

树和图是两种常见的数据结构,在计算机技术应用十分广泛,他们也是两种思考问题的方式,常用于结局实际问题。树最直观的用途就是如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用,如在编译源程序如下时,可用树表示源源程序如下的语法结构。在数据库系统中,树型结构也是信息的重要组织形式之一,一切具有层次关系的问题都可用树来描述。数据结构的图就是实际情况的抽象,即逻辑模型,然后通过计算机编程来解决问题。比如一个很复杂的地图,有很多城市,有很多路,如何找出最短路径呢?当然是用计算机来算了,你就得用图来表示等等,很多用途,如果你学习数学建模,你会经常遇到他们的好好学吧

什么是树图

什么是树图

树状图 dendrogram
亦称树枝状图。树形图是数据树的图形表示形式,以父子层次结构来组织对象。是枚举法的一种表达方式。
为了用图表示亲缘关系,把分类单位摆在图上树枝顶部,根据分枝可以表示其相互关系,具有二次元和三次元。在数量分类学上用于表型分类的树状图,称为表型树状图(phenogram),掺入系统的推论的称为系统树状图(cladogram)以资区别。表型树状图是根据群析描绘的,系统树状图是根据一种模拟的假定的性状进化方向即用电子计算机描绘的。
树状图也是初中学生学习概率问题所需要画的一种图形。
如何画树状图

最小树形图,就是给有向带权图中指定一个特殊的点v,求一棵有向生成树T,使得该有向树的根为v,并且T中所有边的总权值最小。最小树形图的第一个算法是1965年朱永津和刘振宏提出的复杂度为O(VE)的算法。
  判断是否存在树形图的方法很简单,只需要以v为根作一次图的遍历就可以了,所以下面的算法中不再考虑树形图不存在的情况。
  在所有操作开始之前,我们需要把图中所有的自环全都清除。很明显,自环是不可能在任何一个树形图上的。只有进行了这步操作,总算法复杂度才真正能保证是O(VE)。
  首先为除根之外的每个点选定一条入边,这条入边一定要是所有入边中最小的。现在所有的最小入边都选择出来了,如果这个入边集不存在有向环的话,我们可以 证明这个集合就是该图的最小树形图。这个证明并不是很难。如果存在有向环的话,我们就要将这个有向环所称一个人工顶点,同时改变图中边的权。假设某点u在 该环上,并设这个环中指向u的边权是in[u],那么对于每条从u出发的边(u, i, w),在新图中连接(new, i, w)的边,其中new为新加的人工顶点; 对于每条进入u的边(i, u, w),在新图中建立边(i, new, w-in[u])的边。为什么入边的权要减去in[u],这个后面会解释,在这里先给出算法的步骤。然后可以证明,新图中最小树形图的权加上旧图中被收缩 的那个环的权和,就是原图中最小树形图的权。
  上面结论也不做证明了。现在依据上面的结论,说明一下为什么出边的权不变,入边的权要减去in [u]。对于新图中的最小树形图T,设指向人工节点的边为e。将人工节点展开以后,e指向了一个环。假设原先e是指向u的,这个时候我们将环上指向u的边 in[u]删除,这样就得到了原图中的一个树形图。我们会发现,如果新图中e的权w'(e)是原图中e的权w(e)减去in[u]权的话,那么在我们删除 掉in[u],并且将e恢复为原图状态的时候,这个树形图的权仍然是新图树形图的权加环的权,而这个权值正是最小树形图的权值。所以在展开节点之后,我们 得到的仍然是最小树形图。逐步展开所有的人工节点,就会得到初始图的最小树形图了。
  如果实现得很聪明的话,可以达到找最小入边O(E),找环 O(V),收缩O(E),其中在找环O(V)这里需要一点技巧。这样每次收缩的复杂度是O(E),然后最多会收缩几次呢?由于我们一开始已经拿掉了所有的 自环,我门可以知道每个环至少包含2个点,收缩成1个点之后,总点数减少了至少1。当整个图收缩到只有1个点的时候,最小树形图就不不用求了。所以我们最 多只会进行V-1次的收缩,所以总得复杂度自然是O(VE)了。由此可见,如果一开始不除去自环的话,理论复杂度会和自环的数目有关。

历史上的今天:

avatar

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: