Exercicios de grafos

•

UFRGS

guilherme

06/07/2021

Prévia do material em texto

UFRGS – Instituto de Matemática
Departamento de Matemática Pura e Aplicada
PPGMAp - Programa de Pós-Graduação em Matemática Aplicada
MAT 0205 – Métodos Discretos - Semana 13
Os itens 1 e 2 de cada exerćıcio são relacionados e podem ser considerados como uma
sequência de resultados dependentes. Sugerimos que todos façam estes dois itens. Coletiva-
mente, eles têm o objetivo de mostrar que a largura em árvore de um grafo é 1 se, e somente
se, ele é uma floresta.
Exerćıcio 1.
1. Construa uma decomposição em árvore de largure 1 da estrela Sn.
2. Mostre, por indução no número de vértices, que uma árvore admite uma decomposição
em árvore de largura 1.
3. Construa uma decomposição em árvore do grafo da Figura 1 - 1 que não seja uma de-
composição boa.
4. Transforme a decomposição do item anterior em uma decomposição boa, usando o Lema
4.3.
5. Discuta e, se posśıvel, determine a largura em árvore do grafo.
Exerćıcio 2. Os itens 1 e 2 são subsequentes aos itens 1 e 2 do Exerćıcio 1.
1. Conclua que uma floresta tem largura em árvore 1.
2. Construa uma decomposição em árvore do ciclo Cn de largura 2.
3. Construa uma decomposição em árvore do grafo da Figura 1 - 2 que não seja uma de-
composição boa.
4. Transforme a decomposição do item anterior em uma decomposição boa, usando o Lema
4.3.
5. Discuta e, se posśıvel, determine a largura em árvore do grafo.
Exerćıcio 3. Os itens 1 e 2 são subsequentes aos itens 1 e 2 do Exerćıcio 2.
1. Defina e dê exemplos da operação de contração de arestas. Verifique que se G é K3-livre,
então a contração de arestas não produz arestas duplas.
2. Seja G um grafo K3-livre com tw(G) = k. Se G
′ é obtido de G pela contração de uma
aresta de G, então tw(G′) ≤ k.
3. Construa uma decomposição em árvore do grafo da Figura 1 - 3 que não seja uma de-
composição boa.
4. Transforme a decomposição do item anterior em uma decomposição boa, usando o Lema
4.3.
5. Discuta e, se posśıvel, determine a largura em árvore do grafo.
Exerćıcio 4 Os itens 1 e 2 são subsequentes aos itens 1 e 2 do Exerćıcio 3.
1. Prove que o ciclo Cn tem largura em árvore k = 2.
2. Seja G um grafo com n vértices. Mostre que tw(G) = n − 1 se e somente se G = Kn, o
grafo completo.
3. Conclua, usando os resultados dos itens 1 e 2 dos Exerćıcios 1, 2, 3 e 4 que um grafo G
tem largura em árvore 1 se e somente G é uma floresta.
4. Construa uma decomposição em árvore do grafo da Figura 1 - 4 que não seja uma de-
composição boa.
5. Transforme a decomposição do item anterior em uma decomposição boa, usando o Lema
4.3.
6. Discuta e, se posśıvel, determine a largura em árvore do grafo.