Grafos e Recorrência

Prévia do material em texto

2017.2 CB 0661 - MATEMÁTICA DISCRETA (PROF. FABRICIO)
LISTA 3 (19/11/2017)
Cada
√
denota um nível de dificuldade:
√
fácil,
√√
médio e
√√√
difícil.
1.(
√
) (OBM) Três polígonos regulares, de 8, 12 e 18 lados respectivamente, estão inscritos em uma mesma cir-
cunferência e têm um vértices em comum. Os vértices dos três polígonos são marcados na circunferência.
Quantos vértices distintos foram marcados?
2.(
√√
) (OBM, adaptado) Um quadrado de lado 3 é dividido em 9 quadrados de lado 1, formando um quadric-
ulado. Cada quadrado unitário é pintado de azul ou vermelho. De quantas maneiras é possível pintar o
quadriculado? Dentre essas maneiras, em quantas delas existe um quadrado 2 por 2 pintado inteiramente
de uma mesma cor?
3.(
√√
) Uma permutação caótica de {1, . . . , n} é uma função f : {1, . . . , n} → {1, . . . , n} que é bijetora e satisfaz
f(i) 6= i para todo i. Use o princípio da inclusão e exclusão para calcular o número de permutações caóticas
de {1, . . . , n}. (Dica: defina conjuntos de permutações ruins Ai onde, para cada i, tal conjunto é formado
pelas permutações onde f(i) = i).
4.(
√
) Resolva as seguintes relações de recorrência.
(a) a0 = 4;
an =
2
3an−1.
(b) a0 = 0;
an = 1,2an−1 + 1.
(c) T (1) = 13;
T (n) = 5T (n/2) + 3n.
(d) T (1) = 29;
T (n) = 3T (n/3) + 17n.
(e) a0 = 5; a1 = 1;
an = 2an−1 − an−2.
(f) a0 = 5; a1 = 1;
an = −2an−1 − an−2.
(g) a0 = 1;
an = nan−1 + 2n.
5.(
√√
) Tente usar a mesma idéia vista em sala para encontrar o termo geral de uma relação de recorrência ho-
mogênea de segunda ordem para encontrar o termo geral da seguinte relação de recorrência também
homogênea. (Dica: as raizes do polinômio obtido são 1, 2 e 3)
a0 = 1; a1 = 2; a2 = 3;
an = 6an−1 − 11an−2 + 6an−3
6.(
√
) Considere o problema de colorir as regiões de um mapa de forma que regiões fronteiriças não possuam a
mesma cor. Desenhe um mapa que exija ao menos três cores para ser colorido, mas que não possua três
regiões A, B e C tais que A faz fronteira com B e com C e B também faz fronteira com C (seu mapa pode
ter uma região “vazada”, isto é, uma espécie de lago ou mar no meio que não precisa ser colorido).
7.(
√√
) Qual a quantidade máxima de arestas que um grafo com n vértices pode possuir? E se o grafo puder ter
arestas múltiplas? Quantos grafos distintos cujo conjunto de vértices é {v1, · · · , vn} existem?
8.(
√
) Prove que em todo grafo com dois ou mais vértices, deve haver dois vértices com mesmo grau.
1
9.(
√√
) Seja G um grafo. O complemento de G, denotado por G é o grafo cujo conjunto vértices é o mesmo de G e
cujo conjunto de arestas é o complemento do conjunto de arestas de v (isto é, {u, v} ∈ E(G) se e somente
se {u, v} /∈ E(G)). Prove que se G é desconexo, então G é conexo.
10.(
√√
) Seja G um grafo onde todo vértice tem grau dois. Prove que toda componente de G é um ciclo.
11.(
√
) Prove ou desprove: T é uma árvore se e somente todo vértice de T que não é uma folha é um vértice de
corte.
12.(
√√
) Seja G um grafo euleriano. Prove que as arestas de G podem ser particionadas em subconjuntos que
definem ciclos disjuntos de G.
13.(
√
) Seja G um grafo que possui 2k vértices de grau ímpar, k ≥ 2. Diga como obter um grafo euleriano a
partir de G: 1) acrescentando arestas; 2) acrescentando um vértice e arestas incidentes somente a este novo
vértice. Quantas arestas possui o grafo obtido?
2