Lista 1 de Teoria de Grafos

Prévia do material em texto

Lista 1 de Teoria de Grafos
Profa Cla´udia Linhares Sales
Atenc¸a˜o ! Algumas questo˜es conte´m novas definic¸o˜es que se unira˜o ao elenco
das definic¸o˜es apresentadas em sala de aula, como se assim o tivessem sido.
1. Mostre que se um grafo e´ simples, enta˜o m ≤ (n2).
2. Mostre que se G e´ isomorfo a H, enta˜o |V (G)| = |V (H)| e |E(G)| =
|E(H)|.
3. Mostre que o K4 possui onze subgrafos simples na˜o isomorfos.
4. Seja G um grafo simples. Mostre que m =
(
n
2
)
se e somente se G e´
completo.
5. Como sa˜o os grafos K¯n e K¯r,s ?
6. Mostre que:
(a) |E(Kr,s)| = rs;
(b) Se G e´ simples e bipartite, enta˜o m ≤ n2/2.
7. Seja I a matriz de incideˆncia e A a matriz de adjaceˆncias de um grafo G.
(a) Prove que a soma de toda coluna de I e´ exatamente 2;
(b) O que significa a soma das colunas de M ?
8. Mostre que:
(a) Todo subgrafo induzido de um grafo completo e´ completo;
(b) Todo subgrafo de um grafo bipartite e´ bipartite.
9. O k-cubo e´ o grafo cujos ve´rtices sa˜o k-tuplas ordenadas de 0’s e 1’s, onde
dois ve´rtices sa˜o adjacentes se eles diferem em exatamente uma coorde-
nada. Mostre que o k-cubo tem 2k ve´rtices e k2k−1 arestas (dica: tente
usar induc¸a˜o).
10. Encontre um grafo bipartite que na˜o e´ isomorfo a um subgrafo de qualquer
k-cubo.
11. Mostre que δ ≤ 2mn ≤ ∆.
12. Um grafo k-regular e´ um grafo cujo grau de qualquer ve´rtice e´ igual a k.
Mostre que um grafo bipartite k-regular (k > 0) com partic¸o˜es (X,Y ),
possui |X| = |Y |.
1
13. Mostre que em qualquer grupo de duas ou mais pessoas, existe sempre
duas com exatamente o mesmo nu´mero de amigos no grupo.
14. Se G tem ve´rtices v1, v2, . . . , vn, a sequ¨eˆncia (d(v1), d(v2), . . . , d(vn)) e´
chamada a sequ¨eˆncia de graus de G.
Mostre que uma sequ¨eˆncia de inteiros na˜o negativos (d1, d2, . . . , dn) e´ uma
sequ¨eˆncia de graus de algum grafo se e somente se
∑n
i=1 di e´ par.
15. Uma sequ¨eˆncia de graus d = (d1, . . . , dn) e´ grafica se existe um grafo sim-
ples cuja a sequ¨eˆncia de graus e´ d.
Mostre que as sequ¨eˆncias (7, 6, 5, 4, 3, 3, 2) e (6, 6, 5, 4, 3, 3, 1) na˜o sa˜o gra´ficas.
16. O grafo-linha G′ de um grafo G e´ o grafo cujo conjunto de ve´rtices e´ E(G)
e cujo conjunto de arestas e´ definido da seguinte forma: dois ve´rtices sa˜o
adjacentes em G′ se e somente se as arestas correspondentes de G forem
adjacentes.
Mostre que se G e´ simples, enta˜o o grafo-linha de G, G′, tem E(G) ve´rtices
e
∑
v∈V (G)
(
d(v)
2
)
arestas.
17. Mostre que se existe um passeio (u, v) em G, enta˜o existe tambe´m um
caminho (u, v) em G.
18. Mostre que se G e´ simples e δ ≥ k, enta˜o G possui um caminho de com-
primento k.
19. Mostre que G e´ conexo se e somente se, para toda partic¸a˜o de V (G) em
dois conjuntos na˜o vazios V1 e V2, existe uma aresta com uma extremidade
em V1 e a outra extremidade em V2.
20. (a) Mostre que se G e´ simples e m >
(
v−1
2
)
enta˜o G e´ conexo.
(b) Para n > 1, encontre um grafo simples e desconexo com m =
(
v−1
2
)
.
21. Mostre que se G e´ conexo, enta˜o G¯ e´ desconexo.
22. (a) Prove que se G e´ simples e δ > [v2 ]− 1, enta˜o G e´ conexo.
(b) Para n > 1 e n par, encontre um grafo simples desconexo k-regular,
onde k = [n2 ]− 1.
23. Mostre que quaisquer dois maiores caminhos em um grafo conexo teˆm um
ve´rtices em comum.
24. Mostre que se um grafoG tem diaˆmetro maior que 3, enta˜o G¯ tem diaˆmetro
menor que 3.
25. Mostre que se G e´ um grafo simples, conexo e na˜o completo, enta˜o G
possui treˆs ve´rtices x, y e z tais que xy ∈ E(G), yz ∈ E(G) e xz /∈ E(G).
26. Mostre que δ ≥ 2, enta˜o G conte´m um ciclo.
2
27. (a) Mostre que se e ∈ E(G), enta˜o C(G) ≤ C(G− e) ≤ C(G) + 1.
(b) Seja v ∈ V (G). Mostre que G− e na˜o pode, em geral, ser substitu´ıdo
por G− v na desigualdade de (a).
28. Mostre que se m ≥ n, enta˜o G conte´m um ciclo.
29. Mostre que se quaisquer dois ve´rtices de um grafo G sem lac¸os sa˜o conec-
tados por um u´nico caminho, enta˜o G e´ uma a´rvore.
30. Mostre que toda a´rvore com exatamente dois ve´rtices de grau um e´ um
caminho.
31. Seja G um grafo com n − 1 arestas. Mostre que as treˆs sentenc¸as abaixo
sa˜o equivalentes:
(a) G e´ conexo.
(b) G e´ ac´ıclico.
(c) G e´ uma a´rvore.
(Sugesta˜o: prove que (a) ⇒ (b), que (b) ⇒ (c) e que finalmente (c) ⇒
(a).)
32. Mostre que se G e´ uma a´rvore com ∆ ≥ k, enta˜o G tem pelo menos k
folhas.
33. Um grafo ac´ıclico e´ tambe´m chamado de floresta. Mostre que
(a) qualquer componente de uma floresta e´ uma a´rvore;
(b) G e´ uma floresta se e somente se m = n−C(G), onde C(G) e´ o nu´mero
de componentes de G.
34. Mostre que G e´ uma floresta se e somente se toda aresta de G e´ uma
ponte.
35. Mostre que se G e´ simples e k-regular, enta˜o κ = κ′.
36. Mostre que se G e´ simples e δ ≥ n− 2, enta˜o κ = δ.
37. Mostre que se G e´ k-conexo em arestas, enta˜o m ≥ k n2 .
38. Mostre um grafo simples com δ = n− 3 e κ < δ.
39. Mostre que G e´ 2-conexo em arestas se e somente se existem dois caminhos
disjuntos em arestas entre qualquer par de ve´rtices de G.
40. Mostre que se um grafo na˜o tem ciclos pares, enta˜o cada um de seus blocos
ou e´ um K1, ou K2 ou um ciclo ı´mpar.
41. Mostre que um grafo conexo que na˜o e´ um bloco tem pelo menos dois
blocos com exatamente uma articulac¸a˜o cada.
3
42. Descreva um bom algoritmo para achar blocos de um grafo.
43. Se poss´ıvel desenhe um grafo euleriano G com um nu´mero par de ve´rtices
e um nu´mero ı´mpar de arestas. Se na˜o for poss’ıvel, explique porque tal
grafo na˜o existe.
44. Mostre que se G e´ euleriano, cada bloco de G e´ euleriano.
45. Mostre que se G na˜o tem ve´rtices grau ı´mpar, enta˜o existem ciclos disjun-
tos em arestas C1, C2, . . . , Ck tais que E(G) = E(C1)∪E(C2) . . .∪E(Ck).
46. Mostre que se
(a) ou G na˜o e´ 2-conexo;
(b) ou G e´ bipartite com partic¸o˜es (X, Y) onde |X| > |Y |,
enta˜o G na˜o e´ hamiltoniano.
47. Mostre que se G possui um caminho hamiltoniano enta˜o para todo sub-
grafo S pro´prio de V , C(G) ≤ |S|+ 1.
48. Fac¸a um bom algoritmo para
(a) encontrar o feˆcho de um grafo;
(b) encontrar um ciclo hamiltoniano quando o feˆcho for completo.
4