知识卡片
割点与桥标记连通薄弱处
在无向图中,删除一个顶点及其相关边若使连通分支数增加,该顶点是割点,本书称关结点;删除一条边若使分支数增加,该边是桥。它们描述结构上的连接薄弱处,不必涉及边权大小。
02916的4、5为割点,(4,5)为桥。单删4后两部分是{1,2,3}与{5,6,7,8};单删5则是{1,2,3,4}与{6,7,8}。正文所写两组三元素集不能同时代表这两种“任删其一”结果。
无割点的连通部分与双连通概念相关,但具体边界/最小顶点数需按采用的定义说明;本章未给寻找割点/双连通分量的算法,不将此处定义当实现已完成。
201割点可提示模型中连接故障薄弱处,但只增冗余节点而不加形成替代路径的连接,并不能自动消除割点;实际故障域也需由建模覆盖。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
- · 割点与桥标记连通薄弱处
- · 问与答
原书出处 · 2 处
- · 查看原书依据
关结点。比如,在图11-4中,顶点4和5都是关结点,因为如果它们中的任意一个被移除,图就变成非连通的了。移除这些顶点后,图中拥有两个连通分支,{1,2,3}和{6,7,8}。如果移除某条边会使得图失去连通性,则称该边为桥。没有关结点的连通图称为双连通图。尽管图本身可能不是双连通的,但它仍然可能包含双
- · 查看原书依据
单点故障源。因此,如果位于关结点处的系统失效,其他结点上的系统就无法再互相通信了。因此在设计保持长时间连接的大型网络架构时,很重要的一点是要保证网络中没有关结点。可以通过在网络中放置冗余结点来解决这个问题。 问:考虑一下用图来对航线结构进行建模。航线是飞机在空中的高速公路。该结构包含两种类型的元素:
参考来源
- 位置:《算法精解:C语言描述》第11章《图的描述》(spine1321;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1288.html;u186-ch11-010)。
- 结论依据:186关结点/桥/双连通完整段与02916全部链接实读,逐一删除的分量保留剩余桥端点,明确正文结果简化的不准确处。
- 原始内容:关结点。比如,在图11-4中,顶点4和5都是关结点,因为如果它们中的任意一个被移除,图就变成非连通的了。移除这些顶点后,图中拥有两个连通分支,{1,2,3}和{6,7,8}。如果移除某条边会使得图失去连通性,则称该边为桥。没有关结点的连通图称为双连通图。尽管图本身可能不是双连通的,但它仍然可能包含双
- 位置:《算法精解:C语言描述》第11章《问与答》(spine1334;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1301.html;u201-ch11-010)。
- 结论依据:201割点可提示模型中连接故障薄弱处,但只增冗余节点而不加形成替代路径的连接,并不能自动消除割点;实际故障域也需由建模覆盖。
- 原始内容:单点故障源。因此,如果位于关结点处的系统失效,其他结点上的系统就无法再互相通信了。因此在设计保持长时间连接的大型网络架构时,很重要的一点是要保证网络中没有关结点。可以通过在网络中放置冗余结点来解决这个问题。 问:考虑一下用图来对航线结构进行建模。航线是飞机在空中的高速公路。该结构包含两种类型的元素: