1. Rafael Villarroel
  2. notas de matemáticas discretas

Commits

Rafael Villarroel  committed 4c4f355

Se añadió material sobre árboles y una demostración del teorema de Cayley.

  • Participants
  • Parent commits 83815f0
  • Branches master

Comments (0)

Files changed (2)

File libro.pdf

Binary file modified.

File teoriadegraficas.tex

View file
 \section{Árboles}
 \label{sec:arboles}
 
+A partir de esta sección, dada una gráfica $G$ con $x,y\in V(G)$,
+denotaremos con $G+xy$ a la gráfica con:
+\begin{equation}
+  \label{eq:44}
+  V(G+xy)=V(G),\qquad E(G+xy)=E(G)\cup\{\{x,y\}\},
+\end{equation}
+y con $G-xy$ a la gráfica con:
+\begin{equation}
+  \label{eq:45}
+  V(G-xy)=V(G),\qquad E(G-xy)=E(G)\setminus\{\{x,y\}\}.
+\end{equation}
+
+Si $e=\{x,y\}$, también denotaremos a $G+xy$ como $G+e$ y a $G-xy$
+como $G-e$.
+
+Similarmente, denotaremos con $G-x$ a la gráfica con:
+\begin{equation}
+  \label{eq:46}
+  V(G-x)=V(G)\setminus\{x\},\qquad E(G-x)=\setof{\{u,v\}\in E(G)}{x\not\in\{u,v\}}
+\end{equation}
+
+También diremos que una gráfica es \emph{acíclica} cuando no tiene ciclos.
+
 \begin{definition}
   \label{definition:11}
-  Un \emph{árbol} es una gráfica conexa sin ciclos.
+  Un \emph{árbol} es una gráfica conexa y acíclica.
 \end{definition}
 
 \begin{theorem}
 Si $T$ es un árbol, los vértices de grado uno se llaman las
 \emph{hojas} de $T$.
 
+\begin{lemma}
+  \label{lemma:2}
+  Si $x$ es una hoja del árbol $T$, entonces $T-x$ es un árbol. Por
+  otro lado, sean $T$ es un árbol y $y\not\in V(T)$, Demuestra que si
+  la gráfica $T'$ se obtiene a partir de $T$ ańadiendo el vértice
+  $\{y\}$ y una arista uniendo $y$ con cualquier vértice de $T$,
+  entonces $T'$ es un árbol.
+\end{lemma}
+
+\begin{proof}
+  Ejercicio~\ref{exercises:6}.\ref{exercises:8}.
+\end{proof}
+
 \begin{theorem}
   \label{theorem:11}
   Dada una gráfica $T$, las siguientes afirmaciones son equivalentes:
   \begin{enumerate}
   \item $T$ es un árbol.
-  \item Para cualesquiera $u,v\in V(T)$, existe un único $u$-$v$
-    camino en $T$.
-  \item $T$ es conexa, y para todo $e\in E(T)$ se tiene que $T-e$ es
-    disconexa.
-  \item $T$ no tiene ciclos, y para todo $\{x,y\}\in V(T)^{(2)}-E(T)$
-    se tiene que $T+xy$ tiene un ciclo.
+  \item \label{item:10} Para cualesquiera $u,v\in V(T)$, existe un
+    único $u$-$v$ camino en $T$.
+  \item \label{item:11} $T$ es conexa, y para todo $e\in E(T)$ se
+    tiene que $T-e$ es disconexa.
+  \item \label{item:12} $T$ no tiene ciclos, y para todo $\{x,y\}\in
+    V(T)^{(2)}-E(T)$ se tiene que $T+xy$ tiene un ciclo.
   \end{enumerate}  
 \end{theorem}
 
 \begin{proof}
-  Si existieran dos vértices $u,v$ en $T$ con dos $u$-$v$-caminos
-  distintos, entonces habría un ciclo en $T$, pero $T$ es un árbol.
-
-  La hipótesis implica que $T$ es conexa. Supongamos que existe $e=uv$
-  una arista de $T$ con $T-e$ conexa. Entonces existe un
-  $u$-$v$-camino en $T-e$. Como $e$ define un $u$-$v$-camino en $T$,
-  tendríamos dos $u$-$v$-caminos distintos en $T$.
-
-  Si $T$ tuviera un ciclo $C$, entonces para toda $e\in C$ se tendría
-  que $T-e$ es conexa. Sean ahora $x$, $y$ vértices en $T$ no
-  adyacentes. Por hipótesis, $T$ es conexa, así que existe un
-  $x$-$y$-camino en $T$. Por lo tanto, existe un ciclo en $T+xy$.
-
-  Finalmente, demostremos que se tiene que $T$ es conexa. Sean $x$,
-  $y$ vértices de $T$. Entonces $T+xy$ tiene un ciclo $C$. Como $T$ no
-  tiene ciclos, tenemos que $xy\in C$, por lo que $C-xy$ define un
-  camino en $T$ de $x$ a $y$.
+  Supongamos que $T$ es un árbol. Si existieran dos vértices $u,v$ en
+  $T$ con dos $u$-$v$-caminos distintos, entonces habría un ciclo en
+  $T$ por el ejercicio~\ref{exercises:7}.\ref{ex:distintos}, lo cual
+  contradice que $T$ es un árbol y demuestra~\ref{item:10}.
+
+  Supongamos~\ref{item:10}. La hipótesis implica que $T$ es
+  conexa. Supongamos que existe $e=uv$ una arista de $T$ con $T-e$
+  conexa. Entonces existe un $u$-$v$-camino en $T-e$. Como $e$ define
+  un $u$-$v$-camino en $T$, tendríamos dos $u$-$v$-caminos distintos
+  en $T$, lo cual contradice~\ref{item:10} y demuestra~\ref{item:11}.
+
+  Supongamos~\ref{item:11}. Si $T$ tuviera un ciclo $C$, entonces para
+  toda $e\in C$ se tendría que $T-e$ es conexa. Sean ahora $x$, $y$
+  vértices en $T$ no adyacentes. Por hipótesis, $T$ es conexa, así que
+  existe un $x$-$y$-camino en $T$. Por lo tanto, existe un ciclo en
+  $T+xy$, lo cual demuestra~\ref{item:12}.
+
+  Finalmente, supongamos~\ref{item:12} y demostremos que $T$ es
+  conexa. Sean $x$, $y$ vértices de $T$. Entonces $T+xy$ tiene un
+  ciclo $C$. Como $T$ no tiene ciclos, tenemos que $xy$ es una arista
+  de $C$, por lo que $C-xy$ define un camino en $T$ de $x$ a $y$. Por
+  lo tanto $T$ es conexa y acíclica, es decir, es un árbol.
 \end{proof}
 
 \begin{theorem}
 \end{theorem}
 
 \begin{proof}
-  Por inducción en $n$.
+  Por inducción en $n$. El caso $n=1$ es inmediato, pues la única
+  gráfica con un vértice es un árbol y no tiene aristas.
+
+  Supongamos válido el teorema para $n$, y sea~$T$ un árbol con~$n+1$
+  vértices. Sea $x$ una hoja de~$T$. Por el lema~\ref{lemma:2}, $T-x$
+  es un árbol y tiene $n$ vértices. Por hipótesis de inducción, $T-x$
+  tiene~$n-1$ aristas. Como $T-x$ se obtuvo de $T$ removiendo una
+  arista, se tiene que $T$ tiene $n$ aristas, como queríamos demostrar.
+\end{proof}
+
+\begin{definition}
+  \label{definition:13}
+  Sea $G$ una gráfica. Un \emph{árbol generador} $T$ de $G$ es una
+  subgráfica de $G$ que es un árbol y tal que $|T|=|G|$.
+\end{definition}
+
+\begin{theorem}
+  \label{theorem:17}
+  Si $G$ es conexa, entonces $G$ tiene un árbol generador.
+\end{theorem}
+
+\begin{proof}
+  Ejercicio~\ref{exercises:6}.\ref{exercises:9}.
 \end{proof}
 
+\begin{exercises}
+  \label{exercises:6}
+\item Si $T$ es un árbol con al menos tres vértices, demuestra que un
+  vecino de una hoja no es una hoja.
+\item \label{exercises:8} Demuestra el lema~\ref{lemma:2}.
+\item Demuestra que si $G$ es una gráfica conexa, con $n$ vértices y
+  $n-1$ aristas, entonces $G$ es un árbol.
+\item Demuestra que si $G$ es una gráfica acíclica, con $n$ vértices y
+  $n-1$ aristas, entonces $G$ es un árbol.
+\item \label{exercises:9} Demuestra el teorema~\ref{theorem:17}. Mas
+  aún, demuestra que si $G$ es una gráfica conexa y $H$ es una
+  subgráfica acíclica de $G$ tal que $|H|\leq|G|$, existe un árbol
+  generador $T$ de $G$ que tiene a $H$ como subgráfica.
+\item Demuestra que si $G$ es una gráfica conexa con $n$ vértices y al
+  menos $n$ aristas, existe $e\in E(G)$ tal que $G-e$ es conexa.
+\end{exercises}
+
 \section{El teorema de Cayley}
 \label{sec:el-teorema-de}
 
- 
+La gráfica $K_{n}$ tiene vértices $V(K_{n})=\{1,2,\ldots,n\}$ y
+aristas $E(K_{n})=\setof{\{i,j\}}{1\leq i<j\leq n}$. En esta sección
+consideraremos el problema de contar la cantidad de árboles
+generadores de $K_{n}$.
+
+\begin{theorem}[Cayley]
+  \label{theorem:18}
+  Si $n\geq2$, $K_{n}$ tiene $n^{n-2}$ árboles generadores.
+\end{theorem}
+
+\begin{proof}[Primera demostración]
+  El caso $n=2$ es inmediato, así que en adelante supondremos $n\geq
+  3$. La demostración consiste en asignar a cada árbol generador de
+  $K_{n}$ de manera biunívoca una $(n-2)$-ada de números tomados del
+  conjunto $\{1,2,\ldots,n\}$, llamada el \emph{código de Prüfer} del
+  árbol.
+
+  Sea $T$ un árbol generador de $K_{n}$, y sea $x_{1}\in
+  \{1,2,\ldots,n\}$ la menor hoja de $T$. Sea $y_{1}$ el vecino de
+  $x_{1}$ en $T=T_{1}$. Sean ahora $x_{2}$ la menor hoja del árbol
+  $T-x_{1}=T_{2}$ y $y_{2}$ el vecino de $x_{2}$ en $T_{2}$. Es decir,
+  iniciando con $T_{1}=T$ para $k\geq 1$ obtenenos $x_{k}$ como la
+  menor hoja en $T_{k}$ y $y_{k}$ como el vecino de $x_{k}$ en
+  $T_{k}$, y para $k>1$ definimos $T_{k}=T_{k-1}-x_{k-1}$.
+  Enlistaremos del siguiente modo las $n-1$ aristas de $T$:
+  \begin{equation}
+    \label{eq:43}
+    \begin{pmatrix}
+      x_{1} & x_{2} & \cdots & x_{k-1} & x_{k} & \cdots & x_{n-2} & x_{n-1}\\
+      y_{1} & y_{2} & \cdots & y_{k-1} & y_{k} & \cdots & y_{n-2} & y_{n-1}\\
+    \end{pmatrix}.
+  \end{equation}
+  
+  El código de Prüfer de $T$ es entonces
+  $(y_{1},y_{2},\ldots,y_{n-2})$. Claramente la asignación $T\mapsto
+  (y_{1},y_{2},\ldots,y_{n-2})$ está bien definida. Debemos ahora
+  mostrar que cada $(n-2)$-ada de números en $\{1,2,\ldots,n\}$ es
+  código de Prüfer de un árbol generador de $K_{n}$. 
+
+  Consideremos las siguientes observaciones:
+  \begin{enumerate}
+  \item Necesariamente se tiene $y_{n-1}=n$.
+  \item $V(T_{k})=\{x_{k},x_{k+1},\ldots,x_{n-1},n=y_{n-1}\}$ para
+    todo $k=1,2,\ldots,n-1$.
+  \item $E(T_{k})=\setof{\{x_{i},y_{i}\}}{k\leq i\leq n-1}$.
+  \item El grado $d_{T}(v)$ de $v\in V(T)$ es la cantidad de veces que
+    $v$ aparece en la matriz~\eqref{eq:43}. Puesto que $v$ aparece
+    exactamente una vez en $(x_{1},x_{2},\ldots,x_{n-1},y_{n-1})$,
+    tenemos que $v$ aparece exactamente $d_{T}(v)-1$ veces en
+    $(y_{1},y_{2},\ldots,y_{n-2})$. En particular, las hojas de $T$
+    son exactamente los elementos de $\{1,2,\ldots,n\}$ que no están
+    en $\{y_{1},y_{2},\ldots,y_{n-2}\}$ y $x_{1}$ está unívocamente
+    determinado a partir de $\{y_{1},y_{2},\ldots,y_{n-2}\}$ como el
+    menor elemento de $\{1,2,\ldots,n\}$ que no está en
+    $\{y_{1},y_{2},\ldots,y_{n-2}\}$.
+  \item Similarmente, si $v\in V(T_{k})$, entonces $v$ aparece
+    $d_{T_k}(v)-1$ veces en $(y_{k},y_{k+1},\ldots,y_{n-1})$.
+  \item Por lo tanto, las hojas de $T_{k}$ son exactamente los
+    elementos de $\{1,2,\ldots,n\}$ que no están en
+    $\{x_{1},x_{2},\ldots,x_{k-1},y_{k},\ldots,y_{n-2}\}$. Hay al
+    menos un tal vértice, y $x_{k}$ está determinado como el menor de
+    ellos.
+  \end{enumerate}
+
+  Por las observaciones anteriores, se obtiene que cada $(n-2)$-ada de
+  números tomados de $\{1,2,\ldots,n\}$ es código de Prüfer de
+  exactamente un árbol con $n$ vértices, lo que concluye la demostración.
+\end{proof}
+
+
 %%% Local Variables: 
 %%% mode: latex
 %%% TeX-master: "libro"