Slide - Teorema de Euler - 2022-2

Teoria dos Grafos Luerbio Faria e Diana Sasaki Nobrega IME-UERJ 2022 Teoria dos Grafos Ementa 1 Uma introdução à Teoria dos Grafos 2 Grafos e subgrafos, 3 Conjuntos independentes e cliques, 4 Classes Principais, 5 Coloração, 6 Emparelhamentos, 7 Conectividade, 8 Trilhas Eulerianas, 9 Ciclos Hamiltonianos, 10 Grafos orientados, 11 Árvores e Florestas, 12 Planaridade, 13 Complexidade de Algoritmos, classes P, NP e NP-completo. Bibliografia 1 J. A. Bondy, U. S. R. Murty. Graph theory with applications. Macmillan, 1978. 2 D. B. West. Introduction to graph theory. 2nd Ed. Prentice Hall, 2001. 3 J. L. Szwarcfiter. Teoria Computacional dos Grafos. Elsevier, 2018. 4 M. R. Garey and D. S. Johnson. Computers and intractability, A Guide to the Theory of NP-completeness, 1979 Introdução O Teorema de Euler Existe um trajeto deste tipo, então o número de pontes em cada região de terra firme é par. Existe um trajeto deste tipo, se e somente se o número de pontes em cada região de terra firme é par. Existe um trajeto deste tipo, então o número de pontes em cada região de terra firme é par. Existe um trajeto deste tipo, se e somente se o número de pontes em cada região de terra firme é par e o diagrama geral é conexo. Grafo Definição Um grafo é um par G “ pV, Eq, onde V é um conjunto finito não vazio de vértices, e E é o conjunto de arestas formado por pares não ordenados de distintos elementos de V . Denotamos a ordem de G por n “ |V| e m “ |E|. Se uv P E dizemos que u é adjacente a v e que u e v são vértices adjacentes . Dizemos que a aresta uv incide no vértice u e no vértice v. Vamos dizer também que u e v são as extremidades (endpoints) de uv. Vizinhanças+Graus Definição Se uv P E, dizemos tambem que u é vizinho de v e que Npvq “ tu : uv P Eu é a vizinhança aberta ou vizinhança de v em G. A vizinhanca fechada de v em G é o conjunto Nrvs “ Npvq Y tvu. Se S Ă V denotamos por NSpvq “ Npvq X S a vizinhanca de v em S . O grau dpvq de v em G é dpvq “ |Npvq|. O grau máximo e o mínimo de um grafo são denotados, respectivamente, por ∆ e δ. Se dpvq “ 0, então v é dito isolado, e se e dpvq “ 1, então v é dito pendente. Vizinhanças+Graus Dado o grafo G “ pV, Eq, preencha a tabela: v P V Npvq Nrvs dpv q a tb, c, eu ta, b, c, eu 3 b ta, cu ta, b, cu 2 c ta, b, du ta, b, c, du 3 d tc, eu tc, d, eu 2 e ta, du ta, d, eu 2 δ “ 2 ∆ “ 3 Como representar um grafo Definição Dado um grafo G “ pV, Eq com Mnˆn a matriz de adjacência de G satisfaz que: mi,j “ "1, se ij P E, 0, se ij R E. A B C G W E » fi M6ˆ6 “ A B C G W E ——— ———– 0 0 0 1 1 1 ffiffiffiffiffi ffifl 0 0 0 1 1 1 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 0 0 0 Teorema de Euler Teorema Dado um grafo G “ pV, Eq, então řvPVdpvq “ 2m. Demonstração. Dado um grafo G “ pV, Eq com Mnˆn a matriz de adjacência de G. Nela, temos que: mi,j “ "1, se ij P E, 0, se ij R E. Assim, se somarmos a linha correspondente ao vértice v de V teremos dpvq. Se somarmos todas as linhas de M teremos ř vPVdpvq. Como cada aresta ij de E corresponde um 1 em mi,j “ 1 e um 1 em mj,i “ 1. Temos a prova do Teorema. Passeios, Trilhas e Caminhos 1 Dado um grafo G “ pV, Eq. Uma sequência S “ pv0, v1, v2, . . . , vk q, k ě 0 onde vi P V, e vivi`1 P E é chamada de um passeio em G. 2 Dizemos que os vértices vi e vi`1 são consecutivos em S. O valor k é o comprimento do passeio S ou o número de arestas de S, contadas com ou sem repetição. 3 Se o passeio tem v0 “ vk então S é fechado. Se o passeio S não repete arestas, então S é uma trilha . 4 Se uma trilha S não repete vértices então S é um caminho . 5 Um ciclo e uma trilha S fechada com uma única repetição de vértices e com comprimento maior ou igual à três. 6 Um grafo G “ pV, Eq é acíclico se G não tem ciclos. Passeios, Trilhas e Caminhos Dado o grafo G “ pV, Eq dê: 1 Um passeio que não é trilha. 2 Uma trilha que não é caminho. 3 Um caminho máximo de G. 4 Todos os ciclos de G. Supergrafos e Subgrafos Definição Dado um grafo G “ pV, Eq. 1 Dizemos que um grafo H é subgrafo de G se V pHq Ă VpGq e EpHq Ă EpGq. 2 Dizemos que H é subgrafo próprio de G se H é subgrafo de G, e VpHq ‰ VpGq ou EpHq ‰ EpGq. 3 Se H é subgrafo de G, dizemos que G e um supergrafo de H. 4´Dado S Ă V . O subgrafo de G induzido por S é GrSs “ VpGrSsq, EpGrSsq ¯ “ ´ S, tuv : u, v P S, uv P EpGqu ¯ . Supergrafos e Subgrafos 1 G não é subgrafo de J, pois EpGq Ć EpJq nem J é subgrafo de G, pois EpJq Ć EpGq. 2 H é subgrafo de G induzido por ta, c, d, eu. 3 F não é subgrafo de G induzido por ta, b, c, d, eu, pois ac R EpFq. Isomorfismo Definição Dados 2 grafos G e H. Dizemos que G e H são isomorfos se existe uma função bijetora f : VpGq Ñ VpHq tal que uv P EpGq se e somente se f puqf pvq P EpHq. E neste caso, f é chamada de função de isomorfismo de G em H. Isomorfismo 1 Por quê G não é isomorfo a F? 2 F é isomorfo a H. Isomorfismo 2 F é isomorfo a H. x f pxq NF pxq NH pf pxqq a I tb, f , hu tII, V , IV u b II ta, c, gu tI, III, IV u c III tb, d, hu tII, IV , VIIu d VII tc, g, eu tIII, IV , VIIu e VIII td, f , hu tIV , V , VIIu f V ta, g, eu tI, VI, VIIIu g VI tb, d, f u tII, V , VIIu h IV ta, c, eu tI, III, VIIIu Grafo Complemento Definição Dado um grafo G “ pV, Eq, o complemento G “ pV, Eq de G satisfaz que E “ tuv : uv R Eu. a b c b c a e d G e d G n=5 m=6 n=5 m=4 Theorem |EpGq| ` |EpGq| “ `n 2 ˘“n! pn´2q!2! “npn´1q 2. Grafos Autocomplementares Definição Dizemos que G é autocomplementar se G é isomorfo à G. Mostre que os seguintes grafos são autocomplementares. Exemplos de grafos autocomplementares b b c c a a e d e d G G Isomorfismo f : VpGq Ñ VpGq v f pVpGqq a a b c c e a b c d ab c d G G Isomorfismo g : V pGq Ñ V pGq v gpVpGqq a c b a c d d b d b e d O valor de n em um grafo autocomplementar Theorem Se G “ pV, Eq é autocomplementar, então para algum k P N, n “ 4k ou n “ 4k ` 1. Índice Remissivo I ∆, 8 δ, 8 adjacente, 7 aresta, 7 caminho, 12 ciclo, 12 comprimento de passeio, 12 extremidades, 7 fechado, 12 grafo, 7 grafo autocomplementar, 20 grafo complementar, 19 grau, 8 incidente, 7 isolado, 8 isomorfismo, 16 matriz de adjacência, 10 ordem, 7 passeio, 12 pendente, 8 subgrafo, 15 subgrafo induzido, 15 supergrafo, 15 trilha, 12 vizinhança, 8 vizinhança em um conjunto S, 8 vizinhança fechada, 8 vizinho, 8 vértice, 7