·

Matemática ·

Matemática Discreta

· 2022/2

Send your question to AI and receive an answer instantly

Ask Question

Preview text

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