Teoria dos grafos

Prévia do material em texto

Teoria dos grafos
Pesquisa operacional
Conteúdo
Definição
Origem
Propriedades
Classificação
Aplicações 
Algoritmos
Problemas
Exercícios
Definição
O grafo é uma ferramenta matemática que pode ser usada para modelar problemas, encontrando uma solução. Graficamente, aparece representado por uma figura com pontos ou vértices, significando os objetos, unidos por uma linha denominado aresta configurando a relação imaginada.
Sete pontes de königsberg
Foi desenvolvida por Leonhard Euler em 1735.
Problema: atravessar as sete potes do Rio Prego sem passar duas vezes na mesma ponte
Sete pontes de königsberg
Simplificou o problema em um grafo, para que chegasse em uma solução de forma mais objetiva.
Sete pontes de königsberg
Propriedades:
4 vértices
7 arestas
Graus impares
Definido como multigrafos
IMPOSSÍVEL A SOLUÇÃO DO GRAFO
3
5
3
3
Vértice
Aresta
REPRESENTAÇÃO MATEMÁTICA
	Um grafo é representado matematicamente por:
	G = (V,E)
	
	Onde V é o conjunto de vértices e E é o conjunto de arestas ou ligações entre os vértices. (|V| = n, |E| = m).
	Onde: n = |V| é a ordem do grafo
 		 m = |E| é o tamanho do grafo. 
		 Se m = 0 o grafo é dito trivial. 
PROPRIEDADES
Relações de incidência e de adjacência
Se uma aresta conecta dois vértices, então esses dois vértices são ditos incidentes à aresta. 
1 é incidente a 2 e 5, mas não é incidente a 3, 4 ou 6; 
4 é incidente a 5, 3 e 6, mas não a 2 nem a 1.
PROPRIEDADES
Relações de incidência e de adjacência
Dois vértices são considerados adjacentes se uma aresta existe entre eles. Os vértices 1 e 2 são adjacentes, mas os vértices 2 e 4 não são. Além disso o vértice 1 possui 2 vizinhos: vértice 2 e vértice 5.
PROPRIEDADES
	Exemplo:
O grafo dos estados do Brasil é definido assim: cada vértice é um dos estados da República Federativa do Brasil; dois estados são adjacentes se têm uma fronteira comum.
PROPRIEDADES
	Valência (Grau)
É o número de arestas incidentes a ele. Se houver laços, serão contados duas vezes. No grafo de exemplo os vértices 1 e 3 possuem uma valência de 2, os vértices 2, 4 e 5 têm a valência de 3 e o vértice 6 tem a valência de 1
PROPRIEDADES
	Passeio
Um passeio p entre dois vértices A e B, definido como p(A,B), é uma lista alternada de vértices e arestas p(A,B)=v0, e1, v1, e2, v2,..., ek, vk. 
O tamanho de um passeio, definido por |p| corresponde ao número de arestas que possui, incluindo as repetições. 
PROPRIEDADES
	Passeio
Na figura abaixo, um passeio do vértice a até o vértice d possível é a lista p(a,d)=a, e9, c, e2, b, e1, a, e9, c, e8, d de tamanho 5. Note que a aresta e9 se repete. É necessário listarmos as arestas em um passeio para distinguirmos entre as diversas arestas existentes quando estamos trabalhando em um grafo que não é simples. Em um grafo simples, basta listarmos os vértices
PROPRIEDADES
	Caminho
É uma sequência de vértices tal que de cada um dos vértices existe uma aresta para o vértice seguinte. Um caminho é chamado simples se nenhum dos vértices no caminho se repete.
PROPRIEDADES
	Caminho
 Por exemplo, para ir de A até G basta fazer a seguinte sequência A → C → E → F → G. Dizemos então, que esta sequência é um caminho de A até G, com comprimento 4
PROPRIEDADES
	Caminho
 Tipos de caminhos: 
 Caminho euleriano em um grafo é o caminho que usa cada aresta exatamente uma vez.
 Caminho hamiltoniano em um grafo é o caminho que visita cada vértice exatamente uma vez.
Caminho euleriano
Caminho hamiltoniano
PROPRIEDADES
	Ciclo
 Agora, um caminho fechado (que começa e acaba com o mesmo vértice) é chamado de ciclo. Por exemplo, o caminho A → B → E → A é um ciclo de comprimento 3. 
 
PROPRIEDADES
	Laço ou auto-loop
 É uma aresta que conecta um vértice a ele mesmo. Um grafo simples, não contém nenhum laço.
 
	Grafos direcionados e não direcionados:
Direcionados: as arestas possuem sentido; uma aresta sai de um vértice e entra em outro; podem existir laços.
Não direcionados: As arestas (u,v) e (v,u) são consideradas uma única aresta; laços são permitidos.
PROPRIEDADES
CLASSIFICAÇÃO
SIMPLES: Não apresenta múltiplas arestas ou auto-loop, entre um vértice e outro
CLASSIFICAÇÃO
CONEXO: quando há um caminha entre quaisquer dois vértices
O número mínimo de arestas par o grafo ser considerado conexo é a quantidade de vértices menos um.
CLASSIFICAÇÃO
REGULAR: os vértices possuem o mesmo grau
CLASSIFICAÇÃO
COMPLETO: é um grafo regular fortemente conexo.
Todos os pares de vértices são adjacentes, ou seja, não há um intermediário para ir de um vértice a outro
Devem existir n(n-1)/2 arestas
CLASSIFICAÇÃO
CICLO E CIRCUITO: é um caminho de algum vértice v até novamente v, de forma que nenhum vértice ocorra mais de uma vez no caminho.
Um grafo sem ciclo é um grafo acíclico
CLASSIFICAÇÃO
COMPLETO BIPARTIDO: quando cada nó de um conjunto está ligado a todos os outros nós do outro conjunto
CLASSIFICAÇÃO
ISOMORFO: podem ter representações gráficas diferentes mas são essencialmente o mesmo grafo.
CLASSIFICAÇÃO
Simples: um grafo simples não tem loops nem multi-arestas.
Multigrafo: pode ter multi-arestas mas não pode ter laços.
 Exemplo: para modelar as possíveis conexões de voos oferecidas por uma linha aérea.
Grafo simples
Multigrafo
CLASSIFICAÇÃO
Pseudografo: pode ter multi-arestas e laços
Trivial: consiste de um vértice sem arestas
Nulo: não tem vértices, nem arestas
Vazio: é o grafo cujo conjunto de arestas é vazio.
Regular: é um grafo em que todos os vértices tem o mesmo grau.
CLASSIFICAÇÃO
Completo: é o grafo simples em que, para cada vértice do grafo, existe uma aresta conectando este vértice a cada um dos demais. Ou seja, todos os vértices do grafo possuem mesmo grau. O grafo completo de n vértices é frequentemente denotado por Kn. Ele tem n(n-1)/2 arestas (correspondendo a todas as possíveis escolhas de pares de vértices).
Árvore: é um grafo simples acíclico e conexo. Às vezes, um vértice da árvore é distinto e chamado de raiz. As árvores são muito usadas como estruturas de dados em informática (veja estrutura de dados em árvore).
CLASSIFICAÇÃO
Floresta: é um conjunto de árvores; equivalentemente a uma floresta, em algum grafo acíclico.
Subgrafo: de um grafo G é um grafo cujo conjunto dos vértices é um subconjunto do conjunto de vértices G, cujo conjunto de arestas é um subconjunto do conjunto de arestas de G, e cuja função w é uma restrição da função de G
Subgrafo gerador: é aquele obtido pela remoção de uma ou mais arestas de um outro grafo, dizemos então que este novo grafo obtido é gerador do primeiro,
ALGORITMOS IMPORTANTES
Algoritmo de Dijkstra
Algoritmo de Kruskal
Algoritmo do vizinho mais próximo
Algoritmo de Prim.
PROBLEMAS
Teorema das quatro cores
Conjunto independente
Clique
Problema do caminho mínimo
Problema do carteiro chinês
Problema do caixeiro viajante
Problema de fluxo máximo
Grafo de adjacência dos Estados do Brasil
As Estações são os nós e os caminhos são arestas
APLICAÇÕES PRÁTICAS
Aplicação do algoritmo de Dijkstra
APLICAÇÕES PRÁTICAS
APLICAÇÕES PRÁTICAS
Motores de busca de páginas Web
Vértices são as páginas HTML e as arestas (direcionadas) são links ligando as páginas
Identificar proximidade entre duas páginas quaisquer
Identificar se uma página é acessível a partir de outra
Identificar o número de links para uma página (grau do vértice)
APLICAÇÕES PRÁTICAS
Roteamento de Carga
Vértices são pontos de entrega e as arestas (com pesos) são estradas
Descobrir a rota de entrega com menor custo
Identificar a rota mais rápida
Problema de Fluxo em Redes
Exercício
Um químico deseja embarcar os produtos A, B, C, D, E, F e X, usando o menor número de caixas. Os produtos A, B, C e X reagem entre si. A reage com F e com D. E também reage com F e com D. E o produto F reage com D.
Demonstre o grafo que modela essa situação, mostre um diagrama desse grafo e use esse grafo para descobrir o menor número de caixas necessárias para embarcar os produtos com segurança.
Exercício
A
BC
X
F
E
D
Caixa 1 = {A}
Caixa 2 = {B, D}
Caixa 3 = {C, E}
Caixa 4 = {X, F}
R: São necessárias 4 caixas para embarcar os produtos com segurança segundo o grafo.
BIBLIOGRAFIA
https://www.obm.org.br/content/uploads/2017/01/Nivel1_grafos_bruno.pdf
https://pt.wikipedia.org/wiki/Teoria_dos_grafos
https://www.slideserve.com/adina/algoritmos-em-grafos
https://slideplayer.com.br/slide/2823599/