Grafos

GRAFOS
Matemática Discreta - Informática

Profª Me. Geiseane Rubi

?

Refere-se a um método de representação de uma ideia ou conceito, por meio da ilustração ou por escrito.

Tanto em MATEMÁTICA como na linguagem corrente, costuma referir-se a um diagrama usado para exibir o relacionamento entre duas grandezas.

- PROBLEMAS:

*RESOLUÇÃO DOS TRÊS SERVIÇOS

As pontes de Königsberg
Em Königsber, Alemanha, um rio que passava pela
Cidade tinha uma ilha e, logo depois de passar por essa ilha se bifurcava em 2 ramos. Nessa região existiam 7 pontes, como mostra a figura.

É possível andar por toda a cidade de tal modo que cada ponte seja atravessada

exatamente uma vez?
4

Histórico

Euler resolveu o problema das pontes de Königsberg do rio Pregel, em
1736, utilizando um modelo de grafos: partir de uma das 4 regiões, atravessar cada ponte uma única vez e retornar à região de partida.

5

Königsberg -Kalinigrado atualmente.

6

Grafo para o Rio Pregel e suas sete pontes

Modelo de grafos utilizado por Euler para demonstrar que o problema não tem solução.
Para haver solução é necessário que cada região tenha um

número par de pontes associadas.

7

O problema agora consiste em percorrer todos os arcos, passando por cada um apenas uma vez, sem levantar o lápis do papel.

Na teoria de grafos, um caminho completo com as propriedades descritas acima de não retraçar nenhum arco é chamado de TRAJETÓRIA de
EULER
8

Será que existe alguma trajetória de Euler para o gráfico abaixo? Se existir, como ela é?

9

Aplicações de modelos em grafos
1. Grafos planares: problemas de montagens/ trevos

A, B, C : linhas de montagens/ rodovias principais

D1, D2, D3: departamentos/ rodovias secundárias
Ligações: esteiras/ viadutos ou túneis Figura: Um problema de montagem.

2.

Problemas de Localização

Existindo n cidades consumidoras do produto fabricado por uma determinada empresa, deseja-se saber onde seria o melhor local para a instalação de uma filial desta empresa que
atendesse