Grafos

GRAFOS

Matemática Aplicada à computação
Profesora: Cristiana Vidal Accioly

Problema: Como interligar cidades construindo linhas de trêm com menor custo?
• Suponha que o secretário de transportes da
Paraíba quer projetar um sistema ferroviário para interligar todos os grandes centros da Paraíba
(Indicados no mapa). Qual a melhor maneira de interligar todas as cidades, de forma a construir o menor número de linhas? (Com menor custo?
Considerando o custo apenas da quantidade de ferro para instalação das linhas que ligam uma estação a outra.)

Figura 1

GRAFOS

Um grafo é uma conjunto não vazio de vértices
(nós) (V) e um conjunto de arcos (arestas) (E) tais que cada arco conecta dois vértices.
G(V, E)
É uma estrutura usada para representar um modelo em que existem relações entre os objetos de uma certa coleção.

Exemplos de grafos

Figura 2

Aplicações
Problemas em cidades cidades, rede de estradas, redes de computadores …
Na prática:
- As linhas de metro das grandes cidades utilizam grafos de modo a minimizarem o tempo das ligações;
- A distribuição de correio, minimizando percursos de forma a otimizar as deslocações, tanto para um único carteiro como para uma equipe (o mesmo se aplica a empresas de distribuição); - Os sistemas de patrulha da polícia realizam estudos de otimização recorrendo a grafos;

Representação
• Vértices – pontos ou círculos.
• Arcos – linhas que unem dois vértices.
1

2

1

2

6
3

4

4

3

5
5
Conjunto de todos os vértices
V={1, 2, 3,4 , 5, 6}
Conjunto de todos os arcos
E = {(1,2), (1,4), (4,3), (3,5), (2,6)}
Figura 3a

Conjunto de todos os vértices
V={1, 2, 3,4 , 5}
Conjunto de todos os arcos
E = {(1,2), (1,4), (1,3), (4,3), (2,3)}
Figura 3b

Conceitos
• Grafo direcionado – (dígrafo) – arcos iniciam num determinado vértice e terminam em outro. (sentido)
1

2

4
3

Figura 4

Conceitos
• Nós adjacentes –Dois nós em um grafo são
ditos