12.2: Paseos y conectividad

Última actualización
Guardar como PDF

Page ID: 114457

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

Las gráficas se pueden conectar o desconectar. Intuitivamente, esto corresponde a que la red esté conectada o desconectada — ¿es posible viajar de cualquier nodo a cualquier otro nodo? Cuando se desconecta una gráfica (o red), se ha dividido en cierto número de componentes conectados separados, las piezas que aún están conectadas.

Dado que esto es matemática, requerimos definiciones más formales, para asegurar que los significados no estén abiertos a malentendidos. Antes de que podamos definir la conectividad, necesitamos el concepto de un paseo en una gráfica.

Definición: Walk

Un paseo en una gráfica$G$ es una secuencia de vértices$(u_1, u_2, . . . , u_n)$ tal que para cada uno$1 ≤ i ≤ n − 1$, tenemos$u_i ∼ u_{i+1}$. (Es decir, los vértices consecutivos en la caminata deben ser adyacentes.)

Un$u − v$ paseo$G$ es un paseo con$u_1 = u$ y$u_n = v$. (Es decir, una caminata que comienza en$u$ y termina en$v$.)

Ahora podemos definir lo que significa que una gráfica esté conectada.

Definición: Word

La gráfica$G$ con conjunto de vértices$V$ está conectada si por cada$u$$v ∈ V$,, hay una$u − v$ caminata.

El componente conectado de$G$ que contiene el vértice$u$, es

\[\{v ∈ V | \text{ there is a } u − v \text{ walk.}\}\]

Esta definición de componente conectado parece depender significativamente de la elección del vértice$u$. De hecho, sin embargo, estar en el mismo componente conectado de$G$ es una relación de equivalencia en los vértices de$G$, por lo que los componentes conectados de$G$ son una propiedad de$G$ sí mismo, en lugar de depender de elecciones particulares de vértices. No vamos a pasar por una prueba formal de que estar en el mismo componente conectado es una relación de equivalencia (dejamos esto como un ejercicio a continuación), sino que pasaremos por la prueba de una proposición que está estrechamente relacionada.

Proposición$\PageIndex{1}$

Dejar$G$ ser una gráfica, y dejar$u$,$v$,$w ∈ V (G)$. Supongamos que$v$ y$w$ están en el componente conectado de$G$ que contiene el vértice$u$. Entonces$w$ está en el componente conectado de$G$ que contiene el vértice$v$.

Prueba

Dado que$v$ y$w$ están en el componente conectado de$G$ que contiene el vértice$u$, por definición hay un$u − v$ paseo, y un$u − w$ paseo. Que$(u = u_1, u_2, . . . , u_k = w)$ sea un$u − w$ paseo, y que$(u = v_1, v_2, . . . , v_m = v)$ sea un$u − v$ paseo.

Necesitamos mostrar que$w$ está en el componente conectado de$G$ que contiene el vértice$v$; por definición, esto equivale a mostrar que hay un$v − w$ paseo. Considere la secuencia de vértices:

\[(v = v_m, v_{m−1}, . . . , v_1 = u = u_1, u_2, . . . , u_k = w).\]

Dado que$(u = v_1, v_2, . . . , v_m = v)$ es un$u − v$ paseo, los vértices consecutivos son adyacentes, por lo que los vértices consecutivos en la primera parte de la secuencia dada (de$v_m$ a través$v_1 = u$) son adyacentes. De igual manera, dado que$(u = u_1, u_2, . . . , u_k = w)$ es un$u − w$ paseo, los vértices consecutivos son adyacentes, por lo que los vértices consecutivos en la última parte de la secuencia dada (de$u = u_1$ a través$u_k$) son adyacentes. Por lo tanto, la secuencia dada es de hecho un$v − w$ paseo, según se desee.

Al hablar de caminatas, es conveniente tener una terminología estándar para describir la duración de la caminata.

Definición: Longitud de una Caminata

La longitud de una caminata es una menos que el número de vértices en la caminata. Así, si pensamos en una caminata como una secuencia de aristas (formadas por pares consecutivos de vértices de la caminata), la longitud de la caminata es el número de aristas en la caminata.

Desafortunadamente, existe cierto desacuerdo entre los matemáticos en cuanto a si la longitud de una caminata debe usarse para significar el número de vértices en la caminata, o el número de aristas en la caminata. Utilizaremos esta última convención a lo largo de este curso porque es consistente con la definición de la duración de un ciclo (que se introducirá en la siguiente sección). Sin embargo, debes tener en cuenta que podrías encontrar la otra convención utilizada en otras fuentes.

A veces es obvio que una gráfica está desconectada de la forma en que se ha dibujado, pero a veces es menos evidente. En el siguiente ejemplo, es posible que no note inmediatamente si la gráfica está conectada o no.

Ejemplo$\PageIndex{1}$

Considera la siguiente gráfica.

$clipboard_e76bfaad41101e54056e7b89a37bc8338.png$

Encuentra$a$ paseo de longitud$4$ desde$a$ hasta$f$. Encuentre el componente conectado que contiene$a$. ¿Está conectada la gráfica?

Solución

Un paseo de longitud$4$ de$a$ a$f$ es$(a, c, a, c, f)$. (Observe que los vértices y aristas utilizados en una caminata no necesitan ser distintos). Recuerda que la longitud de esta caminata es el número de aristas utilizadas, ¡que es uno menos que el número de vértices en la secuencia!

El componente conectado que contiene$a$ es$\{a, c, e, f\}$. Hay caminatas desde$a$ hasta cada uno de estos vértices, pero no hay aristas entre ninguno de estos vértices y ninguno de los vértices$\{b, d, g, h\}$.

Como no hay paseo de$a$ a$b$ (por ejemplo), la gráfica no está conectada.

Ejercicio$\PageIndex{1}$

1) Demostrar que estar en el mismo componente conectado de$G$ es una relación de equivalencia en los vértices de cualquier gráfica$G$.

2) ¿Está conectada la siguiente gráfica? Encuentre el componente conectado que contiene$a$. Encuentra un paseo de longitud$5$ desde$a$ hasta$f$.

$clipboard_e5f46635a2385dba84b3ebf893af89f7f.png$

3) ¿Está conectada la siguiente gráfica? Encuentre el componente conectado que contiene$a$. Encuentra un paseo de longitud$3$ desde$a$ hasta$d$.

$clipboard_e3b5e5832ed5aea593050e9ba09c97bbc.png$

4) Usa el lema de apretón de manos de Euler para probar (por contradicción) que si$G$ es una gráfica conectada con$n$ vértices y$n − 1$ aristas$n ≥ 2$, y, entonces$G$ tiene al menos$2$ vértices de valencia$1$.

[Pista: ¿Qué implica$G$ estar conectado$d(v)$ para algún vértice$v$ de$G$?]

5) Fijar$n ≥ 1$. Demostrar por inducción en$m$ que para cualquier$m ≥ 0$, una gráfica con$n$ vértices y$m$ aristas tiene al menos componentes$n − m$ conectados.

Search

Text Color

Text Size

Margin Size

Font Type