10.1: ¿Qué es un árbol?

Última actualización
Guardar como PDF

Page ID: 117149

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

Definición

Lo que distingue a los árboles de otros tipos de gráficas es la ausencia de ciertos caminos llamados ciclos. Recordemos que una trayectoria es una secuencia de aristas consecutivas en una gráfica, y un circuito es una trayectoria que comienza y termina en el mismo vértice.

Definición $\PageIndex{1}$: Cycle

Un ciclo es un circuito cuya lista de bordes no contiene duplicados. Se acostumbra usar$C_n$ para denotar un ciclo con$n$ bordes.

El ejemplo más simple de un ciclo en una gráfica no dirigida es un par de vértices con dos aristas que los conectan. Dado que los árboles no tienen ciclos, podemos descartar que todos los multígrafos tengan al menos un par de vértices conectados con dos o más aristas de consideración como árboles.

Los árboles pueden ser gráficos no dirigidos o dirigidos. Nos concentraremos en la variedad no dirigida en este capítulo.

Definición$\PageIndex{2}$: Tree

Un gráfico no dirigido es un árbol si está conectado y no contiene ciclos o auto-bucles.

Ejemplo$\PageIndex{1}$: Some Trees and Non-Trees

$clipboard_e2d93190b71a99cf6ebd48f7fe99e938e.png$ Figura$\PageIndex{1}$: Algunos árboles y algunos no árboles

Las gráficas i, ii y iii en la Figura$\PageIndex{1}$ son todas árboles, mientras que las gráficas iv, v y vi no son árboles.
A$K_2$ es un árbol. Sin embargo, si$n\geq 3\text{,}$ a no$K_n$ es un árbol.
En un sentido flojo, un árbol botánico es un árbol matemático. Por lo general, no hay ciclos en la estructura de ramas de un árbol botánico.
Las estructuras de algunos compuestos químicos son modeladas por un árbol. Por ejemplo, la Figura butano$\PageIndex{2}$ consta de cuatro átomos de carbono y diez átomos de hidrógeno, donde un borde entre dos átomos representa un enlace entre ellos. Un enlace es una fuerza que mantiene dos átomos juntos. El mismo conjunto de átomos se puede unir entre sí en una estructura arbórea diferente para darnos el compuesto isobutano Figura$\PageIndex{3}$. Hay algunos compuestos cuyas gráficas no son árboles. Un ejemplo es el benceno Figura$\PageIndex{4}$.

$clipboard_e284b3a49fd73248ac714941d5496193f.png$ Figura$\PageIndex{2}$: Butano

$clipboard_eada11e971dcf723e74f5e4ab0895fd21.png$ Figura$\PageIndex{3}$: Isobutano

$clipboard_e904e0976b0a5aca2761cf0114db29d4e.png$ Figura$\PageIndex{4}$: Benceno

Un tipo de gráfica que no es un árbol, sino que está estrechamente relacionado, es un bosque.

Definición$\PageIndex{3}$: Forest

Un bosque es una gráfica no dirigida cuyos componentes son todos árboles.

Ejemplo$\PageIndex{2}$: A Forest

La mitad superior de la Figura$\PageIndex{1}$ puede verse como un bosque de tres árboles. La gráfica (vi) en esta figura también es un bosque.

Condiciones para que una gráfica sea un árbol

Ahora examinaremos varias condiciones que son equivalentes a la que define un árbol. El siguiente teorema se utilizará como herramienta para demostrar que las condiciones son equivalentes.

Lema$\PageIndex{1}$

Dejar$G = (V, E)$ ser una gráfica no dirigida sin auto-bucles, y dejar$v_a, v_b\in V\text{.}$ Si existen dos caminos simples diferentes entre$v_a$ y$v_b\text{,}$ entonces existe un ciclo en$G\text{.}$

Prueba: Dejar$p_1= \left(e_1, e_2, \ldots , e_m \right)$ y$p_2=\left(f_1,f_2,\ldots , f_n\right)$ ser dos caminos simples diferentes de$v_a$ a$v_b\text{.}$ El primer paso que daremos es eliminar de$p_1$ y$p_2$ los bordes iniciales que son idénticos. Es decir, si$e_1= f_1\text{,}$$e_2= f_2, \dots \text{,}$$e_{j}= f_j\text{,}$ y$e_{j+1}\neq f_{j+1}$ borra los primeros$j$ bordes de ambos caminos. Una vez hecho esto, ambos caminos comienzan en el mismo vértice, lo llaman$v_c\text{,}$ y ambos aún terminan en$v_b\text{.}$ Ahora construimos un ciclo comenzando en$v_c$ y siguiendo lo que queda de$p_1$ hasta que primero nos encontramos con lo que queda de$p_2\text{.}$ Si este primer encuentro ocurre en el vértice$v_d\text{,}$ entonces el resto del ciclo se completa siguiendo la parte del reverso de$p_2$ que comienza en$v_d$ y termina en$v_c\text{.}$

Teorema$\PageIndex{1}$: Equivalent Conditions for a Graph to be a Tree

Dejar$G = (V, E)$ ser una gráfica no dirigida sin auto-bucles y$\lvert V \rvert =n\text{.}$ Los siguientes son todos equivalentes:

$G$es un árbol.
Por cada par de vértices distintos en$V\text{,}$ existe un camino sencillo único entre ellos.
$G$está conectado, y si$e\in E\text{,}$ entonces$(V, E-\{e\})$ está desconectado.
$G$no contiene ciclos, pero al agregar un borde, se crea un ciclo.
$G$está conectado y$\lvert E \rvert =n-1 \text{.}$

Prueba

Estrategia de Prueba. La mayor parte de este teorema se puede probar probando la siguiente cadena de implicaciones:$(1) \Rightarrow (2)\text{,}$$(2) \Rightarrow (3)\text{,}$$(3)\Rightarrow (4)\text{,}$ y$(4) \Rightarrow (1)\text{.}$ Una vez demostradas estas implicaciones, el cierre transitivo de$\Rightarrow$ on${1, 2, 3, 4}$ establece la equivalencia de las cuatro primeras condiciones. La prueba de que la Declaración 5 es equivalente a los cuatro primeros se puede hacer por inducción, la cual dejaremos al lector.

$(1) \Rightarrow (2)$(Indirecto). Supongamos que$G$ es un árbol y que existe un par de vértices entre los cuales o bien no hay camino o hay al menos dos caminos distintos. Ambas posibilidades contradicen la premisa de que$G$ es un árbol. Si no existe ninguna ruta,$G$ se desconecta, y si existen dos caminos, se puede obtener un ciclo por Teorema$\PageIndex{1}$.

$(2) \Rightarrow (3)\text{.}$Ahora usamos la Declaración 2 como premisa. Dado que cada par de vértices en$V$ están conectados por exactamente un camino,$G$ está conectado. Ahora bien, si seleccionamos cualquier borde$e$ en$E\text{,}$ él conecta dos vértices,$v_1$ y$v_2\text{.}$ By (2), no hay un camino simple que se conecte$v_1$ a$v_2$ otro que no sea$e\text{.}$ Por lo tanto, ningún camino en absoluto puede existir entre$v_1$ y$v_2$ en$(V, E - \{e\})\text{.}$ Por lo tanto$(V, E - \{e\})$ es desconectado.

$(3)\Rightarrow (4)\text{.}$Ahora vamos a suponer que la Declaración 3 es cierta. Debemos demostrar que no$G$ tiene ciclos y que sumar un borde a$G$ crea un ciclo. Utilizaremos una prueba indirecta para esta parte. Dado que (4) es una conjunción, por la Ley de DeMorgan su negación es una disyunción y debemos considerar dos casos. Primero, supongamos que$G$ tiene un ciclo. Entonces la eliminación de cualquier borde en el ciclo mantiene la gráfica conectada, lo que contradice (3). El segundo caso es que la adición de un borde a$G$ no crea un ciclo. Luego hay dos caminos distintos entre los vértices que conecta el nuevo borde. Por Lema$\PageIndex{1}$, entonces se puede crear un ciclo, lo cual es una contradicción.

$(4) \Rightarrow (1)$Supongamos que no$G$ contiene ciclos y que la adición de un borde crea un ciclo. Todo lo que necesitamos demostrar para verificar que$G$ es un árbol es que$G$ está conectado. Si no está conectado, seleccione dos vértices cualesquiera que no estén conectados. Si agregamos un borde para conectarlos, el hecho de que se cree un ciclo implica que se puede encontrar un segundo camino entre los dos vértices que está en la gráfica original, lo cual es una contradicción.

La definición habitual de un árbol dirigido se basa en si la gráfica no dirigida asociada, que se crea al “borrar” sus flechas direccionales, es un árbol. En la Sección 10.3 introduciremos el árbol enraizado, que es un tipo especial de árbol dirigido.

Ejercicios

Ejercicio $\PageIndex{1}$

Dados los siguientes conjuntos de vértices, dibuje todos los árboles no dirigidos posibles que los conecten.

$\displaystyle V_a= \{\text{right},\text{left}\}$
$\displaystyle V_b = \{+,-,0\}$
$V_c = \{\text{north}, \text{south}, \text{east}, \text{west}\}\text{.}$

Contestar: El número de árboles son: (a) 1, (b) 3, y (c) 16. Los árboles que conectan$V_c$ son:

$clipboard_eca2afcca5e5c296920fb939aa0f5d31d.png$ Figura$\PageIndex{5}$

Ejercicio$\PageIndex{2}$

¿Todos los árboles son planos? Si lo son, ¿puedes explicar por qué? Si no lo son, deberías poder encontrar un árbol no planar.

Ejercicio$\PageIndex{3}$

Demostrar que si$G$ es un gráfico simple no dirigido sin auto-bucles, entonces$G$ es un árbol si y solo si$G$ está conectado y$\lvert E \rvert = \lvert V \rvert - 1\text{.}$

Pista: Usar inducción en$\lvert E\rvert \text{.}$

Ejercicio$\PageIndex{4}$

Demostrar que si$G = (V, E)$ es un árbol y$e \in E\text{,}$ luego$(V, E - \{e\})$ es un bosque de dos árboles.
Demostrar que si$\left(V_1,E_1\right.$) y$\left(V_2,E_2\right)$ son árboles$e$ disjuntos y es un borde que conecta un vértice en$V_1$ un vértice en$V_2\text{,}$ entonces$\left(V_1\cup V_2, E_1\cup E_2\cup \{e\}\right)$ es un árbol.

Ejercicio$\PageIndex{5}$

Demostrar que cualquier árbol con al menos dos vértices tiene al menos dos vértices de grado 1.
Demostrar que si un árbol tiene$n$ vértices,$n \geq 4\text{,}$ y no es una gráfica de ruta,$P_n\text{,}$ entonces tiene al menos tres vértices de grado 1.

Contestar

Supongamos que$(V,E)$ es un árbol con$|V|≥2$, y todos menos posiblemente un vértice en$V$ tiene grado dos o más.
\[\begin{aligned}2|E|=\sum\limits_{v\in V}^{}\text{deg}(v)\geq 2|V|-1 &\Rightarrow |E|\geq |V|-\frac{1}{2} \\ &\Rightarrow |E|\geq |V| \\ &\Rightarrow (V,E)\text{ is not a tree.}\end{aligned}\]
La prueba de esta parte es similar a la parte a en que podemos inferir$2|E|≥2|V|−1$, utilizando el hecho de que un árbol no encadenado tiene al menos un vértice de grado tres o más.

Search

Text Color

Text Size

Margin Size

Font Type

Ejercicios