Teoria de Grafos - Lista de Exercícios

Prévia do material em texto

MO405/MC878 - Teoria e Aplicac¸o˜es de Grafos
Lista de Exerc´ıcios 4
Os exerc´ıcios sem marcas sa˜o (ou deveriam ser) relativamente simples. Os exerc´ıcios marcados com
(*) exigem alguma reflexa˜o. . . . Os exerc´ıcios marcados com (**) sa˜o mais dif´ıceis.
Observac¸a˜o. A na˜o ser que seja dito o contra´rio ou o´bvio no contexto, nesta lista n e m denotam
respectivamente o nu´mero de ve´rtices e arestas de um grafo denotado por G.
1. Prove ou mostre um contra-exemplo.
(a) Todo grafo conexo possui pelo menos m− n+ 1 circuitos distintos.
(b) Uma floresta G possui n− c(G) arestas.
(c) Um grafo G com m = n e´ um circuito.
(d) Um grafo G com m = n conte´m exatamente um circuito.
(e) Uma floresta e´ um grafo bipartido.
(f) Um grafo G e´ uma a´rvore se e somente se m = n− 1.
(g) Um grafo G e´ uma a´rvore se e somente se na˜o possui circuitos.
(h) Um grafo G e´ uma floresta se e somente se m = n− c(G).
(i) Um grafo G e´ uma floresta se e somente se na˜o possui circuitos.
(j) Um grafo G com m < n possui um componente que e´ uma a´rvore.
(k) Todo grafo possui uma a´rvore geradora.
(l) Todo grafo possui uma floresta geradora.
(m) Se F e´ um subgrafo ac´ıclico de um grafo conexo G, enta˜o existe uma a´rvore geradora em
G que conte´m as arestas de F .
2. Prove que se T e´ uma a´rvore com ∆(T ) ≥ 2 enta˜o T possui pelo menos ∆(T ) folhas. Mostre
que isto e´ o melhor poss´ıvel exibindo um grafo com n ve´rtices e ∆ folhas para cada poss´ıvel
n,∆ com n > ∆ ≥ 2.
3. Prove que:
(a) G e´ uma floresta se e somente se todo subgrafo induzido possui ve´rtice de grau menor ou
igual a 1;
(b) G e´ uma floresta se e somente se todo subgrafo conexo e´ um subgrafo induzido.
Por que na˜o posso dizer a´rvore em vez de floresta nas afirmac¸o˜es acima?
4. Seja T uma a´rvore na˜o-trivial. Seja q o nu´mero de ve´rtices de grau pelo menos 3 de T e seja
n1 o nu´mero de folhas de T . Mostre que q ≤ n1 − 2.
5. Seja T uma a´rvore tal que cada ve´rtice possui grau 1 ou k. Quais sa˜o os poss´ıveis valores de
|V (T )|?
6. Prove que toda a´rvore na˜o-trivial T possui pelo menos dois conjuntos independentes maximais
distintos. Mostre que a u´nica a´rvore com exatamente dois conjuntos independentes maximais
e´ uma estrela (a´rvore isomorfa a K1,t para algum t ≥ 1)..
1
7. Usando induc¸a˜o no nu´mero de ve´rtices, mostre diretamente que uma a´rvore e´ um grafo bipartido.
Usando isto, mostre que um grafo sem circuitos ı´mpares e´ bipartido. Sugesta˜o: considere uma
a´rvore geradora de G.
8. Toda a´rvore e´ um grafo bipartido! Mostre que toda a´rvore possui uma folha na maior das
classes da bipartic¸a˜o (em ambas se elas teˆm o mesmo tamanho).
9. Um ve´rtice v e´ dito paiza˜o1 se na˜o e´ uma folha e e´ adjacente a pelo menos g(v) − 1 folhas. E´
verdade que toda a´rvore com n ≥ 3 possui um ve´rtice paiza˜o?
10. Suponha que T seja uma a´rvore na qual todo ve´rtice adjacente a uma folha tem grau pelo
menos 3. Prove que T possui duas folhas adjacentes a um mesmo ve´rtice.
11. Seja T uma a´rvore. Prove que todos os ve´rtices de T teˆm grau ı´mpar se e somente se para
aresta e ∈ E(T ), as duas componentes de T − e possuem um nu´mero ı´mpar de ve´rtices.
12. Sejam g1, . . . , gn inteiros positivos com n ≥ 2. Prove que existe uma a´rvore com ve´rtices de
graus g1, . . . , gn se e somente se
∑n
i=1 gi = 2n− 2.
13. (*) Seja G um grafo com n ≥ 3 tal que G− v e´ uma a´rvore para todo v ∈ V (G). Determine m
em func¸a˜o de n e use isto para determinar G.
14. (**) Prove que se T e´ uma a´rvore com k + 1 ve´rtices e G e´ um grafo simples com δ(G) ≥ k,
enta˜o G conte´m uma co´pia de T (isto e´, um subgrafo isomorfo a T ). Sugesta˜o: use induc¸a˜o
em k.
15. Usando o exerc´ıcio anterior, mostre que todo grafo simples com grau me´dio pelo menos 2(k−1),
onde k − 1 > 0 e´ inteiro, possui uma co´pia de qualquer a´rvore com k + 1 ve´rtices.
16. (**) Prove a propriedade de Helly para a´rvores: sejam T1, . . . , Tk suba´rvores de uma a´rvore T
tais que quaisquer duas dessas a´rvores possuem um ve´rtice em comum. Prove que existe um
ve´rtice comum a todas essas suba´rvores.
Me´todo 1: use induc¸a˜o em k; vai ser preciso fazer duas induc¸o˜es.
Me´todo 2: use induc¸a˜o em |V (T )|; tome uma folha de T e verifique se para alguma das
suba´rvores vale que V (Ti) = {v}. Se isto na˜o valer, modifique T e as suba´rvores Ti convenien-
temente.
Mostre que a afirmac¸a˜o acima na˜o e´ verdade se T na˜o for uma a´rvore.
17. (*) Seja T uma a´rvore e seja s ∈ V (T ). Seja P um caminho mais longo em T que comec¸a em s.
Digamos que P termina em u. Seja Q um caminho mais longo em T que comec¸a em u. Prove
que Q e´ um caminho mais longo em T .
18. Suponha que T e T ′ sejam a´rvores geradoras de um grafo G. Para cada aresta e ∈ E(T )−E(T ′),
prove que existe uma aresta e′ ∈ E(T ′) − E(T ) tal que T ′ + e − e′ e T − e + e′ sa˜o a´rvores
geradoras de G.
19. Seja G um grafo conexo contendo um u´nico circuito, digamos C. Determine o nu´mero de a´rvores
geradoras de G.
1Pura falta de imaginac¸a˜o.
2
20. Seja G um grafo conexo contendo exatamente dois circuitos C e C ′. Determine o nu´mero de
a´rvores geradoras de G. Sugesta˜o: esses circuitos podem ter arestas em comum?
21. Determine o nu´mero de a´rvores geradoras τ(G) de um grafo G em func¸a˜o dos nu´meros de
a´rvores geradoras dos blocos de G.
22. (* ou **) Determine o nu´mero de a´rvores geradoras de K2,n para n ≥ 2. Sugesta˜o: chame de
x e y os ve´rtices da menor parte. Note que em qualquer a´rvore geradora exatamente um dos
ve´rtices da outra parte tem que ser vizinho de x e de y enquanto cada um dos outros ve´rtices
e´ vizinho de x ou de y (mas na˜o de ambos). Conte o nu´mero de possibilidades.
23. (** ou ***) Seja e uma aresta qualquer de Kn onde n ≥ 3. Prove que o nu´mero de a´rvores
geradoras de Kn − e e´ (n− 2)n
n−3. Sugesta˜o: note que por simetria, e´ irrelevante qual aresta
de Kn e´ removida. Conte o nu´mero de pares (f, T ) onde T e´ uma a´rvore geradora de Kn e
f ∈ E(T ). Divida este resultado por ?? para obter o nu´mero de a´rvores geradoras de Kn que
conte´m uma aresta fixa e. O resto deveria ser fa´cil.
24. Seja G um grafo na˜o-separa´vel e seja e ∈ E(G). Mostre que o grafo obtido a partir de G
subdividindo e e´ na˜o-separa´vel.
25. Seja G um grafo e e ∈ E(G). Mostre que
(a) se G− e e´ na˜o-separa´vel e e na˜o e´ um lac¸o, enta˜o G e´ na˜o-separa´vel,
(b) se G/e (G contrai e) e´ na˜o-separa´vel e e na˜o e´ nem um lac¸o nem aresta-de-corte, enta˜o G e´
na˜o-separa´vel.
26. Mostre que todo grafo separa´vel possui pelo menos dois blocos-folhas.
27. Seja G um grafo na˜o-separa´vel e seja e ∈ E(G) tal que G− e e´ separa´vel. Mostre que a a´rvore
de blocos de G e´ um caminho.
28. Mostre que um grafo e´ par se e somente se cada um de seus blocos e´ par.
29. Mostre que um grafo e´ bipartido se e somente se cada um de seus blocos e´ bipartido.
30. Mostre que se um grafo G na˜o conte´m circuitos pares, enta˜o cada bloco de G ou e´ um circuito
ı´mpar ou uma co´pia de K1 ou K2.
31. (*) Seja G um grafo simples na˜o-separa´vel e na˜o-bipartido. Sejam x e y ve´rtices distintos em
G. Mostre que existem um caminho par e um caminho ı´mpar de x a y (os caminhos na˜o
tem relac¸a˜o entre si, o importante e´ que tenham a paridade desejada). Sugesta˜o: escolha
convenientemente subconjuntos A,B de V (G) e use um resultado visto em aula. O resultado
vale se o grafo for separa´vel?
32. (* ou **) Nesta questa˜o voceˆ deve provar a versa˜o para arestas-de-corte de um teorema visto
em aula. Seja G um grafo sem arestas-de-corte e sejam x, y ∈ V (G). Mostre que existem dois
caminhos disjuntos nas arestas de x a y em G.
3