Lista de Exercicios sobre Teoria dos Grafos e Algoritmos

g Se G possui uma ponte então G possui uma articulação h Se G possui uma articulação então G possui uma ponte i Se G contem Kp como subgrafo então χG p j Se G e são conexos e o diâmetro de é maior que 3 então o diâmetro de é menor que 3 k Se PNP então existe um algoritmo polinomial para todo problema de NP l Se existe um algoritmo polinomial para um problema de NP então PNP m P NP 9 Prove ou refute Não existe grafo Euleriano conexo com número par de vértices e número ímpar de arestas 10 Um grafo é semiEuleriano se existe uma trilha não fechada contendo todos os vértices e todas as arestas de G Prove que G é semiEuleriano se e somente se G possui exatamente 2 vértices de grau ímpar 11 Para cada grafo a seguir diga para quais valores de m e n o grafo é Hamiltoniano Euleriano planar o número cromático χ o tamanho da maior clique ω e o tamanho do maior conjunto independente α com a respectiva justificativa GRAFO HAMIL Eul PLANAR χ ω α Kn1n2 Kn Qn Pn Sn Wn Cn Dodecaedro LQ3 12 Prove que se G é um grafo Euleriano e xy e f xz são duas arestas diferentes de G com um extremo x em comum então G tem uma trilha Euleriana na qual as arestas e f aparecem consecutivamente 13 Mostre que se um grafo G V E é Hamiltoniano então LG é Hamiltoniano 14 Mostre que se um grafo G V E é Euleriano então LG é Euleriano 15 Demonstre se vale o se somente se nas questões 13 e 14 16 Mostre o teorema das 6 cores isto é se G é planar então G é 6colorível 17 Um grafo G V E periplanar outerplanar é planar e possui um desenho plano DG no qual existe uma face com todos os seus vértices Mostre que se G é periplanar e n 3 então existem pelo menos 2 vértices de grau 2 18 Dado que o menor ciclo de um grafo planar tem tamanho pelo menos k e que em uma desenho plano cada face f tem pelo menos 3 df k n a determine o limite superior m kk2 n 2 para o número m de arestas b forneça 3 grafos com k 3 4 5 e verifique o limite c argumente como deve ser o grafo planar para um valor de k cada vez maior 19 Transformações polinomiais e problemas NPcompletos a Defina os problemas de decisão SAT 3SAT COLORAÇÃO CONJUNTO INDEPENDENTE CLIQUE MÁXIMA e COBERTURA POR VÉRTICES Mostre que b SAT3SAT c 3SAT COBERTURA POR VÉRTICES d 3SAT CONJUNTO INDEPENDENTE e CONJUNTO INDEPENDENTE CLIQUE MÁXIMA 1 Na Figura 1 em cada grafo Demonstre e certifique se a são planares b são Hamiltonianos c são Eulerianos rode o algoritmo d encontre o número cromático e o subgrafo planar máximo 2 Determine todas as árvores não isomorfos com 11 vértices e diâmetro 7 3 Determine G com o menor n tal que cuG ceG δ 1 3 3 1 2 3 1 4 3 2 3 4 3 3 3 4 Descreva algoritmos para a Busca em largura b Listar as componentes conexas c Determinar o diâmetro de um grafo 5 Mostre que dois caminhos máximos em um grafo conexo SEMPRE possuem pelo menos um vértice em comum 6 Seja G um grafo com n vértices e m n 1 arestas Prove que as seguintes afirmações são equivalentes a G é conexo b G é acíclico c G é uma árvore 7 Mostre que se todo vértice de G V E possui grau pelo menos n12 então G é conexo 8 Prove ou dê contraexemplo a G e seu complemento não podem ser ambos desconexos b Se G é um grafo bipartido dregular e X Y consiste em uma partição em conjuntos independentes para V então X Y