Aula 23 - Grafos - Matemática Discreta 2021 2

Aula 23 Grafos MAT13700 Matematica Discreta Ricardo 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 Formula de Euler Vamos mostrar primeiro que a formula de Euler vale para arvores uma arvore e um grafo conexo e sem ciclos Proposicao Seja G V A uma arvore Entao A V 1 Fómula de Euler Formula de Euler Proposicao Seja G V A um grafo As afirmacoes abaixo sao equivalentes 1 G e uma arvore 2 G e conexo e A V 1 3 G nao tem ciclos e A V 1 Demonstracao Ja temos que 1 implica em 2 e 3 Basta ver que vale 2 se e somente se vale 3 Fómula de Euler Formula de Euler Como uma arvore so tem a face externa temos V A F 1 1 2 Formula de Euler Demonstracao da Formula de Euler Por inducao sobre o numero de arestas m A menos de isomorfismos Existem 3 grafos conexos com 3 arestas Suponte que la fórmula de Euler es válida para un grafo con m aristas Así m es un grafo con n 1 aristas Si G es un árbol entonces G tiene un ciclo G permite como se tienen n aristas Por inducción 1V1 A1 F 1 2 V A F 2 Formula de Euler Suponha que a formula de Euler seja valida para qualquer grafo planar conexo com m arestas Seja G um grafo planar conexo com m 1 arestas Se G e uma arvore a demonstracao acabou Se G nao e uma arvore entao G Formula de Euler Suponha que a formula de Euler seja valida para qualquer grafo planar conexo com m arestas Seja G um grafo planar conexo com m 1 arestas Se G e uma arvore a demonstracao acabou Se G nao e uma arvore entao G Fórmula de Euler Formula de Euler Exemplo O grafo completo K5 nao e planar Fórmula de Euler Colorindo grafos Uma creche tem seis criancas e duas salas Catarina briga com Bianca Fabio e Emanuel Emanuel briga com Catarina Alice e Daniela e Alice e Bianca tambem brigam E possıvel dividir as criancas nas duas salas para que as brigas nao ocorram Colorindo grafos Quando e possıvel colorir um grafo com 2 cores Ou seja quando e possıvel colorir com 2 cores um grafo de tal forma que vertices adjacentes tenham cores diferentes Colorindo grafos Colorindo grafos Teorema Um grafo e colorıvel com 2 cores se e somente se ele nao contem um ciclo ımpar 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