2 Prova - 2022.2-Parente

Prévia do material em texto

UFBA
INSTITUTO DE COMPUTAÇÃO
MATA53 – Teoria dos Grafos – 2022.2
Professor: Roberto Freitas Parente
Avaliação 02
Nome:
Instruções (leia antes de começar):
• É proibido o uso de qualquer aparelho ou recurso de processamento e/ou comunicação.
• É proibido realizar consulta a qualquer tipo de material.
• A compreensão e interpretação do enunciado é parte integrante da avaliação.
• Respostas sem a devida explicação não serão aceitas.
IMPORTANTE: A soma total de pontos é 16, mas a nota máxima é 10, i.e., Nota = min{pontuação obtida, 10}.
- , Escolha bem as questões que você fará! BoA Provaa!! , -
Teorema 1. (Fórmula de Euler) Se G é um grafo plano conexo, então |V (G)| − |E(G)|+ |F (G)| = 2.
Questão 1 (3,0 pts). Apresente as seguintes definições:
1. Um subgrafo k-fator para k ∈ N
2. Cobertura por vértices
3. κ(G), κ′(G)
4. Grafo planar e face
5. Defina F (G)
6. para f ∈ F (G) defina gr(f)
Questão 2 (3,5 pts). Prove os seguintes:
1. (1,0 pts) Se G é um grafo plano, então ∑
f∈F (G)
gr(f) = 2|E(G)|
2. (1,5 pts) Se G é um grafo planar simples conexo com n ≥ 3 vértices e m arestas, então m ≤ 3n− 6. Ademais, se G
é K3-livre, então m ≤ 2n− 4.
3. (1,0 pts) Se G é um grafo planar simples conexo, então existe um vértice v ∈ V (G) tal que dG(v) ≤ 5.
Questão 3 (2,0 pts). Sejam G um grafo e M,M ′ dois emparelhamentos de G. Prove que o grafo G′ gerado pela diferença
simétrica M△M ′ contém apenas caminhos, vértices e ciclos pares.
Questão 4 (2,0 pts).
1. (1,5 pts) Use o Teorema de König–Egerváry para provar que todo grafo bipartido G tem um emparalhamento de
tamanho pelo menos e(G)/∆(G).
2. (0,5 pts)Use o resultado acima para concluir que todo subgrafo de Kn,n com mais que n(k − 1) arestas tem um
emparelhamento de tamanho pelo menos k.
Questão 5 (3,0 pts). Duas pessoas jogam o seguinte jogo sob um grafo G: Jogador 1 começa pela escolha de qualquer
vértice. Cada escolha subsequente deve ser adjacente à escolha anterior do outro jogador. Desta forma, juntos eles seguem
um caminho. Um jogador ganha quando sua movimentação é a última rodada posśıvel. Prove que o segundo jogador tem
uma estratégia vencedora se G tem um emparelhamento perfeito, e caso contrário o primeiro jogador tem um estratégia
vencedora.
Dica: Para a segunda parte, o primeiro jogador deve começar com um vértice omitido por algum emparelhamento
máximo.
Questão 6 (2,5 pts). Seja G um grafo conexo com pelo menos três vértices. Construa G′ a partir de G pela adição uma
aresta entre u, v ∈ V (G) sempre que dG(u, v) = 2. Prove que G′ é 2-conexo.
1