Monografia Final do Trabalho de Formatura

Daniel Morgato Martin

Resumo

Esta é a monografia que conta como se desenrolaram as atividades da minha Iniciação Científica intitulada “Tópicos em Teoria dos Grafos”. Como exemplo dos assuntos que estudei, apresento dois problemas combinatórios, escritos numa linguagem técnica. Muitos outros problemas há que não poderiam ser expostos nestas poucas páginas.

Introdução

Esta monografia pretende apresentar, de um modo bem sucinto, as atividades que realizei ao longo da Iniciação Científica, que foi precisamente o trabalho que escolhi como sendo o Trabalho de Formatura. Comecei a Iniciação Científica em março de 2002 e terminei em dezembro de 2003. Durante esse tempo o meu orientador foi o professor Yoshiharu Kohayakawa. Em 2002 tive também a ajuda do professor José Coelho de Pina Jr. e em 2003 da professora Yoshiko Wakabayashi. A todos eles agradeço a imensa ajuda e atenção com que me assistiram.

Durante esses dois anos tive a oportunidade de conhecer bastante sobre Teoria dos Grafos. Meu estudo foi bem abrangente no sentido de que tive contato com diversas subáreas da Combinatória. O principal objetivo da Iniciação foi adiantar o mestrado, de modo que eu pudesse me dedicar melhor a assuntos mais avançados. Dentre os assuntos que estudei releva citar: enumeração básica, paridade e dualidade em grafos, conexidade de grafos, emparelhamentos e fatores de grafos, coloração de grafos, problemas extremais, teoria de Ramsey, quase boas-ordens e menores.

Metodologia de Estudo

A Iniciação Científica teve como base o livro de László Lovász chamado “Combinatorial Problems and Exercices”. Esse livro contém diversos problemas, mais ou menos divididos por assunto. Para resolver cada problema é necessária uma idéia, um princípio, que é a chave para matar o problema. Conforme fui resolvendo os problemas fui ganhando mais e mais ferramentas combinatórias (conceitos abstratos). Também estudei alguns tópicos dos livros: “Modern Graph Theory” de Béla Bollobás e “Graph Theory” de Reinhard Diestel.

Estudei em torno de 5 problemas por semana. Os problemas eram então expostos ao orientador, ou co-orientador, e discutíamos suas soluções. Nossas reuniões eram semanais e desse modo pude também treinar como fazer uma exposição e adquirir certa prática. Alguns dos exercícios foram colocados nos quatro relatórios que tive de fazer para o CNPq e, posteriormente, para a FAPESP.

Um Problema de Paridade

Gostaria de apresentar nesta seção um problema concreto, que ilustrasse o tipo de situação com que me deparei na Iniciação Científica e que pudesse interessar o leitor a conhecer mais sobre Teoria dos Grafos. A terminologia utilizada será técnica, porém todas as definições necessárias serão fornecidas. (Veja a seção Definições e Notação, caso haja alguma dúvida.) Embora algum contato prévio com Teoria dos Grafos seja necessário, o leitor não deverá ter dificuldades para acompanhar o texto.

Começo decrevendo uma pequena história:

“Certa vez, um homem, tomado de perversidade, convidou n amigos para uma festa intitulada Festa do Cabide. A certa altura da festa, o homem resolveu fazer uma brincadeira com os convidados. Tinha anunciado que, quando ele pronunciasse o nome de alguém na festa, essa pessoa e seus amigos, cada um, deveriam executar o seguinte procedimento: se está vestido então tire a roupa e coloque-a num cabide, senão vista-se novamente. Haja visto o mau caráter do anfitrião, não é muito difícil perceber que seu objetivo era deixar todo mundo nu. Ele só escolheu este método esquisito para camuflar suas más intenções. É possível que ele sempre consiga o que quer? (Ele não participava da brincadeira.)”

Para modelar este problema sob a linguagem própria da Teoria de Grafos vamos considerar amizade como sendo uma relação simétrica. Além disso, vamos supor que cada um seja amigo de pelo menos outro convidado na festa: caso isso não aconteça, a festa terá “panelinhas”, mas então basta considerar cada panelinha como uma festa em separado. A resposta do problema é um pequeno teorema. Há duas provas desse teorema. A primeira usa álgebra linear e, apesar de elegante, foge um pouco do contexto do nosso trabalho por isso não vamos apresentá-la aqui. Já a segunda necessita de um lema que vamos mostrar a seguir.

Lema: Para todo grafo simples G, pode-se dividir V (G) em duas classes A e B de tal forma que os subgrafos induzidos por A e B tenham, ambos, apenas vértices de grau par.

Prova: Se G tem apenas vértices de grau par, tomando A = ∅ e B = V (G) a afirmação é verdadeira. Suponha então que exista a ∈ V (G) de grau ímpar. Construa um grafo G′ modificando G da seguinte forma: retire a e as arestas incidentes a a; para todo par x, y de vizinhos de a, se a aresta {x, y} está em G retire-a de G′ senão coloque-a em G′. Sabemos que a remoção do vértice a garante que |G′| < |G|. Por indução^{1} na ordem do grafo afirmamos que existem duas classes de vértices A′ e B′ em V (G′) tal que os subgrafos induzidos por A′ e B′ têm apenas vértices de grau par. Como d_{G}(a) é ímpar, uma das classes tem intersecção ímpar com Γ(a). Vamos supor, sem perda de generalidade, que seja a classe A′. Tome A = A′ e B = B′ ∪ {a}. Vamos mostrar que os subgrafos de G induzidos por A e B têm apenas vértices de grau par. Os pontos de (A ∪ B) \ Γ(a) continuam com grau par, pois a eles nada foi ligado nem desligado. Sabemos que a tem grau par no subgrafo induzido por B pois B′ tem um número par de vizinhos de a. Resta-nos verificar que os vértices em Γ(a) têm grau par. O que muda de A′ para A é que houve uma complementação nas arestas que ligavam os vértices de Γ(a) ∩ A entre si, e por que temos um número ímpar deles, eles continuam com grau par em A. A mesma complementação acontece nas arestas que ligam os vértice de B ∩ Γ(a) entre si, mas como agora temos um número par deles, eles ficaram com grau ímpar. O fato de que colocamos a em B torna-os de grau par novamente. □

1A base dessa indução é o grafo N_{1} com apenas um vértice e nenhuma aresta.

Vamos modelar a festa do cabide por um grafo conexo. Cada vértice desse grafo representa uma pessoa. Dois vértices são adjacentes se as pessoas correspondentes são amigas. A cada vértice associo um número 0 ou 1: 0 se a pessoa está vestida, 1 caso contrário. Uma operação sobre um vértice corresponde a uma ordem verbal dada pelo anfitrião quando chama o nome de alguém. Essa operação consiste em trocar os valores associados àquele vértice e aos seus vizinhos.

Teorema: Seja G um grafo simples conexo de ordem n. Para todo vértice v ∈ V (G) associo uma valor w(v) ∈ {0, 1}. Inicialmente, w(v) = 0 para todo vértice v. Seja ϕ_{v} uma operação que consiste em trocar o valor de w(u) se u = v ou se u é vizinho de v. Então existe um conjunto X = {v_{1}, v_{2}, …, v_{t}} ⊆ V (G) tal que aplicando as operações ϕ_{v_{1}}, ϕ_{v_{2}}, …, ϕ_{v_{t}}, obtemos w(v) = 1 para todo vértice v.

Prova: Construa G′ acrescentando a G um vértice u e ligando-o a todos os outros que possuem grau par. Pelo lema anterior posso dividir os vértices de G′ em classes A e B de tal forma que os subgrafos induzidos por A e B tenham apenas vértices de grau par. Sem perda de generalidade, vamos supor que u ∈ B. Afirmo que cada vértice em B \ {u} se liga a um número ímpar de vértices em A. Para ver isso, retire u de B. O conjunto B pode, agora, ser dividido em duas classes B_{P} dos vértices com grau par (em B) e B_{I} dos que ficaram com grau ímpar (em B) após a remoção de u. Repare que, em relação a G, os vértices de B_{I} têm graus pares (por que foram ligados a u) e os de B_{P} tem graus ímpares. Assim, cada vértice de B está ligado a um número ímpar de vértices de A. Tomando t = |A| e X = A = {v_{1}, v_{2}, …, v_{t}}, temos que após as operações ϕ_{v_{1}}, ϕ_{v_{2}}, …, ϕ_{v_{t}}, é verdade que w(v) = 1 para todo v ∈ V (G), pois w(v) troca de valor um número ímpar de vezes. □

Então, se o anfitrião chamar os nomes das pessoas que ficaram na classe A, todo mundo fica sem roupa no final.

Mais Resultados Interessantes

Nesta seção eu gostaria de apresentar algo ligeiramente diferente. Ao contrário do que foi feito na seção anterior, o problema que vou descrever aqui não está em nenhum livro, mas foi fruto de uma pergunta que fiz a mim mesmo. E isso é a base da pesquisa científica: saber fazer perguntas adequadas e saber respondê-las com as ferramentas adquiridas com o estudo e com a experiência.

Antes de mais nada, vamos apresentar a notação que será utilizada nesta seção, pois ela é de fundamental importância na compreensão dos resultados que virão a seguir.

Um m-vetor sobre um conjunto S, m ≥ 2, é uma função que vai do conjunto S no conjunto {0, 1, …, m − 1}. O conjunto de todos os m-vetores sobre S será denotado por m^{S}. A expressão cX, 0 ≤ c ≤ m − 1, denota o m-vetor sobre X ⊆ S que vale c para todo elemento de X. Seja v um m-vetor sobre S. O valor assumido por v no ponto x ∈ S será expresso por v(x). Denotaremos por supp(v) o subconjunto de S cujos elementos assumem valores positivos no m-vetor v. Se supp(a) ∩ supp(b) = ∅ então podemos definir a soma c dos m-vetores a e b da forma usual: c(x) = a(x) + b(x). Um m-vetor v sobre X ⊆ S pode ser enxergado como um m-vetor sobre S forçando v(x) = 0 para todo x ∈ S \ X.

Um dos resultados que estudei na Iniciação foi o Teorema de Hales–Jewett que está enunciado abaixo. Este é um resultado importante com diversas aplicações, por exemplo, pode ser usado para provar o Teorema de Van der Waerden^{2}. A demonstração desse teorema é bastante complicada, por isso não vou pô-la aqui.

Teorema (Hales–Jewett): Seja S um conjunto finito e α uma kcoloração dos m-vetores em m^{S}. Para todo r ≥ 1 existe um inteiro N(k, r, m) tal que, se |S| ≥ N(k, r, m), então existem conjuntos disjuntos não-vazios X_{1}, X_{2}, …, X_{r} ⊆ S e um m-vetor b sobre S \ X, X = X_{1} ∪ X_{2} ∪ ⋯ ∪ X_{r}, tal que todos os m-vetores da forma

b + ∑_{i=1}^{r} a_{i}X_{i} (0 ≤ a_{i} ≤ m − 1)

têm a mesma cor. □

A pergunta que me fiz foi basicamente a seguinte: será que vale uma versão infinita do Teorema de Hales–Jewett? Ou seja, queremos saber se para toda k-coloração dos ∞-vetores sobre ℕ (funções de ℕ em ℕ) e para todo r existem conjuntos disjuntos não-vazios e finitos X_{1}, X_{2}, …, X_{r} ⊆ ℕ e um ∞-vetor b sobre ℕ\(X_{1} ∪X_{2} ∪…∪X_{r}), tais que os ∞-vetores da forma:

2O Teorema de Van der Waerden afirma que, se colorirmos os números inteiros de 1 até n com k cores, e se n = n(k, m) for suficientemente grande, então existe uma progressão aritmética de tamanho m monocromática nesse intervalo.

b + ∑_{i=1}^{r} a_{i}X_{i} (0 ≤ a_{i})

têm todos a mesma cor. Meu orientador me deu uma idéia e, com essa ajuda, consegui provar o Lema 2 e o Teorema 1 abaixo.

Não vamos mais dizer ∞-vetor pois soa meio estranho; vamos dizer ℕvetor ou simplesmente função. Seguindo a notação usual, o conjunto de todas as funções de ℕ em ℕ vamos denotar por ℕ^{ℕ}.

Lema 1: União enumerável de conjuntos enumeráveis é enumerável. Prova: Suponha X = X_{1} ∪ X_{2} ∪ …, com os conjuntos X_{i} enumeráveis.

Podemos supor que X_{i} = {x_{i,1}, x_{i,2}, …}. Queremos provar que X é um conjunto enumerável. Considere a seguinte ordenação em forma matricial dos elementos de X:

\begin{matrix}x_{1,1} & x_{1,2} & x_{1,3} & x_{1,4} & ⋯ \\ x_{2,1} & x_{2,2} & x_{2,3} & x_{2,4} & ⋯ \\ x_{3,1} & x_{3,2} & x_{3,3} & x_{3,4} & ⋯ \\ x_{4,1} & x_{4,2} & x_{4,3} & x_{4,4} & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}

Podemos considerar uma ordem dos elementos de X que corresponde a varrer a matriz acima diagonal por diagonal. Ou seja, queremos percorrer na ordem: x_{1,1}, x_{1,2}, x_{2,1}, x_{1,3}, x_{2,2}, x_{3,1}, …, etc. Desse modo iremos percorrer todos os elementos de X. Para tornar a bijeção de X com ℕ mais precisa, o elemento x_{i,j} será colocado na posição:

\frac{(i + j − 1)(i + j − 2)}{2} + (i − 1).

Isso prova que X é um conjunto enumerável. □

Lema 2: Seja H um hipergrafo onde cada hiperaresta é um conjunto infinito e o conjunto de hiperarestas é enumerável. Então χ(H) = 2.

Prova: Se o conjunto de hiperarestas é enumerável, então podemos chamá-las C_{1}, C_{2}, …, etc. Queremos colorir os vértices de H com duas cores, sem que haja uma hiperaresta C_{i} cujos elementos (vértices) tenham todos a mesma cor. No primeiro passo, escolha x_{1}, y_{1} ∈ C_{1} e pinte x_{1} de vermelho e y_{1} de azul. Agora suponha que i ≥ 2. Escolha x_{i}, y_{i} ∈ C_{i} que ainda não foram coloridos. Note que podemos fazer tal escolha, pois C_{i} tem um número infinito de elementos e, até agora, colorimos apenas um numero finito de vértices em H, a saber, 2(i − 1) vértices. Pinte, então, x_{i} de vermelho e y_{i} de azul. Desse modo, já temos colorido os vértices do conjunto:

⋃_{i=1}^{∞} {x_{i}, y_{i}}.

Pelo modo como atribuimos as cores aos vértices desse conjunto, nenhuma hiperaresta C_{i} é monocromática. Agora, dê cores vermelho/azul ao restante dos vértices como quiser. A coloração descrita aqui é uma 2-coloração própria de H. Portanto χ(H) = 2. □

Na demonstração do teorema seguinte, vamos usar o seguinte fato: o conjunto 𝒫_{<∞}(ℕ), dos subconjuntos finitos de ℕ, é enumerável. Para ver que isso é verdade, podemos pensar nos vetores característicos dos subconjuntos finitos de ℕ. Cada um desses vetores corresponde a um número natural escrito em base binária, lendo-se da esquerda para a direita.

O teorema abaixo apresenta, então, uma resposta negativa à minha pergunta como se pode ver.

Teorema 1: Existe uma 2-coloração α das funções em ℕ^{ℕ} tal que não existem um subconjunto não-vazio finito X ⊆ ℕ e um ℕ-vetor f sobre ℕ \ X tais que os ℕ-vetores da forma f + aX, a ≥ 0, têm todos a mesma cor.

Prova: Considere a seguinte relação ∼ em ℕ^{ℕ}: dois ℕ-vetores f e g estão relacionados (f ∼ g), se seus valores diferem em um número finito de coordenadas.

A relação ∼ é claramente uma relação de equivalência. Observe que, para qualquer subconjunto não-vazio finito X ∈ ℕ e ℕ-vetor f ∈ ℕ^{ℕ\X}, os ℕvetores da forma f +cX, c ≥ 0, estão todos na mesma classe de equivalência.

Seja A uma classe de equivalência arbitrária de ℕ^{ℕ}/∼. Afirmo que a classe A é um conjunto enumerável. Para provar isso, fixe uma função f ∈ A e considere a relação de equivalência ≡_{f} definida assim: g ≡_{f} h se supp|f−g| = supp|f −h|, onde |f −g| é o ℕ-vetor tal que |f −g|(i) = |f(i)−g(i)|, para todo i ∈ ℕ. Existe uma bijeção óbvia ϕ: A/≡_{f}⟶ 𝒫_{<∞}(ℕ). Portanto temos um conjunto enumerável de classes em A/≡_{f}. Por outro lado, também é fácil ver que cada classe de A/≡_{f} é enumerável. Assim, A é uma união enumerável de conjuntos enumeráveis (as classes de A/≡_{f}) e, pelo Lema 1, A é enumerável.

Para cada ℕ-vetor f ∈ A, e para cada subconjunto finito não-vazio X ⊆ ℕ, considere o conjunto de funções C_{f,X} = {f_{X} + cX: c ∈ ℕ}, onde f_{X} é definido por:

f_{X}(i) = \begin{cases}0 & se i ∈ X, \\ f(i) & caso contrário. \end{cases}

Note que o que realmente queremos provar é que não existe classe A e nem conjunto C_{f,X}, f ∈ A, tal que todas as funções de C_{f,X} tenham a mesma cor. O conjunto C_{f} = {C_{f,X}: X ⊆ ℕ é subconjunto finito} é claramente enumerável. Como A é enumerável, temos que

C = ⋃_{f∈A} C_{f}

é uma união enumerável de conjuntos enumeráveis, e portanto é enumerável. Suponha, então, que os elementos de C sejam C_{1}, C_{2}, …, etc. Considere o hipergrafo H cujo conjunto de vértices é A e o conjunto de hiperarestas é C. Como o hipergrafo H satisfaz as condições do Lema 2, podemos afirmar que existe uma 2-coloração própria φ_{A} de H. A arbitrariedade com que tomamos a classe A garante que podemos fazer o mesmo para cada classe de ℕ^{ℕ}/∼. As colorações obtidas em cada uma dessas classes formam, juntas, uma 2-coloração α de ℕ^{ℕ} como gostaríamos que fosse. □

Integração com o Curso

Desafios e frustrações

Resolver problemas é, sem dúvida uma maneira muito eficaz de se aprender combinatória. Porém, isso exige muito tempo já que as idéias não vêm voando do nada: é preciso muito esforço e dedicação, é preciso gastar tempo observando os fatos até que alguma idéia rudimentar surja. Issa é a parte mais difícil e, às vezes, chega até a ser frustrante quando nenhuma idéia vem à cabeça. No entanto, quando elas vêm, são fixadas de tal modo que quando outro problema precisar da mesma idéia, você rapidamente lembra dela e sabe aplicá-la de modo adequado.

Disciplinas relevantes

Embora tenha cursado uma disciplina chamada “Algoritmos em Grafos” na graduação, não tive oportunidade de ver Teoria de Grafos tão a fundo como na Iniciação Científica. A Iniciação fez com que eu entendesse mais facilmente várias disciplinas, como “Algoritmos de Aproximação”, “Programação Inteira” e “Tópicos de Matemática Discreta”, e vice-versa. Vejo a Iniciação Científica como uma atividade que me ajudou muito a desenvolver clareza de raciocínio e a melhorar a forma de expressar conceitos abstratos.

Atuação na área

A Iniciação Científica ajudou-me a decidir por continuar estudando esses assuntos. Pretendo fazer mestrado e, quem sabe, doutorado. Um dos assuntos que mais me chamou a atenção durante a Iniciação foi Coloração de Grafos, e é esse tópico que pretendo estudar mais a fundo no mestrado.

Conclusão

A Iniciação Científica foi muito válida pois com ela:

• adiantei os estudos do mestrado e poderei me dedicar melhor ao estudo de tópicos mais avançados,

• aprendi muita coisa sem assistir a aulas, sem ficar preso a um horário e nem a bibliografia fixa,

• os problemas que estudei me ajudaram bastante na graduação e me ensinaram a ter clareza de raciocínio,

• pude testar meus conhecimentos durante as reuniões semanais com o orientador e nos relatórios que tive de elaborar para as instituições financiadoras.

Gostaria, finalmente, de agradecer aos meus colegas do BCC2000 por todo o apoio que recebi.

Definições e Notação

Nas linhas seguintes G é um grafo qualquer, X e Y são conjuntos e v é vértice.

grau de um vértice v ⟶ É o número de arestas que incide no vértice v. subgrafo induzido por um conjunto X de vértices ⟶ É o subgrafo de G obtido removendo-se todos os vértices que não estejam no conjunto X e todas as arestas que neles incidiam. grafo simples ⟶ Um grafo que não possui arestas paralelas. |G| ⟶ Denota o número de vértices do grafo G. X \ Y ⟶ Denota o conjunto dos elementos que estão em X mas não em Y. |X| ⟶ Denota o número de elementos do conjunto X. d_{G}(v) ⟶ Denota o grau do vértice v no grafo G. Γ(v) ⟶ Denota o conjunto de vértices de G que são adjacentes a v.

[n] ⟶ Conjunto dos n primeiros inteiros positivos: {1, 2, …, n}. 𝒫_{k}(X) ⟶ Conjunto dos subconjuntos de X que possuem exatamente k elementos. 𝒫_{<∞}(X) ⟶ Conjunto dos subconjuntos finitos de X.

Uma coloração de um conjunto X é uma função φ: X ⟶ C, onde C é um conjunto qualquer cujos elementos são chamados de cores.

Um conjunto X é enumerável se existe uma bijeção de X no conjunto ℕ dos naturais. Dizemos que uma união é enumerável se é uma união da forma:

⋃_{i∈I} X_{i},

onde I é um conjunto enumerável.

Bibliografia

L. Lovász, Combinatorial problems and exercises, second ed., North-Holland Publishing Co., Amsterdam, 1993.

Reinhard Diestel, Graph theory, Springer-Verlag, New York, 1997, Translated from the 1996 German original.

M. Aigner, G. M. Ziegler, Proofs from THE BOOK, Springer-Verlag, Berlin 1998.