Grafos Aula01 1

Teoria dos Grafos

Curso: Ciência da Computação
Disciplina: Teoria dos Grafos
Profª Luciana Ap. Oliveira Betetto

Aula 01

1. Definição e Aplicações de Grafos
Um grafo é uma representação gráfica de elementos de dados e das conexões entre alguns destes itens. Um grafo pode ser informalmente definido como um conjunto de objetos chamados vértices e um conjunto de arestas que unem esses pares de objetos. A maneira mais comum de representar um grafo é por meio de um diagrama, no qual os vértices são representados por pontos, e as arestas, por um segmento de reta.
Grafos podem ser usados para representar mapas, onde cada vértice representa uma cidade, e cada aresta representa uma estrada entre as cidades correspondentes. Em outra aplicação, um grafo pode ser usado para representar uma árvore genealógica. Nesse caso, os vértices representam indivíduos em uma família. Uma aresta conecta dois indivíduos da família se um deles é filho ou filha do outro.
Uma árvore é um caso particular de grafo onde as conexões entre os elementos não são circulares. Diagramas de organizações, mapas rodoviários, redes de transporte e de comunicações e outras pode ser representado como grafos ou árvores. Em algumas situações “uma figura vale por centenas de palavras”.
Definição: um grafo é uma tripla ordenada (N,A,g) onde:
N = um conjunto não-vazio de vértices (nós ou nodos)
A = um conjunto de arestas (arcos) g = uma função que associa cada aresta a um par não ordenado x-y de vértices chamados de extremos de a.
Nossos grafos terão sempre um número finito de vértices e de arestas.
O conjunto de vértices do mapa da empresa aérea da Figura 1 é {Chicago, Nashville, Miami,
Dallas, St. Louis, Albuquerque, Phoenix, Denver, San Francisco, Los Angeles}. Existem 16 arestas; por exemplo, Phoenix-Albuquerque, Albuquerque-Dallas, etc.

Figura 1

1º semestre 2015

1/6

Teoria dos Grafos

Existem grafos, entretanto, com a seguinte propriedade: não importa como eles são desenhados no plano (com linhas