15.4: Vértices de articulación, puentes y conectividad de borde
- Page ID
- 118267
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\dsum}{\displaystyle\sum\limits} \)
\( \newcommand{\dint}{\displaystyle\int\limits} \)
\( \newcommand{\dlim}{\displaystyle\lim\limits} \)
\( \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}\)un vértice de una gráfica tal que, si fuera a ser eliminada (junto con cualquier borde incidente en ella), el subgrafo resultante tendría más componentes conectados que el original
un borde de una gráfica tal que, si fuera a ser eliminada, el subgrafo resultante tendría más componentes conectados que el original
En la gráfica de la Figura\(\PageIndex{1}\), el vértice central que es común a ambas subgráficas en forma de diamante es un vértice de articulación, ya que eliminarlo y todos los bordes incidentes en él dejaría dos “orejas” desconectadas en el exterior de las dos formas de diamante.
En la gráfica de la Figura\(\PageIndex{2}\), el borde\(e\) es un puente, y cada uno de\(v\) y\(v'\) son vértices de articulación.
En la prueba del Teorema 15.3.1, nuestra concepción era que el vértice “extra”\(v_0\) era un vértice de articulación, donde eliminarlo crearía una subgrafía\(G'\) que se dividiría en componentes conectados\(G_1', \ldots, G_\ell'\text{.}\) (Aunque es posible no\(v_0\) es un vértice de articulación, si subgrafo \(G'\)está conectado.)
el número mínimo de aristas que deben eliminarse de una gráfica conectada para obtener una subgráfica no conectada
La conectividad de borde mide la redundancia en la gráfica, ya que cada borde que se puede eliminar sin dividir el gráfico en subgráficos no conectados debe ser incidente con un par de vértices que permanecen conectados a través de algún otro recorrido por la gráfica.
La conectividad de borde de la gráfica en la Figura\(\PageIndex{1}\) es\(2\text{.}\)
Un puente representa un “punto único de falla”, y cada gráfico que contiene un puente tiene conectividad de borde\(1\text{.}\) Por ejemplo, al eliminar el borde único\(e\) en el gráfico de la Figura,\(\PageIndex{2}\) se divide el gráfico en dos subgráficos no conectados.
Supongamos que\(G = (V,E)\) es una gráfica conectada. Dejar\(n = \vert V \vert\text{,}\)\(e = \vert E \vert \text{,}\) y dejar\(d\) ser el grado más pequeño de cualquiera de los vértices de\(G\text{.}\) Entonces la conectividad de borde de\(G\) no puede ser mayor que cualquiera de los enteros\(d\) o\(\lfloor 2 e / n \rfloor \text{.}\)
- Comprobante.
-
Primero, si\(v\) es un vértice de\(G\) con\(\text{deg} v = d\text{,}\) entonces eliminar todos los bordes incidentes\(v\) a\(v\) hará que se aíslen y\(G\) se vuelvan desconectados. Así que la conectividad perimetral de\(G\) no puede ser mayor que\(d\text{.}\)
A continuación, recordemos que la suma de los grados de los vértices de\(G\) es igual a\(2e\) (Teorema 14.2.1). Usando esto, tenemos
\ begin {ecuación*} 2e =\ texto {deg} v_1 +\ texto {deg} v_2 +\ cdots +\ texto {deg} v_n\ ge d + d +\ cdots + d = nd\ texto {.} \ end {equation*}
Entonces\(d \le 2 e / n\text{.}\) El número\(2e/n\) es racional, pero puede que no sea un entero. No obstante,\(d\) es definitivamente un entero, así que debemos tener\(d \le \lfloor 2e/n \rfloor \text{.}\) Dado que ya hemos concluido que la conectividad edge de no\(G\)\(d\text{,}\) es mayor que tampoco puede ser mayor que\(\lfloor 2 e / n \rfloor \text{.}\)
Con\(n\) y\(e\) como en la declaración del teorema,\(2 e\) es igual a la suma de los grados de los vértices (Teorema 14.2.1), por lo que\(2 e / n\) es igual al grado promedio de vértices en la gráfica.
Tus rivales de tree fort han establecido un sistema de comunicación de latas y cuerdas. Has trazado su red como en la Figura\(\PageIndex{3}\). Para minimizar el riesgo de ronchas de manzana cangrejo, ¿cuál es el número mínimo de cuerdas que debes cortar para interrumpir sus comunicaciones?
Solución
Hay\(6\) nodos y\(10\) bordes, por lo que Proposition\(\PageIndex{1}\) dice que la conectividad de borde no debe ser mayor que\(\lfloor 20/6 \rfloor = 3\text{.}\) Por inspección, la conectividad perimetral no es\(1\) ya que no hay puentes. Sin embargo, podemos aislar ya sea fort ALPHA o ECHO con dos cortes.