断一条路:哪些地点会失联

逻辑思维 · 建议年级 5

在小型网络中识别唯一连接边并判断断开影响。

下载视频
展开视频文字稿
  1. A、B、C三村两两有路,构成三角形;D只通过道路C到D连接网络。
  2. 先看D的连接表,它只有C到D这一条边,没有第二条替代路线。
  3. 封闭C到D后,D没有任何出口,所以D与其余村失去联系。
  4. A、B、C之间的三条道路仍保留,任意两村仍可直接到达。
  5. 逐点做可达检查,只有D失败;这条唯一连接边控制了D的连通。
  6. 挑战换成E、F、G成三角形,G再连H。请划掉G到H并检查谁失联,小宝贝到你了。
讲解依据

逻辑思维

删边后从每点做可达遍历。

看一个例子

村A-B-C构成三角形,C还通过唯一道路连D。封闭C-D后,谁与其余村失联?

删C-D后D失联,ABC互通。删边后从每点做可达遍历。

马上试一题

X、Y、Z成三角形,W只通过Z-W连接网络。删Z-W后谁失联?