\documentclass[letterpaper, 12pt]{article}
\usepackage[spanish]{babel}
\usepackage[latin1]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{latexsym} 
\usepackage{amssymb}  
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\usepackage{amsmath} 
\usepackage{graphicx}
\usepackage{color} 
\usepackage{xcolor} 
\usepackage{wrapfig} 
\usepackage{pdfsync}
% \usepackage{floatflt}
\usepackage{paralist}
% \usepackage{makeidx}
\usepackage{ifpdf}
% \usepackage{graphfig}
% \usepackage{subfig}
\usepackage{graphicx} 
\usepackage{mathrsfs}
\usepackage{caption} 
\newcommand{\header}[2]{
	\begin{center}
 		\rule{\linewidth}{1pt}
 		\Large{#1}
 		\rule{\linewidth}{1pt}
 		\normalsize{#2}
 	\end{center}
}

\usepackage{pgf,tikz}
\usetikzlibrary{arrows}

\theoremstyle{plain}
\newtheorem{proposicion}{Proposition}
\newtheorem{lema}{Lema}
\newtheorem{teorema}{Teorema}
\newtheorem{corolario}{Corolario}
\newtheorem{conjetura}{Conjetura}

\theoremstyle{definition}
\newtheorem{definicion}[proposicion]{Definición}

\renewcommand{\figurename}{Figura}

\DeclareMathOperator{\mcd}{mcd}

\begin{document}
\header{Teoría de las gráficas I}{Versión definitiva de la segunda tarea}

Lee, piensa y responde con cuidado. No olvides justificar bien tus respuestas. Se entrega en equipos de dos personas.

\begin{enumerate}
 \item Dada una gráfica $G$, una \emph{orientación} de $G$ es cualquier digráfica obtenida al darle una dirección (y sólo una) a cada arista de $G$. Prueba que existen exactamente cuatro orientaciones de $K_4$ (la gráfica completa de cuatro vértices), salvo isomorfismos. (\textit{Sugerencia.} Considera los ex-grados e in-grados de los vértices así como aquellas orientaciones que son y no son fuertemente conexas para probar que sólo existen cuatro posibles orientaciones.)


\item Las \emph{componentes fuertemente conexas} de una digráfica $D$ son las subdigráficas fuertemente conexas máximas por contención en los vértices de $D$ (i.e., una componente fuertemente conexa no es subdigráfica propia de ninguna subdigráfica fuertemente conexa de $D$).

Dada una digráfica $D$, la \emph{condensación} de $D$ es la digráfica $\mathcal{C}(D)$ cuyos vértices son las componentes fuertemente conexas de $D$ y si $D_1$ y $D_2$ son dos vértices de $\mathcal{C}(D)$ y hay alguna flecha de $D_1$ a $D_2$ en $D$ entonces hay flecha de $D_1$ a $D_2$ en $\mathcal{C}(D)$. Prueba que $\mathcal{C}(D)$ es acíclica (i.e., no posee ciclos dirigidos, ni siquiera de longitud dos). (\textit{Sugerencia.} Supón que no es acíclica y llega a una contradicción).

\item Define una función \emph{distancia} para digráficas, de forma análoga a como lo hicimos para gráficas pero considerando la dirección. Prueba qué propiedades de las métricas (las cuatro que se enunciaron en clase) satisface esta distancia y cuáles no.

\item Recuerda que una gráfica se dice que es \emph{multipartita completa} si existe una partición de sus vértices $V_1$, $V_2$, \ldots, $V_k$ (las \emph{partes} de la gráfica) tales que entre vértices en la misma parte no hay arista y entre cualesquiera par de vértices en partes distintas siempre hay arista. La gráfica multipartita completa con $k$ partes y $n$ vértices tal que en cada parte tiene $\lceil \frac{n}{k} \rceil$ o $\lfloor \frac{n}{k} \rfloor$ vértices se denota como $T_{k,n}$\footnote{Recuerda que $K_{n_1, n_2, \ldots, n_k}$ donde $n_i$ es un entero para $i \in \{1$, $2$, \ldots, $k\}$ es la gráfica multipartita completa con $k$ partes tal que la $i$-ésima parte tiene $n_i$ vértices. Algunos ejemplos de las $T_{k,n}$ son: $T_{3,6}=K_{2,2,2}$, $T_{3,7}=K_{2,2,3}$, $T_{3,8}=K_{2,3,3}$, $T_{3,9}=K_{3,3,3}$, $T_{4,6}=K_{1,1,2,2}$, $T_{4,7}=K_{1,2,2,2}$, $T_{4,8}=K_{2,2,2,2}$ y $T_{4,9}=K_{2,2,2,3}$.}. Prueba que
\begin{displaymath}
 \lvert A(T_{k,n})  \rvert = \binom{n-p}{2}+(m-1)\binom{p+1}{2}
\end{displaymath}
donde $p=\lfloor \frac{n}{k} \rfloor$. ¿Puedes decir algo sobre el tamaño de cualquier gráfica multipartita completa de orden $n$ con $k$ partes y el tamaño de $T_{k,n}$? No es necesario justificar esto último. (\textit{Sugerencia.} Tanto $\lceil \frac{n}{k} \rceil$ como $\lfloor \frac{n}{k} \rfloor$ lo pueden expresar en término de $p$. El problema sólo es desarrollar la expresión y acomodarla adecuadamente.)


 \item Las \emph{componentes conexas} de una gráfica $G$ son las subgráficas conexas máximas por contención de los vértices de $G$ (i.e., una componente conexa no es subgráfica propia de ninguna subgráfica conexa de $G$).

 Dada una gráfica $G$, se dice que $u$ y $v$ están \emph{conectados}, $u \sim v$, si existe una $(u$, $v)$-trayectoria. La relación de estar conectados es de equivalencia sobre los vértices de $G$ y, por lo tanto, induce una partición de los vértices de $G$. Prueba que una subgráfica de $G$ es una componente conexa de $G$ si y sólo si está inducida por alguna parte de la partición inducida por la relación de estar conectados. (\textit{Sugerencia.} Por un lado, prueba que en una componente conexa, todos los vértices están relacionados. Por el otro, prueba que cada subgráfica inducida por una parte de la partición es máxima por contención en los vértices.)

 \item \begin{enumerate}
  \item Prueba que si $v$ es un vértice de grado uno en una gráfica conexa $G$ entonces $G-v := G[V(G) \setminus \{ v\}]$ es conexa (\textit{Sugerencia}. Puedes usar la siguiente caracterización, una gráfica es conexa si y sólo si existe un camino que pasa por todos sus vértices).
  \item Prueba que si en una gráfica $G$ todo vértice tiene grado al menos dos entonces $G$ posee un ciclo (\textit{Sugerencia}. Considera una trayectoria de longitud máxima y fíjate en alguno de sus extremos y aplica la hipótesis).
  \item Prueba que toda gráfica conexa tiene tamaño al menos $n-1$, donde $n$ es el orden de la gráfica (\textit{Sugerencia}. Hazlo por inducción sobre el número de vértices y considera dos casos, si todo vértice tiene grado mayor o igual que dos o si no, en este último caso, utiliza el primer inciso).
  \item Prueba que si todos los vértices de una \textbf{digráfica} $D$ tienen ex-grado mayor o igual que uno entonces $D$ posee un ciclo dirigido. (\textit{Sugerencia}. Se hace con la misma idea que el segundo inciso).
\end{enumerate}
\end{enumerate}

\end{document}