Aula 20 - Grafos - Matemática Discreta 2021 2

Aula 20 Grafos MAT13700 Matematica Discreta Ricardo Pontes de Konisberg Figura By Bogdan Giusca Public domain PD Pontes de Konisberg A cidade era divida por bracos de rios em 4 distritos que eram conectados por 4 pontes E possıvel caminhar pela cidade passando por cada ponte apenas uma vez e voltando para o ponto original Pontes de Königsberg Pontes de Königsberg Grafos Um grafo simples e naoorientado e um conjunto de vertices V e um conjunto de arestas A u v u v V u v G V A Dois vertices u e v que sao conectados por uma aresta sao chamados de adjacentes ou vizinhos denotamos por u v e a aresta por uv ou vu Grafos Grau de um vertice O numero de arestas que chegam incidem de um dado vertice e chamado grau do vertice Grau de um vértice Tipo de grafos Vazio Trivial Completo Kn Tipo de grafos Complementar overlineG Tipos de grafos Subgrafo Tipos de grafos O grafo H V A e um subgrafo de G V A se V V e A A denotamos H G Passeios caminhos ciclos Um passeio em um grafo G e uma sequˆencia v1 v2 vk de vertices tais que vi e vi1 sao adjacentes para i 1 2 k 1 O vertice v1 e o vertice inicial o vertice vk e o vertice final e k e o comprimento do passeio Uma trilha em um grafo G e um passeio que nao repete arestas mas pode repetir vertices Passeios caminhos ciclos Passeios caminhos ciclos Um circuito em um grafo G e uma trilha tal que o vertice inicial e o vertice final Um caminho e uma trilha que nao repete vertices Um ciclo e uma trilha tal que o vertice inicial e o vertice final mas nenhum outro vertice e repetido Passeios caminhos ciclos Tipo de grafos Tipo de grafos Um grafo G e conexo se para quaisquer dois vertices u e v existe um caminho ligando u e v Conexidade Sejam a b e c vertices de um grafo G Suponha que a e b estao ligados por um caminho C e b e c estao ligados por um caminho D Entao existe um caminho ligando a e c Conexidade Uma componente conexa de um grafo G V A e um subgrafo H V A conexo tal que se I e um subgrafo conexo de G tal que H I entao H I Tipos de grafos Árvore Tipos de grafos Uma arvore e um grafo conexo sem ciclos Uma floresta e um grafo sem ciclos Referˆencias 1 Matematica Discreta Lovasz Pelikan Vesztergombi 2 Analise Combinatoria e Probabilidade Morgado Pitombeira Carvalho e Fernandez 3 Matematica Comcreta Graham Knuth Patashnik 4 Princıpios de Combinatoria e Probabilidade Tertuliano Franco SBM 2020 5 Matematica Discreta Morgado e Carvalho PROFMAT 6 httpsenwikipediaorgwikiSevenBridgesof Konigsberg