lista03 (1)-Parente

Prévia do material em texto

UFBA
Instituto de Computação
MATA53 – Teoria dos Grafos – 2023.2
Professor: Roberto Freitas Parente
Exerćıcios 03
Entrega: Sempre verifique o horário e data de cada entrega no AVA/Moodle.
(Formato digital (PDF) somente pelo Moodle – Preferencialmente LATEX)
Última atualização: 6 de novembro de 2023
A listas deverão ser realizadas por 2 (dois) ou 3 (três) estudantes. Vocês devem indicar o nome da
dupla para cada submissão. Caso seja detectado plágio entre equipes em uma das listas, a sua nota de todas
as lista serão zeradas.
• Respostas sem a devida explicação não serão aceitas.
Exerćıcio 1 (Entrega: 13/11/2023). Prove o seguinte sobre conectividade de grafos.
1. Seja G um grafo conexo com pelo menos três vértices. Faça G a partir de G através da adição de arestas
entre vértices x, y sempre que dG(x, y) = 2. Prove que G
′ é 2-conexo.
2. Prove que κ(G) = κ′(G) = 3 quando G é um grafo simples com ∆(G) ≤ 3.
Exerćıcio 2 (Entrega: 13/11/2023). Prove ou dê contraexemplo para cada desigualdade: É verdade que para
todo grafo G e todo vértice v ∈ E(G) temos
1. κ(G)− 1 ≤ κ(G− v) ≤ κ(G)?
2. κ′(G)− 1 ≤ κ′(G− v) ≤ κ′(G)?
Exerćıcio 3 (Entrega: 13/11/2023). Use o Teorema de Menger para provar κ(G) = κ(G) quando G é 3-regular.
Exerćıcio 4 (Entrega: 13/11/2023). Prove o desprove:
1. Todo grafo G k-coloŕıvel G tem uma k-coloração própria em que alguma classe de cor tem α(G) vértices
2. Se G = F ∪H, então χ(G) ≤ χ(G) + χ(H).
3. Todo grafo G tem χ(G) ≤ n− α(G) + 1
4. Se G é um grafo conexo, então χ(G) ≤ 1 + d̄(G), onde d̄(G) é o grau médio de G.
Exerćıcio 5 (Entrega: 13/11/2023). Faça o seguinte
1. Detemine χ′(G) onde G = Cn□K2.
2. Obtenha uma inequação para χ′(G) em termos de e(G) e α′(G), quantidade de arestas e emparelhamento
máximo respectivamente.
Exerćıcio 6 (Entrega: 13/11/2023). Estude o que é o grafo linha L(G) de G e determine a quantidade de
triângulos em L(H), onde H é o grafo de petersen.
Exerćıcio 7 (Entrega: 13/11/2023). Prove que todo grafo bipartido k-regular com k ≥ 2, têm k emparelha-
mentos perfeitos disjuntos. Ademais, utilizando esse primeiro resultado, conclua o Teorema de König em que
afirma se G é bipartido, então χ′(G) = ∆(G).
Exerćıcio 8 (Entrega: 13/11/2023). Sejam G e H grafos simples não triviais. Prove que
• χ′(H) = ∆(H), implica que χ′(G□H) = ∆(G□H).
• χ(G□H) = max{χ(G), χ(G)}.
Exerćıcio 9 (Entrega: 13/11/2023). Um museu de arte tem uma grande sala cujo contorno é um poĺıgono
fechado, não necessariamente convexo, com n lados. Queremos postar guardas em alguns dos vértices do poĺıgono
de modo que cada ponto da sala possa ser visto por pelo menos um dos guardas (o ângulo de visão de cada guarda
só é limitado pelas paredes da sala). Mostre que ⌊n/3⌋ guardas são suficientes. Mostre que há salas que precisam
de ⌊n/3⌋.
Dica: Modele o problema como um grafo e utilize alguma forma de coloração.
1