Lista exercicio - Matemática discreta

Prévia do material em texto

Lista 2 de Matema´tica Discreta II
Bacharelado em Cieˆncia da Computac¸a˜o
Rodrigo de Souza
11 de Julho de 2012
Exerc´ıcio 1 Quantos grafos diferentes existem com n ve´rtices e m arestas ? Justifique.
Resposta. A resposta e´ o nu´mero de conjuntos de tamanho m tirados do conjunto de arestas, que
tem tamanho n(n− 1)/2, ou seja,
(
n(n−1)/2
m
)
.
Exerc´ıcio 2 Seja G um grafo com δ(G) ≥ 3. Mostre que G tem um circuito de comprimento par.
Resposta. Seja c = v1 . . . vk um caminho de comprimento ma´ximo em G. Enta˜o, todos os vizinhos
de vk tem de estar em c. O grau de vk e´ no mı´nimo 3, enta˜o vk tem pelo menos dois vizinhos ale´m de
vk−1. Sejam vi e vj vizinhos de vk, i < j < k − 1. Se o segmento f = vi . . . vj de c tem comprimento
par, enta˜o vi . . . vjvkvi e´ um circuito de comprimento par. Se o segmento g = vj . . . vk de c tem com-
primento ı´mpar, enta˜o vj . . . vkvj e´ um circuito de comprimento par. Se f tem comprimento ı´mpar e
g tem comprimento par, enta˜o fg tem comprimento ı´mpar, e vi . . . vkvi e´ um circuito de comprimento
par.
Exerc´ıcio 3 O grafo do bispo t-por-t e´ definido como segue : os ve´rtices sa˜o as casas de um tabuleiro
de xadrez de dimensa˜o t linhas por t colunas (ou seja, ha´ t2 ve´rtices) ; dois ve´rtices u e v sa˜o vizinhos
se ha´ um movimento do bispo de u para v, ou seja, se u e v esta˜o na mesma diagonal. Quantos
componentes tem o grafo do bispo t-por-t ? Justifique.
Resposta. Dois componentes : um corresponde a`s casas pretas e outro a`s casas vermelhas. Um bispo
partindo de uma casa preta pode atingir todas as outras com seus movimentos na diagonal ; mas na˜o
pode atingir nenhuma branca. Idem para um bispo numa casa branca.
Exerc´ıcio 4 Seja G um grafo tal que δ(G) ≥ ⌊n(G)/2⌋. Mostre que G e´ conexo.
Resposta. Suponha que G na˜o seja conexo. Enta˜o G tem pelo menos dois componentes ; seja X o
menor deles. Enta˜o, X tem no ma´ximo ⌊n(G)/2⌋ ve´rtices. Ou seja, um ve´rtice qualquer em x tem
no ma´ximo ⌊n(G)/2⌋ − 1 vizinhos (pois so´ e´ vizinho de ve´rtices em X). Contradic¸a˜o com a hipo´tese
sobre o grau mı´nimo em G.
Exerc´ıcio 5 Uma a´rvore e´ um grafo sem circuitos e conexo. Prove que um grafo conexo G e´ uma
a´rvore se, e somente se, para cada aresta a, o grafo obtido removendo-se a de G na˜o e´ conexo.
1