15.4: Articulation vertices, bridges, and edge connectivity
- Page ID
- 83481
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)a vertex of a graph such that, if it were to be removed (along with any edges incident to it), the resulting subgraph would have more connected components than the original
an edge of a graph such that, if it were to be removed, the resulting subgraph would have more connected components than the original
In the graph of Figure \(\PageIndex{1}\), the central vertex that is common to both diamond-shaped subgraphs is an articulation vertex, as removing it and all edges incident to it would leave two unconnected “ears” on the outside of the two diamond shapes.
In the graph of Figure \(\PageIndex{2}\), edge \(e\) is a bridge, and each of \(v\) and \(v'\) are articulation vertices.
In the proof of Theorem 15.3.1, our conception was that “extra” vertex \(v_0\) was an articulation vertex, where removing it would create a subgraph \(G'\) that would be split into connected components \(G_1', \ldots, G_\ell'\text{.}\) (Though it is possible \(v_0\) is not an articulation vertex, if subgraph \(G'\) is connected.)
the minimum number of edges that must be removed from a connected graph to obtain a nonconnected subgraph
Edge connectivity measures redundancy in the graph, as each edge that can be removed without breaking the graph into nonconnected subgraphs must be incident to a pair of vertices that remain connected via some other walk through the graph.
The edge connectivity of the graph in Figure \(\PageIndex{1}\) is \(2\text{.}\)
A bridge represents a “single point of failure,” and every graph that contains a bridge has edge connectivity \(1\text{.}\) For example, removing the single edge \(e\) in the graph of Figure \(\PageIndex{2}\) breaks the graph into two nonconnected subgraphs.
Suppose \(G = (V,E)\) is a connected graph. Let \(n = \vert V \vert\text{,}\) \(e = \vert E \vert \text{,}\) and let \(d\) be the smallest degree of any of the vertices of \(G\text{.}\) Then the edge connectivity of \(G\) cannot be greater than either of the integers \(d\) or \(\lfloor 2 e / n \rfloor \text{.}\)
- Proof.
-
First, if \(v\) is a vertex of \(G\) with \(\text{deg} v = d\text{,}\) then removing all of the edges incident to \(v\) will cause \(v\) to become isolated and \(G\) to become nonconnected. So the edge connectivity of \(G\) cannot be greater than \(d\text{.}\)
Next, recall that the sum of the degrees of the vertices of \(G\) is equal to \(2e\) (Theorem 14.2.1). Using this, we have
\begin{equation*} 2e = \text{deg} v_1 + \text{deg} v_2 + \cdots + \text{deg} v_n \ge d + d + \cdots + d = nd \text{.} \end{equation*}
So \(d \le 2 e / n\text{.}\) The number \(2e/n\) is rational, but may not be an integer. However, \(d\) is definitely an integer, so we must have \(d \le \lfloor 2e/n \rfloor \text{.}\) Since we have already concluded that the edge connectivity of \(G\) is no greater than \(d\text{,}\) it also can be no greater than \(\lfloor 2 e / n \rfloor \text{.}\)
With \(n\) and \(e\) as in the statement of the theorem, \(2 e\) is equal to the sum of the degrees of the vertices (Theorem 14.2.1), so \(2 e / n\) is equal to the average degree of vertices in the graph.
Your tree fort rivals have set up a communication system of tin cans and strings. You have mapped out their network as in Figure \(\PageIndex{3}\). To minimize the risk of crab apple welts, what is the minimum number of strings you must cut to disrupt their communications?
Solution
There are \(6\) nodes and \(10\) edges, so Proposition \(\PageIndex{1}\) tells that the edge connectivity must be no greater than \(\lfloor 20/6 \rfloor = 3\text{.}\) By inspection, the edge connectivity is not \(1\) as there are no bridges. However, we may isolate either fort ALPHA or ECHO with two snips.