Resumo do meu curso de Matemática Discreta - Parte 3: Teoria dos Grafos

Essa é a parte 3 do resumo do meu curso de Matemática Discreta. Separei ele em 3 partes, uma parte pra cada prova.

Você pode conferir a parte 1 e parte 2 aqui:

Resumo do meu curso de Matemática Discreta – Parte 1: Análise Combinatória

Resumo do meu curso de Matemática Discreta – Parte 2: Recorrências e Teoria das probabilidades

Quase todos os dias, após as aulas, eu vinha aqui escrever o que o professor passou.

Separei o resumo em resumo e comentários. O resumo é o que está seguido de bolinhas e os comentários não.

Lista das aulas

— publicidade —

Aula 15: começo da parte de grafos, matriz de adjacência, 4 teoremas sobre grafos e muitas definições

Começo do conteúdo da P3, que é grafos.

Eu perdi os primeiros 40 minutos da aula porque fiquei conversando com um amigo.

Acho que no começo da aula o professor deu a definição de grafo e um problema motivador sobre apertos de mão. Além disso ele definiu matriz de adjacência de um grafo.

Creio que a definição de grafo seja um conjunto de vértices e um conjunto de arestas, que é um conjunto de pares não ordenados de vértices.

Definição de grau de um vértice, que é a quantidade de arestas à qual ele pertence.

Meio que o conjunto de arestas é uma relação no conjunto de vértices. Só não é exatamente isso porque as arestas não são pares ordenados.

Acho que um vértice pode não pertencer a nenhuma aresta, isto é, ele pode não estar conectado.

3 fatos estranhos sobre a quantidade de vértices de graus par ou ímpar de um grafo qualquer.

Enunciamento de que a soma de todos os graus dos vértices de um grafo é sempre par.

Acho que isso eu consigo explicar em breve.

Definição de subgrafo, grafo completo, grafo complementar, grafo estrelado, caminho, ciclo, grafo conexo, passeio e componente conexo (que tem que ser um subgrafo conexo maximal).

Aula 16: multigrafos, problema das pontes de Konisberg e árvores

Resolução do problema das pontes de Konisberg, que é o problema que deixou Euler famoso.

O argumento é que o problema não tem solução pois há 4 vértices de grau ímpar e só poderia haver 0 ou 2 vértices assim por algum motivo.

Definição de multigrafo, que é um grafo onde pode haver mais de uma aresta ligando os mesmos vértices. O grafo das pontes de Konisberg é um multigrafo.

Definição de caminho em multigrafos.

Definição de caminho euleriano em multigrafos.

Enunciamento das seguintes 3 propriedades de um multigrafo conexo $G$: se $G$ tem mais de 2 vértices com grau ímpar então não existe caminho euleriano em $G$. Se $G$ tem exatamente 2 vértices com grau ímpar então existe caminho euleriano em $G$ e esses 2 vértices são os extremos do caminho. Se $G$ não tem vértices de grau ímpar então existe caminho euleriano em $G$, e nesse caso todo caminho euleriano é fechado.

Tem mais duas propriedades, mas fiquei com preguiça de copiar e não tirei foto.

Definição de ciclo hamiltoniano.

Apresentação ao grafo de Petersen.

Depois disso voltamos aos grafos normais para estudar árvores.

Definição de árvore.

Enunciamento de que um grafo é uma árvore se e só se é conexo mas se deletarmos qualquer aresta ele fica desconexo.

Enunciamento de que um grafo é uma árvore se e só se ele não tem ciclos mas se adcionarmos uma aresta geramos um ciclo.

Aula 17: mais árvores e fórmula de Euler

Prova de que um grafo é uma árvore se e só se é conexo mas se deletarmos qualquer aresta ele fica desconexo.

Exercício pra casa: provar que um grafo é uma árvore se e só se ele não tem ciclos mas se adcionarmos uma aresta geramos um ciclo.

A prova é muito bonita porque ela feita só com palavras e até uma criança de 10 anos entenderia se você ensinasse pra ela as definições. Mas mesmo assim é difícil pra caramba. Ela é feita por absurdo.

O professor disse que árvores não é assunto da ementa, mas ele quis passar pois elas aparecem em todo lugar.

Enunciamento de que toda árvore com pelo menos dois vértices tem 2 vértices de grau 1.

Enunciamento de que toda árvore com $n$ vértices tem $n-1$ arestas.

Definição de grafos isomorfos, que meio que são grafos com desenhos diferentes mas que são iguais.

Definição de grafo planar.

As arestas não precisam ser segmentos de reta, só lembrar da definição de aresta em termos de conjuntos pra perceber isso.

Fórmula de Euler.

Prova por absurdo (usando a fórmula de Euler) de que um grafo lá que parece um símbolo satânico não é planar.

Aula 18: prova da fórmula de Euler e dedução do número máximo de arestas de um grafo planar

Prova da fórmula de Euler. A prova é por indução no número de vértices, e tem que separar em 2 casos.

Prova de que um grafo planar com $n$ vértices tem no máximo $3n – 6$ arestas. A prova usa a fórmula de Euler.

Nessa parte da aula o professor disse que chamamos as regiões delimitadas pelas arestas de faces porque quando Euler estava estudando isso ele fazia estudando poliedros.

Onde estão as aulas 19 a 21

Foram aulas de exercícios da matéria da P2 e a P2, por isso as coloquei na parte 2 do resumo.

Aula 22: outra prova da fórmula de Euler e colorindo grafos

Definição de mapa planar.

Prova de que o número de faces + número de vértices = número de lados + 2 (fórmula de Euler).

Prova de que é possível pintar $n$ círculos com duas cores de forma com que círculos adjascentes fiquem com cores diferentes.

Definição de grafo bipartido e resolução de um exemplo usando isso.

Aula 23: prova de muitos teoremas sobre colorir grafos

Explicação de como transformar um mapa num grafo.

Enunciação e prova do teorema: Seja $G$ um grafo planar cujo vértice de maior grau é $d$. Então $G$ é colorível com $d+1$ cores.

Colorir um grafo é dar cores pros vértices de tal forma que dois vértices adjascentes não possuem a mesma cor.

Colorir grafos é um pouco contra intuitivo, mas colorir mapas não.

Enunciação e prova do teorema: se todo subgrafo de um grafo planar $G$ tem um vértice de grau menor ou igual a $d$ então $G$ é colorível com $d+1$ cores.

Enunciação e prova do teorema: todo grafo planar tem um vértice de grau menor ou igual a 5.

Enunciação e prova do teorema: todo grafo planar é colorivel com 6 cores.

Aula 24: teorema das 5-cores

Prova de que todo grafo planar é 5-colorível.

A prova é por indução e é muito bonita.

Aula 25: aula de dúvidas

Aula de dúvidas.

Aula 26: P3

Coisas que aprendi nessa parte

Coisas sobre grafos que aprendi ao longo do curso:

Para mostrar que qualquer grafo possui dois ou mais vértices com o mesmo grau se usa princípio das gavetas.
O número de arestas do grafo de arestas é $ \sum_{v \in V} {g(v) \choose 2} $
O triângulo é um grafo de 3 vértices completo.
A notação para grafo completo com $n$ vértices é $K_n$.
A matriz de adjacência de um grafo não orientado é sempre simétrica (suas linhas são iguais suas colunas).
A soma das linhas de uma matriz de adjacência é o grau do vértice.
Num grafo completo, todos os vértices tem o mesmo grau.
Num caminho quase todos os vértices tem grau par.
A prova de que todo grafo tem um número par de vértices de grau ímpar é por indução no número de arestas.
As mesmas árvores que construimos nos problemas de combinatória são as árvores que são grafos conexos e sem ciclos.
Praticamente todas as provas em teoria dos Grafos é feita por indução no número de vértices ou arestas.
É bem legal usar o teorema das 4 cores de forma política, pois ele diz que é possível 4 correntes políticas estarem espalhadas pelo mundo de forma que nenhum país da corrente A faça fronteira com outros países da corrente A.
O $K_5$ pode ser representado por uma estrela num pentágono.
Deduzir quantos subgrafos um grafo tem é difícil.
A fórmula de Euler é a melhor ferramenta para estudar grafos planares.
Provar que em todo grafo conexo retirar uma aresta de um ciclo dele não faz ele ficar desconexo é difícil, mas muito importante.
As provas na Teoria dos Grafos são feitas com palavras, e usa-se muito pouco de teoria dos Conjuntos nelas. Isso faz elas ficarem muito bonitas, mas também ficam parecendo argumentos não necessariamente válidos.
Todo grafo sem ciclo ímpar é bipartido, pois ele é 2-colorível.

Diário de Estudos

Eu nunca mais farei um resumo de um curso meu. Isso deu MUITO trabalho e não me fez aprender mais sobre as matérias.

Pelo menos espero que esse resumo sirva de curiosidade para aqueles que querem ter uma noção do que vemos na faculdade de matemática e que ele prove meu ponto de que a quantidade de conteúdos que vemos é absurda, e por isso não da pra aprender tudo.

Muito obrigado por ter chegado até aqui ^^