Grafos

Apostila

Teoria dos Grafos

Professora: MSc. Sofia Mara de Souza Período: 4º Período Curso: Ciência da Computação

UNIRG

O que é ?
1 O grafo é uma representação gráfica de relações entre “objetos”, isto é, elementos de dados. Essa representação advém de uma noção abstrata e intuitiva de um determinado problema ou aplicação prática.
1 Um grafo é formado por dois conjuntos: um conjunto de vértices e arestas; cada aresta está associada a dois vértices: o primeiro é a ponta inicial e o segundo a ponta final. Pode-se imaginar um grafo como um mapa rodoviário idealizado: os vértices são as cidades e as arestas são estradas de mão única.
Como é usado?
1 Os grafos são descritos em um espaço plano, em que os elementos de dados são representados por círculos chamados vértices, e as relações entre tais elementos são representadas por linhas denominadas arestas.
Por que é usado?
2 Existe a necessidade de se representar problemas existentes de forma gráfica assim como solução destes.
2 É fundamental para a maioria das aplicações. De fato, a habilidade para resolver problemas é freqüentemente usada como medida para máquinas e homens de interesse da Inteligência Artificial. Exemplo: uma representação gráfica, um método de avaliação e soluções de busca em amplitude com menor custo, a técnica da subida da encosta, etc.
Exemplos de uso de grafos
1 Cada vértice é um dos setores (agricultura, bancos, mineração, comércio, etc.) da economia de um país. Há uma aresta de x a y se houver um fluxo significativo de bens e serviços de x para y. O grafo não tem arestas paralelas, mas pode ter laços; em geral, o grafo não é simétrico.
1 Cada vértice é uma tarefa de um grande projeto. Há uma aresta de x a y se x é pré-requisito de y, ou seja, se x deve estar pronta