Commits

Rafael Villarroel committed a9613f3

Se añadió material sobre caminos, conexidad, subgráficas. También ejercicios.

  • Participants
  • Parent commits 8861add

Comments (0)

Files changed (3)

libro.pdf

Binary file modified.
 %%% TeX-master: t
 %%% TeX-PDF-mode: t
 %%% TeX-source-correlate-mode: t
+%%% eval: (set-input-method "spanish-prefix")
 %%% End: 

teoriadegraficas.tex

 \begin{definition}
   \label{definition:2}
   Una gráfica $H$ es \emph{subgráfica} de $G$ si $V(H)\subseteq V(G)$
-  y $E(H)\subseteq E(G)$.
+  y $E(H)\subseteq E(G)$. La subgráfica $H$ de $G$ es \emph{inducida}
+  si $\{x,y\}\subseteq V(H)^{(2)}\cap E(G)$ implica $\{x,y\}\in E(H)$.
 \end{definition}
 
 Por ejemplo, la gráfica $H$ de la figura~\ref{fig:57} es subgráfica de
-la gráfica $G$ de la figura~\ref{fig:56}.
+la gráfica $G$ de la figura~\ref{fig:56}. No es una subgráfica
+inducida, ya que los vértices $1,2$ están en $H$ y forman arista en
+$G$, pero no forman arista en $H$.
+
 \begin{figure}[htb]
   \centering
   \begin{minipage}[t]{0.4\linewidth}
   \end{minipage}
 \end{figure}
 
+Una subgráfica inducida está determinada por su conjunto de
+vértices. A la subgráfica de $G$ inducida por $X\subseteq V(G)$ se le
+denota con $G[X]$.
+
+\begin{definition}
+  \label{definition:5}
+  Si $x\in V(G)$, definimos \emph{la vecindad} de $x$, denotada
+  $N_{G}(x)$, a la subgráfica de $G$ inducida por $\setof{y\in
+    V(G)}{y\sim x}$. El \emph{grado} $d(x)$ de $x$ es $|N_{G}(x)|$.
+\end{definition}
+
 \begin{definition}
   \label{definition:6}
   Una gráfica $B$ es \emph{bipartita} si existen conjuntos ajenos y no
 
 \begin{definition}
   \label{definition:5}
-  Una gráfica $G$ es \emph{conexa} si para todo par de vértices $u,v$ en
-  $G$ existe un $u$-$v$~camino en $G$.
+  Una gráfica $G$ es \emph{conexa} si para todo par de sus vértices
+  $u,v$ existe un $u$-$v$~camino en $G$.
 \end{definition}
 
 Por ejemplo, la gráfica $G$ de la figura~\ref{fig:56} es conexa, pero
   \end{equation}
 \end{definition}
 
+\begin{proposition}
+  \label{proposition:1}
+  La relación binaria entre vértices de una gráfica $G$, donde dos
+  vértices $u$, $v$ están relacionados cuando existe un $u$-$v$ camino
+  entre ellos, es una relación de equivalencia.
+\end{proposition}
+
+\begin{definition}
+  \label{definition:12}
+  Las subgráficas inducidas por las clases de equivalencia de la
+  relación de equivalencia de la proposición~\ref{proposition:1} se
+  llaman \emph{componentes conexas} de la gráfica.
+\end{definition}
+
 \begin{definition}
   \label{definition:9}
   Sea $G$ una gráfica. Un \emph{ciclo} en~$G$ de \emph{longitud}~$n$,
   con $n\geq 3$, es una sucesión de vértices
-  $v_{0},v_{1},\ldots,v_{n}$, todos distintos entre sí, tales que
-  $v_{i-1}\sim v_{i}$ para $i=1,\ldots,n$ y $v_{0}\sim v_{n}$.
+  $v_{1},\ldots,v_{n}$, todos distintos entre sí, tales que
+  $v_{i-1}\sim v_{i}$ para $i=2,\ldots,n$ y $v_{1}\sim v_{n}$.
 \end{definition}
 
 Un ciclo de longitud~$k$ se llama un \emph{$k$-ciclo}. Un $3$-ciclo 
   bipartita si y sólo si no contiene un ciclo impar.
 \end{theorem}
 
+\begin{proof}
+  Sea $G$ bipartita con partes $X$, $Y$. Sea $v_{1},\ldots,v_{n}$ un
+  ciclo en $G$. Sin perder generalidad, podemos suponer $v_{1}\in
+  X$. Por definición de gráfica bipartita, tenemos que $v_{2}\in Y$,
+  $v_{3}\in X$, etc., en particular, $v_{k}\in Y$ si y sólo si $k$ es
+  par. Como $v_{n}\in Y$ (ya que $v_{1}\in X$), se tiene que $n$ es
+  par.
+
+  Supongamos ahora que $G$ no tiene ciclos impares. Por el
+  ejercicio~\ref{exercises:7}.\ref{ex:bipartita}, podemos suponer que
+  $G$ es conexa. Sea $u\in V(G)$ un vértice fijo. Definimos los conjuntos:
+  \begin{align}
+    \label{eq:40}
+    X & =\setof{v\in V(G)}{d(u,v)\text{ es par}}\\
+    Y & =\setof{v\in V(G)}{d(u,v)\text{ es impar}}
+  \end{align}
+\end{proof}
+
 \begin{definition}
   \label{definition:10}
   Si $G$ tiene ciclos, definimos el \emph{cuello} $g(G)$ como la
 
 
 \begin{exercises}
+\label{exercises:7}
 \item Una gráfica $G$ es \emph{$k$-regular} si todo vértice de $G$
   tiene grado $k$. Demuestra que si $G$ es $k$-regular con $k$ impar,
   entonces $|G|$ es par.
 \item Si $G$ es conexa, y $X\ne\emptyset$ es un subconjunto propio de
   $V(G)$, demuestra que existe $e=uv\in E(G)$ con $u\in X$ y $v\nin
   X$.
+\item Sean $u,v,x\in V(G)$. Demuestra que $d(u,v)\leq d(u,x)+d(x,v)$.
+\item \label{ex:geodesico} Si $u,v$ son vértices de una gráfica $G$,
+  un $u$-$v$ camino de longitud $d(u,v)$ se llama
+  \emph{geodésico}. Sea $x\in V(G)$. Demuestra que
+  $d(u,v)=d(u,x)+d(x,v)$ si y sólo si $x$ está en algún $u$-$v$ camino
+  geodésico.
+\item \label{ex:bipartita} Demuestra que una gráfica es bipartita si y
+  sólo si cada una de sus componentes conexas es bipartita.
 \item Demuestra que una gráfica $k$-regular de cuello~$5$ tiene cuando
   menos $1+k^{2}$ vértices.
 \end{exercises}
 %%% Local Variables: 
 %%% mode: latex
 %%% TeX-master: "libro"
+%%% TeX-PDF-mode: t
+%%% TeX-source-correlate-mode: t
+%%% eval: (set-input-method "spanish-prefix")
 %%% End: