Exercicios 3 - Departamento de Matemática - PUC-Rio

MAT1310 – Matemática Discreta - 2012.1
PUC-Rio
Lista de Exercı́cios III
1. Desenhe um grafo com seis vértices, cada um com grau 3.
2. Desenhe cinco grafos diferentes que possuam quatro vértices e sejam conexos e simples.
3. Prove que se um grafo tem 100 vértices e mais de 4950 arestas então ele não é simples.
4. Prove que se um grafo simples tem 100 vértices e mais de 4851 arestas então ele é conexo.
5. Considere o grafo simples com 10 vértices no qual existe uma aresta conectando cada
par de vértices (geralmente denotado K10 ). Existem quantos caminhos de comprimento
5 que não repetem vértices?
6. Mostre que em qualque grafo, o número de vértices com grau impar é par.
7. Determine se existe ou não um grafo, sem laços, com 7 vértices, cujos graus são:
(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 são pares ordenados: A ⊂ V ×V .
Para cada vértice, definimos o grau de saı́da gr+ (v) de um vértice v ∈ V e o grau de
entrada gr− (v) por:
gr+ (v) = # {(vi , vo ) ∈ A, vi = v} ,
Demonstre por indução que:
X
v∈V
gr− (v) =
X
gr− (v) = # {(vi , vo ) ∈ A, vo = v} .
gr+ (v) = #A .
v∈V
9. Mostre que: se G é um grafo onde todo vértice tem grau 2 e G é conexo, então G é um
ciclo.
10. Verdadeiro ou falso? Justifique sua resposta!
(a) Seja G um grafo com pelo menos 2 vértices, e seja A a sua matriz de adjacência.1
Então G é conexo se e somente se existe um inteiro n ≥ 1 tal que todas as entradas
da matriz An são números diferentes de 0.
(b) Se um grafo tem 10 vértices e 50 arestas então ele não é simples (isto é, contém
algum laço ou alguma aresta múltipla).
11. Seja G um grafo orientado, e seja A a sua matriz de adjacência 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?
1
Uma matriz quadrada A de ordem n é dita matriz de adjacência de um grafo (não orientado) simples G
de n vértices se cada elemento aij de A é igual a 1 se existe uma aresta unindo o vértice i ao vértice j e é
igual a zero, caso contrário.
12. Suponha que A é a matriz de adjacência de

4
A3 = 3
5
um certo grafo. Sabendo que

3 5
4 5 ,
5 7
determine:
(a) a quantidade de caminhos de comprimento 3 saindo do vértice 1.
(b) a quantidade de caminhos de comprimento 6 saindo do vértice 2 e terminado no
vértice 3.
13. Seja G conexo com exatamente dois vértices de grau ı́mpar. Mostre que existe um
caminho ligando os dois vé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 vértices, sendo a deles
azuis e v vermelhos, tal que que existe uma aresta ligando dois vértices se e somente se
eles são de cores diferentes.
(a) Expresse o número de arestas de G em função 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 ı́mpar, para que condições sobre a e/ou v, G tem um caminho
euleriano?
(e) Determine em função de a e v o número de caminhos com 29 arestas que começam
em algum vértice azul (não especificado).
15. Sejam a, v inteiros positivos. Considere o grafo simples com a + v vértices, sendo a deles
azuis e v vermelhos, tal que que existe uma aresta ligando dois vértices se e somente
se eles são de cores diferentes. Para quais valores de a e v existe caminho Euleriano
(fechado ou não) neste grafo? (Dica: ver questão anterior).
16. Considere uma famı́lia de grafos Gi (Vi , Ei ). Vi é o conjunto dos vértices de Gi definidos
pelos pontos do R2 de coordenadas inteiras entre 0 e i. Ei é o conjunto das arestas de Gi
de tal modo que se u é uma aresta que une os vértices P e Q de Gi então as coordenadas
de P e Q diferem de uma unidade, em uma e somente uma coordenada, conforme os
exemplos abaixo.
(0,0)
G1
(0,0)
G2
(a) Quantos vértices e quantas arestas possui o grafo G5 ?
(b) Generalize, em função de i o número de vértices e arestas do grafo Gi .
(c) Para que valor(es) de i, Gi é um grafo euleriano? Justifique.
(d) Quando Gi não é euleriano, quantas arestas, em função de i devo acrescentar para
torná-lo euleriano?