Trabalho sobre grafos

2871 palavras 12 páginas
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

Relacionados

  • Trabalho sobre grafos
    1438 palavras | 6 páginas
  • Trabalho sobre Teoria dos Grafos
    3822 palavras | 16 páginas
  • Grafos
    695 palavras | 3 páginas
  • Programação Orientada à Aspectos
    8086 palavras | 33 páginas
  • APLICAÇÃO DO ALGORITMO DO CARTEIRO CHINÊS EM ROTAS LOCAIS EM UM AMBIENTE ANDROID COM INTERFACE GRÁFICA
    19757 palavras | 80 páginas
  • Teoria de grafos: - uma possibilidade interdisciplinar ao alcance do ensino fundamental e médio
    2586 palavras | 11 páginas
  • Problema do carteiro chinês
    992 palavras | 4 páginas
  • sindicato
    13069 palavras | 53 páginas
  • Resenha II Breno Luis SantAna Freitas Pereira
    1438 palavras | 6 páginas
  • JIC SaSilva 1
    2174 palavras | 9 páginas