Videoaula

Introduzimos o conceito de grafo, uma representação de elementos e das relações entre eles através de vértices e elos (ou arestas). Apresentamos dois problemas aparentemente não relacionados, mas que podem ser visualizados através de grafos. O primeiro é o famoso problema das Pontes de Königsberg, e o segundo pede para se mostrar que em qualquer grupo existem duas pessoas que possuem o mesmo número de amizades dentro do grupo.

Apresentamos um problema em que a visualização através de um grafo é bastante clara: No ano 3000 será possível viajar entre os seguintes planetas: Terra-Mercúrio, Plutão-Vênus, Terra-Plutão, Plutão-Mercúrio, Mercúrio-Vênus, Urano-Netuno, Netuno-Saturno, Saturno-Júpiter, Júpiter-Marte e Marte-Urano. Será possível viajar da Terra para Marte? A resolução exemplifica como os grafos muitas vezes podem simplificar o entendimento de uma situação-problema.

Resolvemos um novo problema através da visualização da situação por um grafo, visando aumentar a familiaridade com esta nova ferramenta. O problema é o seguinte: Em um país há nove cidades, cujos nomes são 1, 2, 3, 4, 5, 6, 7, 8 e 9. Existem estradas ligando duas cidades sempre que o número formado pelos 2 algarismos lado a lado é múltiplo de 3. É possível viajar da cidade 1 para a cidade 9?

Apresentamos um problema que aparentemente não possui nenhuma relação com grafos: Em um tabuleiro de xadrez 3x3 há 4 cavalos, 2 pretos e 2 brancos, sendo que cada cavalo está em um canto e cavalos da mesma cor estão em diagonal. Existe uma sequência de movimentos específicos que após sua realização os 4 cavalos continuem nos cantos, mas cavalos de cor diferente fiquem em diagonais opostas? A solução apresentada se baseia em uma representação do problema através de um grafo.

Definimos o conceito de grau de um vértice e observamos que, dependendo do problema a ser estudado, olhar apenas os graus dos vértices de um grafo pode fornecer informações não triviais para o problema. Como exemplo, damos uma solução ao problema das Pontes de Königsberg.

Em um país há 100 cidades, e sabemos que de cada cidade partem exatamente 4 estradas diretas para outras cidades. Quantas estradas existem no total? Para resolver este problema, aprendemos que às vezes uma contagem a princípio errada pode ser facilmente consertada.

Aplicamos a técnica de contagem dupla apresentada na aula anterior para resolver a seguinte questão: É possível construir um polígono com exatamente 30 diagonais?

Formalizamos a ideia apresentada nas duas aulas anteriores de contagem dupla, colocando-a na forma de um teorema. O teorema diz que em qualquer grafo a soma dos graus de todos os vértices é igual ao dobro do número de arestas. Utilizamos este resultado para resolver o problema abaixo.Em um certo país existem 200 estradas no total, sendo que uma estrada sempre conecta duas cidades distintas. É possível que de cada cidade partam exatamente 3 estradas?

É possível desenhar 9 segmentos de reta no plano de maneira que cada segmento intersecte exatamente 3 outros? Nesta aula, iremos resolver este problema modelando-o através de um grafo. Mostraremos que esta construção é impossível de ser realizada, utilizando o Teorema da Soma dos graus dos vértices de um grafo e uma análise de paridade. Ao final, mostramos que em qualquer grafo a quantidade de vértices de grau ímpar deve ser necessariamente par.

Suponha que em um país existam 15 cidades e que de cada cidade partam pelo menos 7 estradas. Nesta aula mostramos que para quaisquer das duas cidades escolhidas existe um caminho de estradas ligando estas duas cidades, possivelmente passando por outras no meio do percurso. A propriedade que demonstramos é um conceito importante em teoria dos grafos, conhecido como conexidade. Intuitivamente, um grafo é conexo se ele "tem apenas um pedaço", ou seja, se quaisquer dois vértices estão conectados através de um caminho andando pelas arestas do grafo. Ao final, generalizamos o problema anterior para um país com um número n de cidades.

Como vimos na aula anterior, uma propriedade interessante que um grafo pode ter é ser conexo, isto é, quaisquer dois vértices do grafo estarem conectados por um caminho de arestas do grafo. O que podemos dizer de um grafo quando ele não é conexo? Nesta aula veremos que no caso de um grafo ser desconexo nós podemos decompor o grafo em componentes conexas, ou seja, decompomos o grafo nos seus pedaços que são conexos.

Suponha que estamos trabalhando com um grafo conexo e deletamos uma de suas arestas. O novo grafo obtido agora pode não ser mais conexo. Nesta aula provamos formalmente um fato que pode parecer evidente, mas dá algum trabalho para justificar: demonstramos que após deletar a aresta, ou o grafo obtido continua sendo conexo ou então ele possui exatamente duas componentes conexas.

Considere um país em que cada cidade está conectada a exatamente 100 outras cidades diretamente por estradas. Além disto, pode-se ir de qualquer cidade a qualquer outra passando, possivelmente, por cidades intermediárias. Um dia, uma das estradas é fechada para manutenção. Mostre que ainda assim é possível ir de qualquer cidade a qualquer outra utilizando as estradas em funcionamento. A solução do problema acima envolve de maneira muito bonita resultados e conceitos que vimos em aulas anteriores, o conceito de conexidade e a propriedade de que em qualquer grafo a quantidade de vértices de grau ímpar é necessariamente par.

Apresentamos alguns dos grafos mais comuns que podem aparecer em problemas. Nesta aula apresentamos três exemplos. O primeiro é o grafo completo com n vértices, que possui arestas entre quaisquer dois vértices. O segundo é o grafo complementar de um grafo G dado, que é construído a partir de G utilizando-se o mesmo conjunto de vértices, mas tendo arestas apenas entre vértices que não estavam conectados no grafo original. E o terceiro é o grafo vazio, ou nulo, que é o complementar do grafo completo.

Continuando com a aula anterior, apresentamos mais alguns tipos de grafos que são bastante comuns. Introduzimos mais três tipos de grafos, alguns dos quais já apareceram em aulas anteriores. O quarto exemplo que fornecemos são os grafos k-regulares, isto é, os grafos em que cada vértice possui exatamente k arestas partindo dele. O quinto exemplo é o ciclo de n vértices e o sexto exemplo é o caminho de n arestas.

Introduzimos mais tipos especiais de grafos. O sétimo tipo que apresentamos é a árvore,que por definição é um grafo conexo e sem ciclos. O oitavo é a floresta, que nada mais é do que um grafo em que todas as suas componentes conexas são árvores. O último tipo de grafo que apresentamos é o grafo bipartido.

Apresentamos e demonstramos duas propriedades importantes de uma árvore. Nas aulas anteriores, definimos árvore como sendo um grafo conexo e sem ciclos. Esta definição faz com que as árvores sejam um tipo bastante especial de grafo. Provaremos que: 1. Toda árvore (excluindo-se a árvore que é composta por apenas um vértice isolado) possui ao menos um vértice de grau 1 (isto é, uma folha) . 2. Se uma árvore tem n vértices, então ela possui n-1 elos.

Uma certa rede de vôlei possui 20x50 quadradinhos. Com o passar do tempo, alguns dos barbantes que conectam os vértices dos quadradinhos podem se romper, entretanto, será necessário que vários barbantes arrebentem para que a rede se desfaça em dois ou mais pedaços. Qual é o número máximo de barbantes que podemos cortar de modo que a rede continue em um pedaço após os cortes? Veremos que este problema tem uma relação muito forte com árvores, isto é, grafos conexos e sem ciclos. A solução apresentada, mais do que simplesmente resolver o problema acima, nos diz que qualquer grafo conexo possui um subgrafo com o mesmo número de vértices e que também é uma árvore.