Teoria dos Grafos - Resumo

Teoria dos Grafos

PROF: JULIANO RATUSZNEI. EMAIL: JULIANO.RATUSZNEI@UNICID.EDU.BR

Plano de Ensino

• Fluxos em Redes
  • Conceitos e algoritmo de fluxo máximo
  • Fluxo máximo e corte mínimo
  • Estruturas de dados para redes de fluxo
• Percursos Abrangentes
  • Introdução
  • O problema do carteiro chinês
  • O problema hamiltoniano
  • O problema do caixeiro viajante

Fluxos em Redes

• Algoritmo de Fluxo Máximo
• Fluxo Máximo
• Corte Mínimo
• Estrutura de dados para redes de fluxo

O Problema do Fluxo Máximo

• O problema do fluxo máximo é uma ferramenta de modelagem que pode representar uma variedade de outros problemas.
• Aplicações incluem o fluxo de um líquido através de uma rede de tubos e o fluxo de mercadorias do produtor ao consumidor.

Fluxo

• Para qualquer vértice $v$ do grafo, o fluxo que entra em $v$ (= inflow) é a soma dos fluxos nos arcos que entram em $v$.
• O fluxo que sai de $v$ (= outflow) é a soma dos fluxos nos arcos que saem de $v$.
• O saldo de fluxo (= net flow) em $v$ é a diferença: $netflow = outflow(v) - inflow(v)$
• O saldo de fluxo é estritamente positivo se o fluxo que sai é maior que o fluxo que entra.

Fluxo (Definição Formal)

• Um fluxo (= flow) num grafo com vértice inicial $s$ e vértice final $t$ é uma tabela $f$ que atribui números positivos (não necessariamente inteiros) aos arcos do grafo de tal modo que:
  • o saldo de $f$ é nulo em todo vértice diferente de $s$ e de $t$ e
  • o saldo de $f$ em $s$ é positivo.

Intensidade do Fluxo

• A intensidade (= flow value) de um fluxo $f$ é o saldo de $f$ no vértice inicial $s$.
• Exemplo: em um exemplo dado, a intensidade é 60.
• Representação de um fluxo:
  • Listas de aresta, poderíamos acrescentar um campo nos nós.
  • Matriz, podemos usar uma matriz $f[][]$ definida da maneira óbvia: se $v-w$ é um arco, então $f[v][w]$ é o fluxo no arco;

Exemplo de Fluxo em Grafo-Ciclo

• A tabela a seguir define um fluxo num grafo-ciclo. O vértice inicial é 0 e o vértice final é 2. O fluxo tem intensidade 40.

Corte Máximo

• Corte máximo tem a função de prever em qual parte do grafo possui mais recursos alocados.
• A ideia básica é deslocar os recursos de uma região altamente atendida para uma região que possua uma defasagem de conexões ou recursos.
• Neste caso não há compra de novos recursos apenas a transferência de recursos de uma região para outra.

Corte Mínimo

• Corte mínimo tem a função de prever em qual parte do grafo possui um estrangulamento em algum recurso que diminui o desempenho do sistema.
• A ideia é verificar qual é a parte que ocorre estrangulamento para poder melhorar a fluidez naquele laço ou parte do grafo.
• Neste caso estamos interessados em melhorar o sistema comprando o recurso correto.
• Ex: Em computadores podemos dizer que o Disco pode ser um recurso que ocorre estrangulamento.

Problema Hamiltoniano

• O problema é determinar se existe um caminho que passa por cada cidade (vértice) exatamente uma vez.
• Passar por todos os vértices uma vez.

Problema do Caixeiro Viajante

• Formulando o problema do caixeiro: Suponha que um caixeiro viajante tenha de visitar $N$ cidades diferentes, iniciando e encerrando sua viagem na primeira cidade.
• Suponha, também, que não importa a ordem com que as cidades são visitadas e que de cada uma delas pode-se ir diretamente a qualquer outra.
• O problema do caixeiro viajante consiste em descobrir a rota que torna mínima a viagem total.

Exemplo do Problema do Caixeiro Viajante (n=4)

• Se tivermos quatro cidades A, B, C e D, uma rota que o caixeiro deve considerar poderia ser:
  • saia de A e daí vá para B, dessa vá para C, e daí vá para D e então volte a A.
• Existem seis rotas possíveis:
  • ABCDA, ABDCA, ACBDA, ACDBA, ADBCA, ADCBA

Otimização Combinatória e Enumeração

• O problema do caixeiro é um clássico exemplo de problema de otimização combinatória.
• Primeira abordagem para resolver: reduzi-lo a um problema de enumeração.
  • Achar todas as rotas possíveis e, usando um computador, calcular o comprimento de cada uma delas e então ver qual a menor.
• Ao achar todas as rotas possíveis, estamos contando-as, reduzindo o problema de otimização a um de enumeração.
• Resolução( n ) = ( n - 1 )!

Complexidade do Problema do Caixeiro Viajante

• O problema do caixeiro viajante leva em consideração:
  • Combinatória de percursos (TODOS os percursos)
  • Verificação para cada percurso qual o tamanho do caminho.
  • Para cada um dos caminhos verifica-se qual é o MENOR.
  • Extremamente custoso quando há muitos vértices.
  • Para 13 vértices temos 479.001.600 combinações de caminhos.

Problema da Inspeção de Rotas (Carteiro Chinês)

• O Problema do Carteiro Chinês, enunciado pelo matemático chinês Meigu Guan em 1962.
• Consiste em encontrar um trajeto fechado de custo mínimo que percorre todas arestas de um grafo ao menos uma vez.
• Essa generalização do problema dos circuitos eulerianos possui muitas aplicações na área de logística, podendo ser usado, por exemplo, para reduzir a distância percorrida na rota de carteiros, caminhões de lixo, ou mesmo de veículos de remoção de neve.

Definição do Problema da Inspeção de Rotas

• O problema consiste em encontrar um passeio fechado que visite todas as arestas de um grafo conexo pelo menos uma vez e que possua menor custo.
• A grande diferença aqui é que as arestas podem ser repetidas, ou seja, usadas mais de uma vez no passeio final.

Origem do Nome

• O nome do problema está relacionado ao problema do planejamento de rotas de carteiros: dada uma cidade com várias ruas de diferentes comprimentos e um posto de carteiros, encontrar a menor rota que um carteiro deve percorrer de modo a passar por todas ruas da cidade entregando cartas e voltar ao posto de carteiros no fim de sua rota.

Exemplo de Passeio Fechado de Custo Ótimo

• No exemplo ao lado um passeio fechado de custo ótimo seria: {A, B, D, C, A, D, C, B, A}
• Sendo este um caminho fechado de custo 12 que percorre todas arestas do grafo.
• Neste exemplo foi necessário que as arestas AB e DC fossem percorridas duas vezes no passeio, porém nem sempre é necessária esta repetição.