\documentclass[twoside]{article}
\usepackage{amssymb,amsfonts,amssymb,amsthm}
\usepackage[brazil]{babel}
\usepackage{graphicx}
\usepackage[latin1]{inputenc}%permite escrever com acentos, como no Word
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% POR FAVOR NÀO MODIFIQUEM OS DADOS ABAIXO
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pagestyle{myheadings} \topmargin =-20pt \marginparwidth = 45pt
\evensidemargin = -15pt \oddsidemargin = -15pt \textheight = 670pt
\textwidth = 500pt \linespread{1.2}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\renewcommand{\theequation}{\arabic{section}.\arabic{equation}}
\newtheorem{myth}{Teorema}[section]
\newtheorem{mylem}{Lema}[section]
\newtheorem{mypro}{Proposi\c c\~ao}[section]
\newtheorem{mydef}{Defini\c c\~ao}[section]
\newtheorem{myrem}{Observa\c c\~ao}[section]
\newtheorem{mycor}{Corol\'ario}[section]
\newtheorem{myex}{Exemplo}[section]
\newcommand{\cqd}{\hspace{10pt}\fbox{}}
\newcommand{\cqdf}{\hspace{10pt}\rule{5pt}{5pt}}
%
\begin{document}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%% CABEÇALHO DA PÁGINA - POR FAVOR NÀO MODIFIQUEM!
\pagestyle{empty}
\title{\vspace{-1in}\parbox{\linewidth}{\footnotesize\noindent
{\sc  \bf V Bienal da SBM}
\newline
{\sc  \bf Sociedade Brasileira de Matemática}
\newline
{\sc \bf UFPB - Universidade Federal da Paraíba}
\newline
\bf 18 a 22 de outubro de 2010 }
\newline\newline
%%%%%%%%%%%%%%%%%%%FIM DO CABEÇALHO%%%%%%%%%%%%%%%%%%%%%%%%
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% ESCREVER O TÍTULO DO TRABALHO NO COMANDO ABAIXO COM
%%% LETRAS MINÚSCULAS!
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
{\sc colorindo mapas}
%\vskip -0.5truecm
\author{\sc Gésica Peixoto Campos\,\thanks{Universidade Federal de Pernambuco,\,
UFPE, PE, Brasil,\, gesica.pcampos@bol.com.br} \,\,\,\,\&\,\,\,\, 
Izabelly Marya Lucena da Silva\,\thanks{Universidade Federal de Pernambuco,\,
UFPE, PE, Brasil,\,izabellymarya@ig.com.br
}}}
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% NAO PREENCHER O COMANDO \date{} ABAIXO, DEIXAR COMO ESTÁ!
%% NÃO RETIRAR OS COMANDOS \maketitle E \thispagestyle{empty}
\date{}
\maketitle \thispagestyle{empty} \vspace{-10pt}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%

\section{Introdução}
Vamos começar com a seguinte dinâmica:\\
Em uma entrevista um estilista especializado em cores da moda afirmou que:
\begin{itemize}
\item A cor azul combina com a vermelha;
\item A cor vermelha combina com a rosa;
\item A cor verde combina com todas as outras cores da tendência.
\end{itemize}
Sabendo que as cores da tendência são azul (az), verde (vd), rosa (rs), vermelha (vm) e amarela (am). 

\textbf{Exercício: } Como representar de forma simples as escolhas do especialista?
\vspace{4cm}

A forma de representação mais simples que podemos fazer é um artifício matemático chamado grafo.
\subsection{Grafos}
\begin{mydef} Grafo é um conjunto de pontos (chamados comumente de vértices) e arestas que são curvas que conectam dois desses vértices não mais de uma vez. \end{mydef}

Para construir o grafo relacionaremos os vértices às cores e as arestas à associação que ele vez com as cores. Assim obtemos o grafo:

\begin{figure}[h]
\centering
\includegraphics[scale=0.25]{figura1.eps}
\caption{Grafo que representa o problema anterior}
\label{fig:}
\end{figure}


Mas você concorda com o estilista? Agora vamos tentar fazer outras relações de cores. 

\section{Qual a correspondência entre coloração de mapas e grafos?}
Como na dinâmica os grafos vão servir para facilitar a compreensão e a visualização. Ao pintarmos o mapa, a cada região associaremos um vértice e as devidas vizinhanças às arestas do grafo, portanto um mapa pode ser representado por um grafo.

\subsection{Grafo dual}

Dado um mapa (no sentido usual de mapa), façamos:
\begin{enumerate}
\item Faremos um grafo associado ao mapa da seguinte maneira, chamaremos de vértice um ponto do mapa que é fronteira de três regiões diferentes e as arestas são as fronteiras entre das regiões duas a duas. Ver figura 2b.
\item Demarca - se um novo vértice no interior de cada face do grafo associado ao mapa, em seguida, para cada duas regiões vizinhas, com alguma aresta em comum, desenha-se uma aresta ligando as duas regiões, cortando a fronteira comum de ambos. Ver figura 2c.
\end{enumerate}

\begin{figure}[h]
\centering
\includegraphics[scale=0.7]{Figura2.eps}
\caption{(a) Mapa da Regiâo Sudeste; (b) Grafo associado ao mapa; (c) Grafo dual do mapa}
\label{fig:}
\end{figure}

\textbf{Exercício:} Construa o grafo dual dos mapas de acordo com o exemplo anterior.

\begin{figure}[h]
\centering
\includegraphics[scale=1.2]{Figura3.eps}
\caption{Mapas das Regiões Sul e Nordeste}
\label{fig:}
\end{figure}

\begin{figure}[b]
\centering
\includegraphics{Figura4.eps}
\caption{Exemplo de grafo planar}
\label{fig:}
\end{figure}

\subsection{Planaridade}  
Um grafo é chamado de planar quando pode ser representado no plano de tal forma que suas arestas não se cruzem (exceto nos vértices). Por exemplo:

\textbf{Exercício:} Construir alguns os possíveis grafos com 3, 4, 5 e 6 vértices. 
\vspace{5cm}

\begin{myth} Um grafo planar sobre n vértices tem no máximo 3n - 6 arestas. \end{myth}
\begin{myth} Todo grafo planar tem pelo menos um vértice de grau no máximo 5 (grau: quantidade de aresta que sai do vértice). \end{myth}

Será que todo grafo é planar?\\
Não. Como vimos no exercício anterior existe um tipo de grafo com cinco vértices ($K_5$) e outro com seis ($K_{3,3}$) que não são planares e segundo o teorema de Kuratowski todo grafo que possui na sua composição um dos dois não é planar. 

\begin{figure}[h]
\centering
\includegraphics[scale=0.55]{Figura5.eps}
\caption{$K_{3,3}$ e $K_5$}
\label{fig:}
\end{figure}


\begin{figure}[b]
\centering
\includegraphics[scale=0.7]{Figura6.eps}
\caption{Mapa do Brasil}
\label{fig:}
\end{figure}

\section{Coloração de mapas}
\begin{myth}[Teorema das quatro cores]
Todo mapa pode ser colorido com quatro ou menos cores, respeitando-se a condição de que países vizinhos, com alguma linha de fronteira em comum, tenham cores diferentes. \end{myth}

Mas para ser mais fácil iremos começar com o seguinte teorema: "Todo mapa pode ser colorido com cinco cores". 
\textbf{Exercício:} Vamos tentar pintar o mapa do Brasil com esse teorema.

Agora vamos generalizar, demonstrando para todo mapa.

\textbf{Primeiro passo:} Construir o grafo dual do mapa.\\
Para a demonstração valer, o grafo dual tem que ser planar.\\
\textbf{Exercício:} Mostre que todo mapa tem um grafo dual relacionado a ele e o grafo vai ser sempre planar.
\vspace{5cm}

\textbf{Segundo passo:}

Dem.: Para facilitar esta demonstração iremos considerar coloração de vértices de grafos, isto é, vértices ligados pela mesma aresta não podem ter a mesma cor.
Nomenclatura: $\mathcal{G}$ = grafo; $d(x)$ = grau do vértice $x$.

Obs.: Grafo planar com menos de 5 vértices pode pintar trivialmente.

Suponha que todos grafos com $t$ vértices sejam coloridos com 5 cores. Temos que mostrar que grafo planar com $t+1$ vértices é colorível com 5 cores.

Por hipótese, o grafo $\mathcal{G}\ \backslash \ x$  pode ser colorido com 5 cores.

\begin{itemize}
\item Se $d(x) < 5$, então sobra pelo menos uma cor para colorir $x$, assim satisfazendo o teorema.

\item Se $d(x) = 5$, então considere a arrumação representada pela Figura \ref{F7}:

\end{itemize}

\begin{figure}[h]
       \begin{minipage}[b]{0.48 \linewidth}
          \centering
          \includegraphics[scale=0.3]{estrela.eps}\\
          \caption{O vértice $x_i$ está pintado com a cor $i$}
          \label{F7}
          \end{minipage}
      \begin{minipage}[b]{0.48 \linewidth}
          \centering
          \includegraphics[scale=0.3]{estrela2.eps}
          \caption{O ciclo $C_{1,3}$}
          \label{F8}
          \end{minipage}
\end{figure}


Considere $C_{1,3}$ o subgrafo de $\mathcal{G}\ \backslash \ x$ induzido pelos vértices de cor 1 e 3. Podem os vértices $x_1$ e $x_3$ estarem em componentes distintas? Sim. Porém, se isso ocorre, então na componente que contém $x_1$ poderíamos trocar a cor 1 pela cor 3, ficando assim a cor 1 livre pra pintar $x$. 

Então suponhamos que $x_1$ e $x_3$ estão na mesma componente. Logo, existe um caminho $P_{1,3}$ que liga $x_1$ à $x_3$ (ver Figura \ref{F8}). Unindo $P_{1,3}$ a $x$ obtemos o ciclo $C_{1,3}$. Notemos que os vértices $x_2$ e $x_4$ ficaram em regiões diferentes do ciclo. Suponhamos sem perda de generalidade que $x_2$ pertence ao $intC_{1,3}$ e $x_4$ pertence ao $extC_{1,3}$. 

Olhemos agora para $P_{2,4}$. Se $x_2$ e $x_4$ estivessem na mesma componente teríamos um absurdo, pois $P_{2,4}$ e $C_{1,3}$ teriam um vértice em comum, podendo ser duas possibilidades: Um vértice $y$ que pertence a interseção de $C_{1,3}$ e $P_{2,4}$, assim $y$ tem cor 2 ou 4 e $y$ tem cor 1 ou 3 (absurdo!); ou $x$ pertence a $P_{2,4}$ e a $C_{1,3}$ assim podendo pintá-lo com uma das cores, o que não pode ocorrer por hipótese.

Então $x_2$ e $x_4$ estão em componentes distintas e, por exemplo, podemos trocar a cor 2 pela cor 4 na componente que contém $x_2$, deixando a cor 2 livre pra pintar $x$.

O teorema das quatro cores foi demonstrado em 1976 por Appel e Haken, mas sua prova usou computadores muito intensamente para verificar um enorme número de casos e ainda hoje precisa-se deles para a sua demonstração. Por sua complexidade não demonstraremos o teorema das quatro cores.

\section{Curiosidade}
Em 1º de abril de 1975, Martin Gardner publicou, na revista americana Scientific American, um mapa que, segundo ele, não era possível ser colorido com apenas quatro cores.

\begin{figure}[h]
\centering
\includegraphics{figura07.eps}
\caption{Mapa de Martin Gardner}
\label{fig:}
\end{figure}

Este mapa foi de muita confusão entre os matemáticos durante muitos anos, chegaram até a desacreditar no teorema das quatro cores. Mas esse mapa é só uma mentirinha de primeiro de abril.\\

\textbf{Exercício: } Tentar pintar o mapa de acordo com o teorema das quatro cores.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%% REFERÊNCIAS
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Referências}
\setcounter{equation}{0}
\noindent[1] {\sc lovász, l. \& pelikán, j. \& vestergombi, k.} -
  {\it Matemática Discreta}, SBM, 2003.

\noindent[2] {\sc harary, f.} -
  {\it Graph theory}, Addison - Wesley Publishing company, 1969.

\noindent[3] {\sc sampaio, j.c.v.} {\it Quatro Cores e Matemática}, II Bienal da SBM , UFBA, 2004. \\ site: http://www.bienasbm.ufba.br/M35.pdf.

\noindent[4] {\it http://www.atractor.pt/matviva/geral/t5cores/T4C.htm}.

\noindent[5] {\it http://www.congresscentral.com.br/cnmac2009/pub/arquivos/585\_a976\_PolyUFF.pdf}.

\noindent[6] {\it http://pt.wikipedia.org/wiki/Sete\_pontes\_de\_Koenigsberg}.

\noindent[7] {\it http://algoritmos.tiagomadeira.net/os-grafos-e-o-orkut}.

\noindent[8] {\it http://www.ici.unifei.edu.br/luisfernando/arq\_pdf/palestras/tres\_problemas\_sobre\_grafos.pdf}.

\end{document}
