15.2: Paseos, senderos y senderos
- Page ID
- 118249
\( \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}\)Supongamos que\(G = (V,E)\) es una gráfica.
una secuencia finita\(v_0, e_1, v_1, e_2, \ldots, v_{n - 1}, e_n, v_n\) de elementos de\(V \cup E\text{,}\) con cada uno\(v_i \in V\) y cada uno de\(e_i \in E\text{,}\) tal manera que el borde\(e_i\) conecta vértices\(v_{i-1}\) y\(v_i\)
un paseo que termina en el mismo vértice en el que se inició (es decir,\(v_n = v_0\))
un paseo que no está cerrado (es decir,\(v_n \neq v_0\))
un paseo que no atraviesa ningún borde más de una vez
un paseo que no pasa por ningún vértice más de una vez, excepto posiblemente los puntos finales\(v_0,v_n\)
También podemos aplicar los adjetivos abiertos y cerrados a senderos y caminos.
Considera la gráfica en el Ejemplo 15.1.1.
- El “viaje” que encontramos en el ejemplo es un rastro de longitud máxima comenzando en el vértice\(C\text{.}\)
- Los paseos\(C,r_1,R,r_4,D\) y\(C,r_1,R,r_2,C\) son ambos caminos, el primero abierto y el segundo cerrado.
- El paseo no\(C,r_1,R,r_4,D,r_4,R\) es ni un sendero ni un sendero.
Considera la siguiente gráfica.
Esta gráfica tiene las siguientes propiedades.
- Todo sendero o sendero que\(v_1\) atraviese debe comenzar o terminar ahí pero no puede ser cerrado, excepto los caminos cerrados:
- \(v_1\text{;}\)
- \(v_1, e_1, v_2, e_1, v_1\text{;}\)
- \(v_2, e_1, v_1, e_1, v_2\text{;}\)
- Caminar\(v_1, e_1, v_2, e_5, v_3, e_4, v_4,\) es a la vez un sendero y un sendero.
- Caminar\(v_1, e_1, v_2, e_5, v_3, e_6, v_3, e_4, v_4,\) es un sendero pero no un sendero.
Consideremos de nuevo la gráfica en la Figura\(\PageIndex{1}\) del Ejemplo\(\PageIndex{2}\). ¿De\(v_3\) cuántos senderos\(v_4\) existen? ¿Cuántos de esos senderos son caminos? ¿Hay algún camino de\(v_3\) a\(v_4\) que no sean senderos?
Solución
¡Podemos resolver esto usando una gráfica! La gráfica en la Figura\(\PageIndex{1}\) se creó trazando todos los senderos posibles comenzando en\(v_3\) y terminando al\(v_4\text{,}\) moverse a través de un borde a la vez. Cada nodo en esta nueva gráfica (dirigida) está etiquetada con una caminata parcial que es una continuación de la caminata asignada al nodo por encima de él. Cada tramo en la gráfica se detiene cuando la caminata asociada que se sigue alcanza\(v_4\) y no se puede continuar sin repetir otro borde. Para ahorrar espacio en las etiquetas de nodo, hemos utilizado “...” para significar el paseo desde el nodo anterior.
Contando todos los nodos en la gráfica de Figura\(\PageIndex{2}\) que están etiquetados con un paseo que termina en\(v_4\text{,}\) vemos que hay diez senderos desde\(v_3\) hasta\(v_4\text{.}\) Además, podemos ver fácilmente que sólo tres de los senderos son caminos.
Podemos usar la misma técnica para trazar todos los caminos desde\(v_3\) hasta\(v_4\text{,}\) pero esta vez terminamos una pierna cuando no podemos movernos de un vértice sin repetir un vértice que ya está visitado en esa caminata. (Tenga en cuenta que el paseo\(v_3,e_6,v_3\) es un sendero, pero si extendemos este paseo de alguna manera ya no será un sendero).
Por lo que sólo hay tres caminos de\(v_3\) a\(v_4\text{,}\) y cada uno de ellos es un sendero.
Cada camino abierto es un sendero.
- Prueba
-
Demostraremos lo contrapositivo: un paseo que no es un sendero no puede ser un camino abierto. Entonces supongamos que\(W\) es un paseo en una gráfica, y que\(W\) atraviesa borde\(e\) dos veces.
\(e\)El caso es un bucle.
Después\(W\) pasa por el vértice incidente al\(e\) menos a tres veces, de ahí que no sea un camino.\(e\)El caso no es un bucle.
Escribir\(e=\{v,v'\}\text{.}\) Inicialmente, hay dos posibilidades a considerar. Si cada uno de los dos recorridos asumidos de\(e\) movimientos de\(v\) a\(v'\text{,}\) entonces\(W\) pasa por cada uno de al\(v,v'\) menos dos veces, y por lo tanto no es un camino. Si los dos recorridos asumidos de\(e\) moverse\(v\) hacia\(v'\) y\(v'\) hacia\(v\) respectivamente, entonces\(W\) pasa por al\(v\) menos dos veces. Si\(W\) atraviesa\(v\) dos veces porque empieza y termina ahí, entonces no\(W\) está abierto. Si\(W\) está abierto y atraviesa\(v\) dos veces, entonces no\(W\) es un camino. Entonces, en todo caso, no\(W\) es un camino abierto.
En la Actividad 15.1, se le pide crear contraejemplos de algunas declaraciones relacionadas con la proposición anterior.