faculdade

UNIVERSIDADE DE ITAÚNA
Disciplinas
Curso
Teoria dos Grafos
Ciência da Computação
Professor
Marco Túlio ([e-mail])

Turno
Noite

Período
4◦

Lista de Exercícios I
Material de estudo para a primeira prova
Discussão em sala de aula: 9 de setembro de 2013
1. Considere o grafo simples não direcionado a seguir e responda às seguintes perguntas:

Figura 1: Grafo simples
(a) Qual o conjunto de vértices do grafo?
(b) Qual o conjunto de arestas do grafo?
(c) Existem laços? Se sim, quais são?
(d) Existem arestas múltiplas? Se sim, quais são?
(e) Existem vértices isolados? Se sim, quais são?
(f) Existem ciclos? Se sim, quais são?
(g) O grafo é completo?
(h) O grafo é regular?
(i) O grafo é conexo/conectado?
(j) Quantos componentes conexos existem no grafo?
(k) Qual o grau de cada vértice?
(l) Quais os vizinhos (vértices adjacentes) de cada vértice?
(m) O vértice u é alcançável a partir do vértice z?
(n) O vértice t é alcançável a partir do vértice v?
2. Represente o grafo da Figura 1 com as estruturas de dados a seguir:
(a) Matriz de adjacências.
(b) Lista de adjacências.
3. Qual a complexidade de tempo para se executar cada uma das operações abaixo nas duas estruturas de dados do exercício 2?
(a) Determinar se existe uma aresta entre dois vértices específicos i e j.
(b) Determinar todos os vértices adjacentes a um vértice i.
(c) Determinar o grau de um vértice i.

(d) Determinar o grau total de um grafo.
4. Qual o número máximo de arestas que pode ter um grafo simples com n vértices? Justifique sua resposta. 5. Qual o número de grafos simples distintos que podem existir sobre um conjunto de vértices de tamanho n? 6. Prove que em qualquer grafo simples o grau total é igual a duas vezes o número de arestas.
7. Os grafos abaixo são isomorfos? Analise cada par deles. Demonstre que são isomorfos, se o forem; caso contrário, justifique por que não o são.

Figura 2: Isomorfismo em grafos
8. Prove que se dois grafos