Flows and Connectivity · Connectivity
Lesson 1
In transport and communication networks, it is important not only that the network is connected, but also that it remains so even after the removal of several vertices or edges (that is, road closures, cable breaks, or server failures). This motivates the following definitions.
A bridge in an undirected graph is an edge whose removal increases the number of connected components. It is easy to see that an edge is a bridge if and only if it lies on no cycle.
Problem. Mark the bridges.
5 points
\(\{5, 8\}\)
\(\{1, 5\}\)
\(\{12, 13\}\)
\(\{8, 9\}\)
\(\{2, 7\}\)
\(\{14, 15\}\)