12.3: Caminos y Ciclos

Última actualización
Guardar como PDF

Page ID: 114470

Joy Morris
University of Lethbridge

$ \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}}} $

Recordemos la definición de un paseo. Como vimos en el Ejemplo 12.2.1, los vértices y aristas en una caminata no necesitan ser distintos.

Hay muchas circunstancias en las que tal vez no queramos permitir que se vuelvan a visitar aristas o vértices. La eficiencia es una posible razón para ello. Tenemos un nombre especial para un paseo que no permite volver a visitarse vértices.

Definición: Trayectoria

Un paseo en el que ningún vértice aparece más de una vez se llama camino.

Notación

Para$n ≥ 0$, una gráfica sobre$n + 1$ vértices cuyos únicos bordes son los utilizados en un camino de longitud$n$ (que es un paseo de longitud$n$ que también es un camino) se denota por$P_n$. (Observe que$P_0 \cong K_1$ y$P_1 \cong K_2$.)

Observe que si un borde apareciera más de una vez en un paseo, entonces ambos extremos también tendrían que aparecer más de una vez, por lo que un camino no permite que se vuelvan a visitar vértices o aristas.

Ejemplo$\PageIndex{1}$

En la gráfica

$clipboard_edb7270687d0dc73c8115c27e894fd21b.png$

$(a, f, c, h)$es un camino de longitud$3$. Sin embargo, no$(a, f, c, h, d, f)$ es un camino, aunque no se repitan aristas, ya que el vértice$f$ aparece dos veces. Ambos son paseos.

Proposición$\PageIndex{1}$

Supongamos que$u$ y$v$ están en el mismo componente conectado de una gráfica. Entonces cualquier$u − v$ caminata de mínima longitud es un camino. En particular, si hay un$u − v$ paseo, entonces hay un$u − v$ sendero.

Prueba

Ya que$u$ y$v$ están en el mismo componente conectado de una gráfica, hay un$u − v$ paseo.

Hacia una contradicción, supongamos que tenemos un$u − v$ paseo de mínima longitud que no es un camino. Por la definición de un camino, esto quiere decir que algún vértice$x$ aparece más de una vez en la caminata, por lo que la caminata se ve así:

\[(u = u_1, . . . , u_i = x, . . . , u_j = x, . . . , u_k = v),\]

y$j > i$. Observe que lo siguiente es también un$u − v$ paseo:

\[(u = u_1, . . . , u_i = x, u_{j+1}, u_{j+2}, . . . , u_k = v).\]

Dado que los vértices consecutivos fueron adyacentes en la primera secuencia, también son adyacentes en la segunda secuencia, por lo que la segunda secuencia es un paseo. La longitud de la primera caminata es$k − 1$, y la longitud de la segunda caminata es$k − 1 − (j − i)$. Ya que$j > i$, la segunda caminata es estrictamente más corta que la primera caminata. En particular, la primera caminata no fue una$u − v$ caminata de longitud mínima. Esta contradicción sirve para demostrar que cada$u − v$ caminata de mínima longitud es un camino.

Esto nos permite probar otro dato interesante que será útil más adelante.

Proposición$\PageIndex{2}$

La eliminación de una arista de una gráfica conectada nunca puede dar como resultado una gráfica que tenga más de dos componentes conectados.

Prueba

Dejar$G$ ser una gráfica conectada, y dejar$u_v$ ser un borde arbitrario de$G$. Si$G \setminus \{u_v\}$ está conectado, entonces solo tiene un componente conectado, por lo que satisface nuestra conclusión deseada. Así, asumimos en el resto de la prueba que no$G \setminus \{u_v\}$ está conectada.

Let$G_u$ denotar el componente conectado de$G \setminus \{u_v\}$ que contiene el vértice$u$, y let$G_v$ denotar el componente conectado de$G \setminus \{u_v\}$ que contiene el vértice$v$. Nuestro objetivo es mostrar que$G_u$ y$G_v$ son los únicos componentes conectados de$G \setminus \{u_v\}$.

Que$x$ sea un vértice arbitrario de$G$, y supongamos que$x$ es un vértice que no está adentro$G_u$. Ya que$G$ está conectado, hay un$u − x$ paseo en$G$, y por lo tanto por la Proposición 12.3.1 hay un$u − x$ camino en$G$. Como no$x$ está en$G_u$, este$u−x$ camino debe usar el borde$u−v$, por lo que debe comenzar con este borde ya que$u$ solo ocurre al inicio de la ruta. Por lo tanto, al eliminar el vértice$u$ desde el inicio de esta ruta, obtenemos una$v − x$ ruta que no usa el vértice$u$. Esta ruta no puede usar el borde$u_v$, por lo que debe seguir siendo una ruta en$G \setminus \{u_v\}$. Por lo tanto$x$ es un vértice en$G_v$.

Dado que$x$ fue arbitrario, esto demuestra que cada vértice de$G$ debe estar en uno u otro de los componentes conectados$G_u$ y$G_v$, por lo que hay como máximo dos componentes conectados de$G \setminus \{u_v\}$. Dado que$u_v$ era un borde arbitrario de$G$ y$G$ era un gráfico conectado arbitrario, esto muestra que eliminar cualquier borde de un gráfico conectado nunca puede resultar en un gráfico con más de dos componentes conectados.

Un ciclo es como un camino, excepto que comienza y termina en el mismo vértice. A las estructuras que llamaremos ciclos en este curso, a veces se las denomina circuitos.

Definición: Ciclo

Un paseo de longitud al menos$1$ en el que ningún vértice aparece más de una vez, salvo que el primer vértice es el mismo que el último, se denomina ciclo.

Notación

Para$n ≥ 3$, una gráfica sobre$n$ vértices cuyos únicos bordes son los utilizados en un ciclo de longitud$n$ (que es un paseo de longitud$n$ que también es un ciclo) se denota por$C_n$.

El requisito de que la caminata tenga longitud al menos$1$ sólo sirve para dejar claro que una caminata de un solo vértice no se considera un ciclo. De hecho, un ciclo en una gráfica simple debe tener al menos longitud$3$.

Ejemplo$\PageIndex{2}$

En la gráfica del Ejemplo 12.3.1,$(a, e, f, a)$ se encuentra un ciclo de longitud$3$, y$(b, g, d, h, c, f, b)$ es un ciclo de longitud$6$.

Aquí hay dibujos de algunos pequeños caminos y ciclos:

$clipboard_ea501d80f22da06bc918ea61e6a90363c.png$

Terminamos esta sección con una proposición cuya prueba quedará como ejercicio.

Proposición$\PageIndex{3}$

Supongamos que$G$ es una gráfica conectada. Si$G$ tiene un ciclo en el que$u$ y$v$ aparecen como vértices consecutivos (así$u_v$ es un borde de$G$) entonces$G \setminus \{u_v\}$ se conecta.

Ejercicio$\PageIndex{1}$

1) En la gráfica

$clipboard_ed28261d07020096cc0ed35c4b9e4e9f9.png$

(a) Encontrar un camino de longitud$3$.

(b) Encontrar un ciclo de duración$3$.

2) Demostrar que en una gráfica, cualquier caminata que comience y termine con el mismo vértice y tenga la menor longitud posible distinta de cero, debe ser un ciclo.

3) Proponer Proposición 12.3.3.

4) Demostrar por inducción que si cada vértice de una gráfica conectada en$n ≥ 2$ vértices tiene valencia$1$ o$2$, entonces la gráfica es isomórfica a$P_n$ o$C_n$.

5) Dejar$G$ ser una gráfica (simple) sobre$n$ vértices. Supongamos que$G$ tiene la siguiente propiedad: siempre que$u \nsim v$,$dG(u) + dG(v) ≥ n − 1$. Demostrar que$G$ está conectado.

Search

Text Color

Text Size

Margin Size

Font Type