prova03-Parente-2023.2

Prévia do material em texto

UFBA
Instituto de Computação
MATA53 – Teoria dos Grafos – 2023.2
Professor: Roberto Freitas Parente
Avaliação 03
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 é 13, mas a nota máxima é 10, i.e., Nota = min{pontuação obtida, 10}.
- , Escolha bem as questões que você fará! BoA Provaa!! , -
Questão 1 (3.0 pts). Escolha 5 (cinco) 6 (seis) itens e defina formalmente os seguintes conceitos:
1. Coloração de arestas e número cromático;
2. Clique e conjunto independênte
3. κ(G), κ′(G)
4. Grafo k-conexo
5. Grafo planar e Grafo plano
6. para f ∈ F (G) defina gr(f)
7. Grafo bicoloŕıvel
Questão 2 (3.0 pts). Prove os seguintes:
1. Se G é um grafo plano, então ∑
f∈F (G)
gr(f) = 2|E(G)|
2. 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. 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). Imagine que sua turma estava discutindo sobre como organizar um mapa de um jogo de RPG
chamado Parentolândia. Após determinada as fronteiras e o nome das regiões, estava-se discutindo qual era a melhor
forma de pintar o mapa se seria gulosa ou aleatória, pois é razoável que cada região vizinha não tenha a mesma cor.
Durante a discussão, você lembrou que na disciplina de Teoria dos grafos o seu professor querido Roberto Parente comentou
que um grafo planar tem número cromático no máximo 4. Supondo que essa informação é verdadeira, faça o seguinte:
• Escreva o teorema de forma precisa.
• Usando o teorema, detalhe para seus amigos como seria posśıvel utilizar o teorema no mapa do jogo.
Questão 4 (2.0 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.
Questão 5 (1.0 pts). Mostre que G é bicoloŕıvel se, e somente se, não contém ćıclos ı́mpares
Questão 6 (2.0 pts). Sejam G e H grafos simples não triviais. Prove que
1. χ′(H) = ∆(H), implica que χ′(G□H) = ∆(G□H).
2. χ(G□H) = max{χ(G), χ(H)}.
1