Trabalho sobre grafos

Trabalho Grafos

Ciência da Computação - UEZO - Rio de Janeiro - RJ

RESUMO
São inúmeras as aplicações de grafos, bem como os problemas clássicos que são resolvidos por meio de técnicas que utilizam grafos. Serão apresentados conceitos básicos de grafos, métodos de árvore geradora mínima, caminho mínimo e os principais métodos de busca, visando esclarecer sobre a importância dos grafos em aplicações práticas. Palavras-chave: Grafos. Busca em grafos. Aplicações de grafos. Caminho mínimo.
Algoritmo de Dijkstra. Árvore geradora mínima.

1 Introdução
Você seria capaz de ir em todos os pontos da figura sem tirar o lápis do papel e sem passar 2 vezes pelo mesmo ponto?

Figura 1: Grafo introdutório

Você pode pensar se isso irá server para algo em alguma ocasião, ou não. Mas pense: Você está dirigindo seu carro e este com pouco combustível e você tem pouco tempo para passar nessas 6 casas, para entregar encomendas, então qual seria o caminho que você gastaria menos combustível e percorreria em um menor tempo? Essas são as questões que um grafo tenta responder.

1.1 Conceitos Básicos
Grafo: Conjunto de vértices e arestas.
Vértice: Objeto simples que pode ter nome e outros atributos.
Aresta: Conexão entre dois vértices.
Notação: G = (V, A)

G: Grafo
V: Conjunto de vértices
A: Conjunto de arestas

1.1.1 Tipos e definições de Grafo
Serão citados alguns tipos de grafos entre os vários existentes.
Valorados ou não-valorados: Um grafo é valorado quando a cada arco (ou nó) de G é associado um valor numérico e não-valorado, quando não há distinção valorativa entre os vários nós e arcos.
Para determinar o caminho mais curto entre dois nós, faz-se:
 Para grafos não valorados, o caminho mais curto é o que tem o menor número de arcos.  Grafos valorados requerem algoritmos mais sofisticados.
Grafos podem ser do tipo direcionados ou não direcionados, e ambos possuem grau:
Um grafo direcionado G é um par (V, A), onde V é um conjunto finito