15.3: Vértices, Gráficos y Componentes Conectados
- Page ID
- 118266
\( \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}\)un par de vértices\(v,v'\) tal que existe una caminata que comienza en\(v\) y termina en\(v'\)
cada par de vértices está conectado
Estar conectado es una relación simétrica entre vértices, y las caminatas que conectan vértices se pueden acortar a caminos.
Supongamos que\(v,v'\) son vértices en una gráfica. Entonces los siguientes son equivalentes.
- Los vértices\(v,v'\) están conectados.
- Existe una caminata que comienza en\(v\) y termina en\(v'\text{.}\)
- Existe un camino que comienza en\(v\) y termina en\(v'\text{.}\)
- Existe una caminata que comienza en\(v'\) y termina en\(v\text{.}\)
- Existe un camino que comienza en\(v'\) y termina en\(v\text{.}\)
- Idea de Prueba.
-
Como es habitual, demostramos la equivalencia de múltiples declaraciones utilizando un ciclo de implicaciones lógicas.
Declaración 1 implica Declaración 2.
Esta es la definición de vértices conectados.Declaración 2 implica Declaración 3.
Supongamos que\(v_0, e_1, v_1, \ldots, v_{n - 1}, e_n, v_n\) es un paseo con\(v_0 = v\) y\(v_n = v'\text{.}\) si este paseo no es un sendero, entonces hay un vértice repetido. Supongamos\(v_j = v_i\) con\(j \gt i\text{.}\) Entonces\ begin {ecuation*} v_0, e_1, v_1,\ ldots, v_ {i-1}, e_i, v_j, e_ {j+1},\ ldots, v_ {n - 1}, e_n, v_n\ end {ecuación*} también
es un paseo de\(v\) a\(v'\text{.}\) Seguir quitando vértices repetidos de esta manera hasta obtener una ruta.Declaración 3 implica Declaración 4.
Simplemente invierta el orden de los vértices y aristas en el camino de\(v\)\(v'\) a para obtener un paseo en la otra dirección.Declaración 4 implica Declaración 5.
Como antes, si la caminata de\(v'\) a no\(v\) es un camino, cada par de vértices repetidos se puede eliminar “recortando” la porción de la caminata entre ellos.Declaración 5 implica Declaración 1.
Revertir el camino de\(v'\)\(v\) a para obtener una caminata de\(v\) a satisfacer\(v'\text{,}\) así la definición de vértices conectados.
Una gráfica no conectada puede considerarse simplemente como una colección de subgrafías conectadas.
un subgrafo conectado de una gráfica que no está contenida en ningún subgrafo conectado más grande de esa gráfica
una subgráfica\(G'\) de una gráfica\(G\) que satisfaga lo siguiente:
- \(G'\)está conectado;
- si\(G''\) es un subgrafo de\(G\) tal que\(G''\) se conecta y\(G' \preceq G''\text{,}\) luego\(G'' = G'\)
Considerando la Figura\(\PageIndex{3}\) a continuación como una sola gráfica, hemos colocado los componentes conectados (de los cuales hay tres) en cajas.
Esta gráfica no conectada tiene otras subgráficas conectadas. Por ejemplo, el subgrafo que contiene solo los dos vértices más a la izquierda unidos por un solo borde es un subgrafo conectado. Pero ese grafo conectado no es un componente conectado porque es un subgrafo de un subgrafo conectado más grande.
Las dos gráficas de la Figura\(\PageIndex{4}\) son de hecho la misma gráfica, solo que con diferentes representaciones diagramáticas. En la segunda versión de la gráfica, nuevamente hemos identificado componentes conectados colocando cada uno de ellos en una caja.
Si una gráfica está conectada, entonces toda la gráfica es una subgrafía conectada más grande posible.
Al igual que en nuestra definición de trabajo, informalmente los componentes conectados de una gráfica\(G\) son los subgráficos “más grandes” de los\(G\) que están conectados. La segunda condición en la definición formal es sólo una forma positiva de afirmar la definición de trabajo. Haremos que la noción general de “mayor” sea más precisa de manera similar en el Capítulo 19 (ver la definición de elemento máximo, la Prueba de Elementos Máximos/Mínimos, así como el Ejemplo 19.5.3).
Si\(G = (V,E)\) está conectado y\( \vert V \vert = n\text{,}\) luego\(\vert E \vert \ge n - 1\text{.}\)
- Prueba
-
Por inducción (fuerte).
Estuche base\(n=1\).
Cada gráfico con un solo vértice está conectado y satisface\(\vert E \vert \ge 0\text{.}\)Paso de inducción.
Asumir\(k \ge 1\) y la afirmación es verdadera para todos\(n \le k\text{.}\) Let\(G = (V,E)\) Ser una gráfica conectada con\(k + 1\) vértices. Debemos mostrar\(\vert E \vert \ge k\text{.}\)Elegir arbitrariamente algún vértice\(v_0 \in V\text{,}\) y dejar que\(G' = (V', E')\) sea la gráfica obtenida a partir\(G\) de la eliminación\(v_0\) y todos los bordes incidentes a él. Desafortunadamente,\(G'\) podría no estar conectado. \(G_1', \ldots, G_\mathscr{l}'\)Dejen ser sus componentes conectados. Escribe\(G_i' = (V_i',E_i')\text{,}\) y deja\(n_i = \vert V_i' \vert\text{.}\) Luego cada uno\(G_i'\) está conectado y tiene como máximo\(k\) vértices, por lo que se aplica la hipótesis de inducción. También tenga en cuenta que\(n_1 + \cdots + n_\mathscr{l} = k\text{,}\) dado que cada vértice de\(G\) except\(v_0\) es parte de exactamente un subgrafo\(G_i'\text{.}\)
(a) Vértice “Extra”\(v_0\) y el subgrafo restante\(G'\text{.}\) 
b) Subgrafía\(G'\) split into connected components.Figura\(\PageIndex{6}\): Eliminando vértice “extra” que\(v_0\text{,}\) divide el subgrafo restante en componentes conectados. Por lo tanto, usando nuestra hipótesis de inducción podemos calcular
\ begin {align*}\ vert E\ vert & =\ vert E'\ vert +\ vert\ {\ text {bordes en} G\ text {incidente a} v_0\}\ vert\\ & =\ vert E_1'\ vert +\ cdots\ vert E_\ mathscr {l} '\ vert +\ vert\ {\ text {bordes en} G\ text {incidente a} v_0\}\ vert\\ &\ ge (n_1 - 1) +\ cdots + (n_\ mathscr {l} - 1) +\ vert\ {\ text { bordes en} G\ texto {incidente a} v_0\}\ vert\\ & = k -\ mathscr {l} +\ vert\ {\ texto {bordes en} G\ texto {incidente a} v_0\}\ vert. \ end {align*}
Sin embargo, ya que\(G\) está conectado,\(v_0\) debe ser el pegamento manteniendo las subgráficas\(\{G_i'\}\) juntas. Es decir, para cada uno debe\(i\) haber al menos un borde entre\(v_0\) y algún vértice de\(G_i'\text{.}\) Por lo tanto,\ begin {align*}\ vert E\ vert &\ ge k -\ mathscr {l} +\ vert\ {\ text {bordes en} G\ texto {incidente a} v_0\}\ vert\ &\ ge k -\ mathscr {l} +\ mathscr {l}\\\ & = k.\ end {align*}