Aula 21 - Grafos - Matemática Discreta 2021 2

Aula 21 Grafos MAT13700 Matematica Discreta Ricardo Tipo de grafos Um grafo G e conexo se para quaisquer dois vertices u e v existe um caminho ligando u e v Tipos de grafos Árvore Tipos de grafos Uma arvore e um grafo conexo sem ciclos Uma floresta e um grafo sem ciclos Grafos Mostre que numa festa com um numero ımpar pessoas existe sempre uma pessoa que conhece um numero par de outras pessoas Grafos Mostre que se um grafo tem um numero ımpar de vertices entao existe um vertice de grau par Grafos Mostre que se um grafo tem um numero ımpar de vertices entao existe o numero de vertices de grau par e ımpar Grafos Mostre que se um grafo tem um numero ımpar de vertices entao existe o numero de vertices de grau par e ımpar Mostre que se um grafo tem um numero par de vertices entao existe o numero de vertices de grau par e par Grafos Teorema O numero de vertices de grau ımpar num grafo e par 2A gu gu 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 Circuito euleriano Um circuito em um grafo G e e uma sequˆencia v1 v2 vk de vertices tais que vi e vi1 sao adjacentes para i 1 2 k 1 que nao repete arestas e tal que o vertice final e o vertice inicial Um circuito euleriano em um grafo G e um circuito que contem todas as arestas de G Um grafo e euleriano se possui um circuito euleriano Grafo euleriano Teorema Um grafo conexo nao trivial G e euleriano se e somente se todos os seus vertices sao de grau par Grafo euleriano Teorema Um grafo conexo nao trivial G e euleriano se e somente se todos os seus vertices sao de grau par Demonstracao Suponha que G e um grafo conexo naotrivial euleriano Entao existe um circuito v1 v2 vℓ que contem todas as arestas de G Seja u um vertice de G Como G e nao trivial e o caminho contem todas as arestas entao u vk para pelo menos um k entre 1 e ℓ Quando u vk considere as arestas vk1vk e vkvk1 que nao se repetem Estas arestas somam 2 no grau de u O mesmo acontece quando o circuito passa de novo por u Grafo euleriano Teorema Um grafo conexo nao trivial G e euleriano se e somente se todos os seus vertices sao de grau par Grafo euleriano Suponha que o grau de todos os vertices de G sao par Escolha um vertice v1 Como G e conexo e nao trivial existe uma aresta ligando v1 a um outro vertice v2 Como o grau de todo vertice e par existe uma aresta ligando v2 a um vertice v3 v1 Como v3 tem grau par temos uma aresta ligando v3 a um vertice que pode ser v1 ou um novo vertice v4 Se for v1 obtemos um ciclo C Se v4 v1 continuamos o processo Note que sempre que chegamos em um vertice este vertice tem um numero ımpar de arestas nesta sequˆencia ou o vertice e v1 Como o grafo e finito em algum momento voltamos a v1 Entao obtemos um circuito C Se C contem todas as arestas de G entao C G e terminamos Grafo euleriano Se C G entao remova de G todas as arestas em C obtendo um novo grafo G nao necessariamente conexo mas com todos os vertices de grau par Como G e conexo existe um vertice em comum entre G e cada componente conexa de G Repita o processo anterior em cada componente conexa comecando pelo vertice em comum com C Depois de um numero finito de repeticoes obtemos G Grafo euleriano 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