Exercicios Grafos

Universidade Estadual do Sudoeste da Bahia – UESB
Departamento de Ciências Exatas – DCE
Colegiado do Curso de Computação
Disciplina: Teoria dos Grafos
Prof. Alzira Ferreira
Data:_____/_____/______
Nº Matrícula:
Aluno(a):
I Unidade
Lista de Exercícios

1 Conteúdos abordados a) Grafos Definições; grafo completo, grafo K-partido, grafo conexo e desconexos, componentes conexas b) Operações com Grafos c) Caminho em Grafos d) Fecho Transitivo e) Caminho Mínimo: Algoritmos de Dijkstra 1. Defina e dê exemplos a) grafo completo b) grafo conexo c) componentes conexas. 2. Mostre que, em um grafo orientado, se tem . 3. Emissoras de televisão vão ser instaladas em estações baseadas em nove cidades de nosso estado (cidades A, B, ..., I). As regulamentações do setor de telecomunicações indicam que uma mesma emissora não pode ser instalada em duas cidades com distância inferior a 150 Km. Considere a tabela abaixo que indica as distâncias as distâncias entre as cidades. Faça a representação em forma de grafo.

4. Um cubo de dimensão k, ou k-cubo, é o grafo definido da seguinte maneira: os vértices do grafo são todas as sequências b1b2...bk em que cada bk pertence a {0,1}. Dois vértices são adjacentes se diferem em exatamente uma posição. Faça figuras dos cubos de dimensões 1, 2 e 3. Uma sequencia de bits é denominado palavra, é a quantidade de bits necessárias para representar um informação. 5. O grafo dos estados do Brasil é definido assim: cada vértice é um dos estados da República Federativa do Brasil; dois estados são adjacentes se têm uma fronteira comum. Quantos vértices tem o grafo? Quantas arestas? 6. O grafo dos movimentos da dama , ou simplesmente grafo da dama, é dama definido assim: os vértices do grafo são as casas de um tabuleiro de xadrez com t linhas e t colunas (no tabuleiro usual temos t= 8) e dois vértices são adjacentes se uma dama (= queen ) do jogo de xadrez pode saltar de um deles para o