Videoaula
- Videoaula 18
- Caderno de Exercícios 1
- Aplicativo 1
- Teste
- Material Teórico 2
Outros Conteúdos da Aula
Introdução à Teoria dos Grafos – Aula 1 – O que é um grafo?
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.
Introdução à Teoria dos Grafos – Aula 2 – Alguns problemas simples
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.
Introdução à Teoria dos Grafos – Aula 3 – Conectando cidades
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?
Introdução à Teoria dos Grafos – Aula 4 – Um problema com peças de xadrez
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.
Introdução à Teoria dos Grafos – Aula 5 – Grau de um vértice
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.
Introdução à Teoria dos Grafos – Aula 6 – Contando estradas duas vezes
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.
Introdução à Teoria dos Grafos – Aula 7 – Outra aplicação da contagem dupla
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?
Introdução à Teoria dos Grafos – Aula 8 – Soma dos graus dos vértices
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?
Introdução à Teoria dos Grafos – Aula 9 – Soma dos graus e paridade
É 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.
Introdução à Teoria dos Grafos – Aula 10 – Conexidade
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.
Introdução à Teoria dos Grafos – Aula 11 – Dividindo grafos em componentes conexas
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.
Introdução à Teoria dos Grafos – Aula 12 – Criando componentes ao deletar uma aresta
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.
Introdução à Teoria dos Grafos – Aula 13 – Uma estrada em manutenção
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.
Introdução à Teoria dos Grafos – Aula 14 – Tipos especiais de grafos 1
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.
Introdução à Teoria dos Grafos – Aula 15 – Tipos especiais de grafos 2
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.
Introdução à Teoria dos Grafos – Aula 16 – Tipos especiais de grafos 3
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.
Introdução à Teoria dos Grafos – Aula 17 – Árvores
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.
Introdução à Teoria dos Grafos – Aula 18 – Cortando uma rede de vôlei
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.
Em Breve!
Em Breve!
Graus de Um Grafo
O grau de cada vértice é uma informação importante de um grafo. Você consegue construir um grafo a partir das informações dos graus dos seus vértices?
Em Breve!
Introdução à Teoria dos Grafos - Parte 1
Introduzimos alguns conceitos simples relativos a grafos, ilustrados pela análise de exemplos interessantes
Introdução à Teoria dos Grafos - Parte 2
Continuamos a exposição dos principais conceitos elementares sobre teoria dos grafos, estudando, dentre outros, as ideias de conexidade e árvores