Lista07 MD Grafos

Idéia Principal
Diversas situações podem ser representadas através de grafos.

VII Lista de Exercícios – Matemática Discreta Grafos

Exercícios 5.1

1. Responda as seguintes perguntas sobre o grafo mostrado a seguir:
Gratos e Árvoresa. Este grafo é simples?
b. Este grafo é completo?

c . Este grafo é conexo?
d. Existem dois caminhos entre os vértices 3 e 6?
e. Este grafo possui algum ciclo?
f. O grafo possui algum vértice cuja remoção o tornaria uma árvore?
g. O grafo possui algum vértice cuja remoção o tornaria desconexo?
2. Esboce uma figura para cada um dos seguintes grafos:
a. um grafo simples com três vértices, cada qual com grau 2
b. quatro vértices, com ciclos de tamanho 1, 2, 3 e 4
c. uma árvore com cinco vértices e altura 1

Fig exercício 1

3. Responda as perguntas a seguir sobre a árvore abaixo com o vértice a como raiz.
a. Ela é uma árvore binária?
b. Ela é uma árvore binária completa?
c. Qual o pai do vértice e?
d. Qual é o filho à esquerda do vértice e?
Exercício 1
e. Qual a altura de g?
f. Qual é a altura da árvore?

Exercício 3

4. Use o grafo direcionado da figura a seguir para responder as perguntas abaixo
a. Quais vértices são alcançáveis a partir do vértice 3?
b. Qual é o comprimento do menor caminho entre 3 e 6?
c. Qual é o caminho do vértice 1 ao vértice 6 com comprimento 8?

Exercício 4
5. a. Desenhe K6. b. Desenhe K3,4.
6. Para cada uma das características a seguir, desenhe um grafo ou explique por que um grafo com as características pedidas não existe.
a. Quatro vértices de graus 1, 2, 3 e 4, respectivamente.
b. Simples com quatro vértices de graus 1, 2, 3 e 4, respectivamente.
c. Quatro vértices de graus 2, 3, 3 e 4, respectivamente.
d. Quatro vértices de graus 2, 3, 3 e 3, respectivamente.
7. Qual dos grafos na figura abaixo não é isomorfo aos outros? Por quê?
Seção 5.1 Terminologia e Aplicações de Grafos

(a)

(b)

Exercício 7

8. Qual dos grafos na figura abaixo não é