Prova 2 Teoria dos Grafos UERJ 2022 - Análise e Resoluções

Instituto de Matematica e Estatıstica UERJ Prova 2 de Teoria dos Grafos Professor Luerbio Faria Data 09052022 1 Se n V 3 e G V E tem exatamente 2 vertices u v de grau ımpar Prove ou dˆe um contraexemplo a 05 G u v e Euleriano b 05 Se uv 2 E entao G uv e Eule riano 2 particao a 05 Enuncie a Programacao Dinˆamica do Problema b 10 Rode para a instˆancia S n 1 3 2 4 6 o e construa a tabela c Resolva as instˆancias dizendo se e uma instˆancia Sim ou Nao explicando como obteve a resposta e mostrando o certificado se a resposta for Sim usando a tabela para as instˆancias do problema de decisao da particao i 05 S n 1 3 2 4 6 o ii 05 S n 1 3 2 4 o 3 24 Verifique no grafo a Se e planar b Se e Hamiltoniano c Se e Euleriano d Seu numero cromatico e Sua clique maxima e seu numero de in dependˆencia f Um conjunto dominante mınimo e uma cobertura de arestas mınima por vertices e dˆe o certificado correspondente 4 Considere o grafo G V E e seu complemento G V E b b a b c d e f g a b c d e f g G G h h conjunto independente maximo ci instˆancia Grafo G V E e inteiro positivo k pergunta Existe um conjunto independente S V tal que S k 04 Determine se a instˆancia G 4 e G 5 sao instˆancias Sim de ci 05 Noscasos positivos do item anterior determine os certificados apropriados Considere o problema clique maxima cm instˆancia Grafo G V E e inteiro positivo k pergunta Existe uma clique S V com S k 04 Determine se a instˆancia G 4 e G 5 sao instˆancias Sim de cm 05 Noscasos positivos do item anterior determine os certificados apropriados 05 Prove que o problema clique maxima esta em NP 05 Prove que clique maxima conjunto independente maximo 5 20 Um grafo planar conexo 3regular G V E tem 24 vertices Existe um desenho DG de G so mente com faces quadrangulares e hexagonais De termine os numeros q h de faces quadrangulares e hexagonais de DG 05 EXTRA O desenho do grafo Se n V 3 e G V E tem exatamente 2 vértices u v de grau ímpar Prove ou dê um contraexemplo a 05 G u v é Euleriano b 05 Se uv E então G uv é Euleriano a Falso G diagram G u v diagram b Verdadeiro se G possui apenas 2 vértices de grau ímpar e ambos possuem uma aresta entre si então ao removermos essa aresta teremos apenas vértices de grau par logo o grafo será euleriano a Se é Planar diagram Pelo teorema de Kuratowski o grafo não é planar b Se é Hamiltoniano diagram a i c d f e h g b a c Se é Euleriano Temos 4 vértices de grau ímpar logo o grafo não é euleriano d Seu número cromático wG 4 logo 4 XG XG 4 e Sua clique máxima e seu número de independência wG 4 mI 3 F Um conjunto dominante mínimo e uma cobertura mínima de arestas por vértices CD 6 b c e f i h