MAT1310_Lista3
2 pág.

MAT1310_Lista3


DisciplinaMatemática Discreta3.516 materiais76.280 seguidores
Pré-visualização1 página
MAT1310 \u2013 Matema´tica Discreta - 2012.1 PUC-Rio
Lista de Exerc´\u131cios III
1. Desenhe um grafo com seis ve´rtices, cada um com grau 3.
2. Desenhe cinco grafos diferentes que possuam quatro ve´rtices e sejam conexos e simples.
3. Prove que se um grafo tem 100 ve´rtices e mais de 4950 arestas enta\u2dco ele na\u2dco e´ simples.
4. Prove que se um grafo simples tem 100 ve´rtices e mais de 4851 arestas enta\u2dco ele e´ conexo.
5. Considere o grafo simples com 10 ve´rtices no qual existe uma aresta conectando cada
par de ve´rtices (geralmente denotado K10). Existem quantos caminhos de comprimento
5 que na\u2dco repetem ve´rtices?
6. Mostre que em qualque grafo, o nu´mero de ve´rtices com grau impar e´ par.
7. Determine se existe ou na\u2dco um grafo, sem lac¸os, com 7 ve´rtices, cujos graus sa\u2dco:
(a) 0, 2, 2, 2, 4, 4, 6.
(b) 2, 2, 3, 3, 4, 4, 5.
8. Seja um grafo G = (V,A) orientado, ou seja, as arestas sa\u2dco pares ordenados: A \u2282 V ×V .
Para cada ve´rtice, definimos o grau de sa´\u131da gr+(v) de um ve´rtice v \u2208 V e o grau de
entrada gr\u2212(v) por:
gr+(v) = # {(vi, vo) \u2208 A, vi = v} , gr\u2212(v) = # {(vi, vo) \u2208 A, vo = v} .
Demonstre por induc¸a\u2dco que:\u2211
v\u2208V
gr\u2212(v) =
\u2211
v\u2208V
gr+(v) = #A .
9. Mostre que: se G e´ um grafo onde todo ve´rtice tem grau 2 e G e´ conexo, enta\u2dco G e´ um
ciclo.
10. Verdadeiro ou falso? Justifique sua resposta!
(a) Seja G um grafo com pelo menos 2 ve´rtices, e seja A a sua matriz de adjace\u2c6ncia.1
Enta\u2dco G e´ conexo se e somente se existe um inteiro n \u2265 1 tal que todas as entradas
da matriz An sa\u2dco nu´meros diferentes de 0.
(b) Se um grafo tem 10 ve´rtices e 50 arestas enta\u2dco ele na\u2dco e´ simples (isto e´, conte´m
algum lac¸o ou alguma aresta mu´ltipla).
11. Seja G um grafo orientado, e seja A a sua matriz de adjace\u2c6ncia orientada.
(a) O que podemos afirmar sobre G se A tem uma linha formada apenas por zeros?
(b) O que podemos afirmar sobre G se A tem uma coluna formada apenas por zeros?
1Uma matriz quadrada A de ordem n e´ dita matriz de adjace\u2c6ncia de um grafo (na\u2dco orientado) simples G
de n ve´rtices se cada elemento aij de A e´ igual a 1 se existe uma aresta unindo o ve´rtice i ao ve´rtice j e e´
igual a zero, caso contra´rio.
12. Suponha que A e´ a matriz de adjace\u2c6ncia de um certo grafo. Sabendo que
A3 =
\uf8eb\uf8ed4 3 53 4 5
5 5 7
\uf8f6\uf8f8 ,
determine:
(a) a quantidade de caminhos de comprimento 3 saindo do ve´rtice 1.
(b) a quantidade de caminhos de comprimento 6 saindo do ve´rtice 2 e terminado no
ve´rtice 3.
13. Seja G conexo com exatamente dois ve´rtices de grau \u131´mpar. Mostre que existe um
caminho ligando os dois ve´rtices que passa exatamente uma vez por cada aresta de G.
Dica: Crie uma nova aresta ligando V e W .
14. Sejam a, v inteiros positivos. Seja G o grafo simples com a + v ve´rtices, sendo a deles
azuis e v vermelhos, tal que que existe uma aresta ligando dois ve´rtices se e somente se
eles sa\u2dco de cores diferentes.
(a) Expresse o nu´mero de arestas de G em func¸a\u2dco de a e v.
(b) Supondo a e v pares, G possui circuito euleriano? Justifique.
(c) Supondo a e v impares, G possui circuito euleriano? Justifique.
(d) Supondo a par e v \u131´mpar, para que condic¸o\u2dces sobre a e/ou v, G tem um caminho
euleriano?
(e) Determine em func¸a\u2dco de a e v o nu´mero de caminhos com 29 arestas que comec¸am
em algum ve´rtice azul (na\u2dco especificado).
15. Sejam a, v inteiros positivos. Considere o grafo simples com a+v ve´rtices, sendo a deles
azuis e v vermelhos, tal que que existe uma aresta ligando dois ve´rtices se e somente
se eles sa\u2dco de cores diferentes. Para quais valores de a e v existe caminho Euleriano
(fechado ou na\u2dco) neste grafo? (Dica: ver questa\u2dco anterior).
16. Considere uma fam\u131´lia de grafos Gi(Vi, Ei). Vi e´ o conjunto dos ve´rtices de Gi definidos
pelos pontos do R2 de coordenadas inteiras entre 0 e i. Ei e´ o conjunto das arestas de Gi
de tal modo que se u e´ uma aresta que une os ve´rtices P e Q de Gi enta\u2dco as coordenadas
de P e Q diferem de uma unidade, em uma e somente uma coordenada, conforme os
exemplos abaixo.
(0,0)
(0,0)
G
G
1
2
(a) Quantos ve´rtices e quantas arestas possui o grafo G5 ?
(b) Generalize, em func¸a\u2dco de i o nu´mero de ve´rtices e arestas do grafo Gi.
(c) Para que valor(es) de i, Gi e´ um grafo euleriano? Justifique.
(d) Quando Gi na\u2dco e´ euleriano, quantas arestas, em func¸a\u2dco de i devo acrescentar para
torna´-lo euleriano?