如果我移除 AB 这条路,但保留 BC,那么 A 和 B 就无法直接通行了,但 B 和 C 仍然可以。这个“剩下”的部分就是一个亚图。 如果我移除 BC 这条路,留下 AB,那么 B 和 C 就不能直接通行,但 A 和 B 可以。这又是一个亚图。 如果我同时移除 AB 和 BC,那么就只剩下三个孤立的城市了。这也是一个亚图。
假设我们的地图上有四个城市 A, B, C, D,道路是 AB, BC, CD, DA (形成一个正方形)。这张地图是连通的,你可以从任何一个城市走到任何一个城市。
现在我们想找到“截”。
如果我们移除 AB 这条路。现在 A 和 B 不能直接去了,但 A 还能通过 ADCB 去 B,整个地图仍然是连通的。所以 {AB} 不是一个截。 如果我们移除 AB 和 CD 这两条路。现在 A 只能通过 AD 到 D,然后到 C,但无法直接到 B 了。B 只能通过 BC 到 C,无法直接到 A 了。而且,A 和 D 构成了一个连通块,B 和 C 构成了另一个连通块。原来的连通图现在分裂成了两个部分。所以,{AB, CD} 是一个截。 如果我们移除 BC 和 DA 这两条路。同样地,这也会把地图分成两部分。所以,{BC, DA} 也是一个截。