AULA 12
PROBLEMAS DE CONEXÃO
Eduardo Camargo de Siqueira
PESQUISA OPERACIONAL
TECNÓLOGO EM ANÁLISE E
DESENVOLVIMENTO DE SISTEMAS
INTRODUÇÃO
• Os Problemas de Conexão faz parte de uma
área contida na Pesquisa Operacional.
• Pode ser considerada como uma teoria
baseada na interligação de pontos e linhas.
• Utilizada principalmente na
problemas de roteamento.
solução
de
2
INTRODUÇÃO
• Em 1736, o matemático Leonhard Euler
resolveu o primeiro problema (“O problema
das pontes de Konigsberg”).
• Origem da teoria dos grafos.
• Linhas devem ser percorridas sem que se
tire o lápis do papel e sem passar duas
vezes sobre a mesma linha.
3
INTRODUÇÃO
• Em 1847, o físico Gustav Robert Kirchhoff
iniciou o estudo de um certo tipo de grafo
chamado árvores.
• Quando estudava problemas de circuitos
elétricos.
4
TEORIA DOS GRAFOS
• Um Grafo é definido como sendo um par
ordenado (𝑉, 𝐴).
• Os elementos de 𝑉 são denominados
vértices ou nós do grafo.
• Os pares ordenados de 𝐴, denominados de
arestas ou arcos do grafo.
5
TEORIA DOS GRAFOS
• Aspectos importantes em relação aos
Grafos:
• Quando um arco é incidente a um único
vértice é denominado laço.
• Dois vértices são adjacentes se eles estão
interligados por um arco.
• Uma cadeia é uma sequência de arcos.
6
TEORIA DOS GRAFOS
• Aspectos importantes em relação aos
Grafos:
• Um caminho é uma cadeia em que todos os
arcos têm a mesma direção.
• Um ciclo é uma cadeia cujo vértice inicial e
final é o mesmo.
• Um grafo é conexo quando existe um
caminho entre cada par de vértices.
7
TEORIA DOS GRAFOS
• Quanto às características de seus arcos,
um grafo pode ser:
• Orientado ou não orientado.
• Valorado e não valorado.
• Planar e não planar.
8
TEORIA DOS GRAFOS
9
TEORIA DOS GRAFOS
10
TEORIA DOS GRAFOS
• Quando em um grafo existe a associação de
um ou mais valores aos arcos e/ou nós,
pode-se defini-lo como uma rede.
• Pode-se representar uma rede como 𝑅 =
{𝑉, 𝐴, 𝛼}.
• α é os parâmetros associados aos elementos
do conjunto A e/ou do conjunto 𝑉.
11
TEORIA DOS GRAFOS
12
TEORIA DOS GRAFOS
• Valores de α associados aos arcos:
• a capacidade de fluxo, que corresponde ao
limite que pode passar pelo arco.
• o custo no arco, que pode ser considerado
como um valor monetário, a distância
percorrida ou o tempo de viagem no arco.
13
TEORIA DOS GRAFOS
• Valores de 𝛼 associados aos nós:
• população de uma cidade.
• número de produtos fabricados em uma
unidade.
• demanda de
geográfica.
produtos
em
uma
área
14
TEORIA DOS GRAFOS
• Os problemas de otimização de redes podem ocorrer
em várias áreas.
• Geralmente são encontrados nas áreas de transportes
e comunicações.
•
Um problema típico de transporte consiste em
encontrar uma rota.
• Minimizar ou maximizar alguma medida associada
aos arcos e/ou nós.
15
TEORIA DOS GRAFOS
• Existem outros problemas em que se necessita
minimizar os valores associados aos arcos.
• De forma que possa atender todos os pontos de
uma rede.
• A seguir serão relacionados vários algoritmos que
objetivam a modelagem de redes.
16
PROBLEMAS DE MINIMIZAÇÃO
DE REDES
• Projeto de redes de
conectando 𝑛 localidades.
comunicações
• Arranjo de 𝑛 − 1 conexões, conectando
duas localidades cada.
• Objetivo: dentre as
conexões, achar a
quantidade de cabos.
possibilidades de
que usa menor
17
PROBLEMAS DE MINIMIZAÇÃO
DE REDES
18
PROBLEMAS DE MINIMIZAÇÃO
DE REDES
• Algoritmo de PRIM
• 1º passo: selecionar qualquer nó da rede e o
inserir no conjunto C (árvore mínima).
• 2º passo: identificar o nó que está mais
próximo de qualquer um dos nós do conjunto
C.
• Deve-se repetir este processo até que todos
os nós estejam conectados.
19
EXEMPLO – ALGORITMO PRIM
20
PROBLEMAS DE MINIMIZAÇÃO
DE REDES
• Algoritmo de KRUSKAL
• 1º passo: colocar os arcos em ordem crescente
de valor (A*).
• 2º passo: selecionar o menor dos arcos de A*
que não forme um ciclo com os demais.
• Um arco forma um ciclo quando os vértices deste arco
já fazem parte da árvore mínima em construção.
• Repetir o 2º passo até que a árvore mínima
tenha n-1 arcos.
21
EXEMPLO – ALGORITMO
KRUSKAL
22
CAMINHO MÍNIMO
• Em uma rede podem existir vários caminhos entre
um par de nós (origem/destino).
• Entre os caminhos possíveis, aquele que possui
menor "peso" é chamado de caminho mínimo.
• Este peso pode ser representado pela soma dos
atributos dos arcos que formam o caminho.
23
CAMINHO MÍNIMO
• O problema de caminho mínimo também é
um problema de Emparelhamento.
• O emparelhamento nada mais é que uma
forma de ligação entre dois elementos.
• No caso dos grafos, dois vértices.
24
CAMINHO MÍNIMO
• Para resolver problemas desse tipo, há
vários algoritmos.
• Ford, Faude, Bellman, Dijkstra, Floyd, Hasse
dentre outros.
• Envolvem maior ou menor complexidade de
cálculo.
25
CAMINHO MÍNIMO
• Algoritmo de DIJKSTRA
• Este algoritmo foi desenvolvido em 1959.
• Dantizg e Nicholson (1960) desenvolveram
um algoritmo de duas árvores de Dijkstra.
• Determinar o caminho mínimo de um nó para
outro nó ou para todos os outros nós da rede.
• Arcos orientados e com atributos positivos.
26
FIM
• Dúvidas?
• Obrigado pela atenção!
27