Lista de grafos

Lista de Exercícios – Grafos – Conceitos básicos
1. Responda as seguintes perguntas sobre o grafo mostrado a seguir:

a)
b)
c)
d)
e)
f)
g)
h)
i)
j)
k)
l)
m)
n)
o)
p)

Qual a ordem do grafo?
Qual o grau dos vértices?
Qual é o grau do grafo?
Com base na resposta dada à letra “b”, indique quantas arestas esse grafo possui.
Qual o grau mínimo e o grau máximo do grafo?
Qual é o grau médio do grafo?
Quantos laços o grafo possui?
Este grafo é regular? Justifique.
Dê um exemplo de cadeia que incluía os vértices 1 e 4. Qual o comprimento desta cadeia?
A cadeia 7-6-5-3-4 é simples? Por que?
Dê exemplo de um ciclo no grafo.
O grafo possui algum arco cuja remoção o tornaria um grafo acíclico?Qual?
Este grafo é conexo?
O grafo possui algum arco cuja remoção o tornaria desconexo?
Indique um vértice de corte no grafo.
Indique uma ponte no grafo.

2. Responda as seguintes perguntas sobre o grafo mostrado a seguir:

a)
b)
c)
d)
e)
f)

Qual o grau de entrada e de saída dos vértices?
Com base na resposta dada à letra “a”, indique quantas arestas esse grafo possui.
Existe algum vértice fonte? Em caso afirmativo, qual?
Existe algum vértice sumidouro? Em caso afirmativo, qual?
Exemplifique um caminho no grafo.
Acrescente uma aresta ao grafo que permita que o mesmo tenha um circuito.

3. Responda as seguintes perguntas sobre o grafo mostrado a seguir:

a) Este grafo é regular? Justifique.
b) Este grafo é completo? Justifique.
4. Sabendo que o grafo seguinte é completo. Indique quantas arestas ele possui.

5. O grafo seguinte é bipartido? Justifique.

6. O grafo seguinte é bipartido completo? Por que?

7. O grafo seguinte é um multigrafo? Por que? Exemplifique uma situação real que possa ser modelada por um multigrafo.

8. Desenhe o grafo complementar e também dê um exemplo de subgrafo do grafo seguinte. O subgrafo desenhado por você é abrangente? Por que?

9. Qual dos subgrafos seguintes (b) ou (c) pode ser