Aula 22 - Grafos - Matemática Discreta 2021 2

Aula 22 Grafos MAT13700 Matematica Discreta Ricardo 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 v1 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 2 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 Agora considere v1 temos a aresta inicial e a aresta final que contribuem com 2 para o grau de v1 Se o circuito passa por v1 de novo existe uma aresta que chega e uma que saı logo o grau de v1 tambem e par 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 e 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 e portanto ainda existe uma aresta que passa por este vertice que nao foi usada 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 hamiltoniano Um ciclo e um circuito que nao repete vertices Um ciclo hamiltoniano em um grafo G e um ciclo que contem todos os vertices de G Um grafo que contem um cilclo haniltoniano e dito um grafo hamiltoniano Grafo hamiltoniano Teorema de Dirac condicoes suficientes Seja G V A um grafo com n vertices para n 3 Se o grau de cada vertice e maior ou igual a n2 entao G e hamiltoniano k1 gamVk fracm2 Rightarrow k geq fracm2 1 fracm2 fracm2 1 fracm2 Quando dois grafos são iguais V5 A5 F2 V5 A5 F7 557 eq 2 Quando dois grafos sao iguais Dois grafos G V A e G V A sao isomorfos se existe uma bijecao φ V V que preserva vizinhancas ou seja se existe uma aresta uv em A entao existe a aresta φuφv em A Uma funcao φ deste tipo e um isomorfismo de grafos Grafos planares Um grafo e planar se podemos representalo no plano sem que arestas se cruzem Dado uma representacao planar de um grafo G uma face e uma regiao do plano limitada pelas arestas de G A regiao externa e infinita tambem e uma face Grafos planares Formula de Euler Formula de Euler Seja G V A um grafo planar conexo e F o cojunto das faces em representacao planar deste grafo Entao V A F 2 Corolario Seja G um grafo planar conexo O numero de faces de qualquer representacao planar de G e o mesmo Formula de Euler Formula de Euler Sejam P um poliedro V o seu numero de vertices A o seu numero de arestas e F o seu numero de faces Entao V A F 2 Demonstracao Projete o poliedro no plano Fórmula de Euler 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