TEORIA DOS GRAFOS

Prévia do material em texto

Teoria dos grafos 
FATEC Carapicuíba 
Augusto de Toledo Cruz Junior 
HISTÓRICO 
Teoria dos grafos 
2 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Origem 
• O artigo do matemático e físico 
suiço Leonhard Euler, publicado em 
1736, sobre o problema das Sete 
Pontes de Königsberg, é considerado 
o primeiro resultado da teoria dos 
grafos e não passava de uma 
especulação matemática. Era um 
jogo análogo aos atuais quebra-
cabeças para crianças, baseados em 
um desenho cujas linhas devem ser 
percorridas sem que se tire o lápis 
do papel e sem passar duas vezes 
sobre a mesma linha. 
Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 3 
Desenvolvimento 
• Em 1847 Kirchhoff iniciou o estudo de árvores 
(um tipo de grafo) quando estudava circuitos 
elétricos 
• Em 1857 Cayley relacionou esta teoria com o 
estudo de isômeros na química 
• Em 1859 Hamilton estudava problemas de 
caminhos e em 1869 Jordan procurava 
formalizar a teoria das árvores 
4 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Desenvolvimento no século XX 
• Muitos pesquisadores passaram a estudar, em 
particular os matemáticos 
• Um grande número de aplicações para pesquisa 
operacional foi desenvolvida. Um dos mais extensos e 
importantes capítulos da teoria dos grafos foi 
desenvolvida em 1962 por Ford e Fulkerson 
• Atualmente há tendência em considerar o estudo de 
fluxos em redes como o único de real interesse. Não é 
o único mas é considerado o capitulo mais importante 
da teoria para a pesquisa operacional 
5 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
CONCEITOS 
Teoria dos grafos 
6 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Visão geral de grafo 
• A Teoria dos Grafos é um 
ramo da matemática que 
estuda as relações entre 
os objetos de um 
determinado conjunto. 
• Grafo é uma estrutura 
G(V,A) onde V é um 
conjunto não vazio de 
objetos denominados 
vértices ou nodos e A é 
um conjunto de pares não 
ordenados de V, chamado 
arestas (arcos ou ramos). 
 
 
7 
Vértice 
Aresta 
Grafo com 4 vértices e 6 arestas 
Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Visão geral de grafo 
• Dependendo da aplicação, arestas podem ou não 
ter sentido, pode ser permitido ou não arestas 
ligarem um vértice a ele próprio e vértices e/ou 
arestas podem ter um peso (numérico) 
associado. Se as arestas têm um sentido 
associado (indicada por uma seta na 
representação gráfica) temos um grafo 
direcionado, grafo orientado ou digrafo. 
• Um grafo com um único vértice e sem arestas é 
conhecido como o grafo trivial ou "o ponto". 
 
8 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Composição de um grafo 
• Seja, por exemplo, o grafo G(V,A) 
dado por: 
– V = { p | p é uma pessoa } 
– A = { (v,w) | < v é amigo de w > } 
 
• Esta definição representa toda uma 
família de grafos. Um exemplo de 
elemento desta família é dado por: 
– V = { Maria, Pedro, Joana, Luiz } 
– A = { (Maria, Pedro) , (Joana, Maria) , 
(Pedro, Luiz) , (Joana, Pedro) } 
 
9 
• Neste exemplo estamos 
considerando que a 
relação <v é amigo de w> 
é uma relação simétrica, 
ou seja, se <v é amigo de 
w> então <w é amigo de 
v>. Como conseqüência, 
as arestas que ligam os 
vértices não possuem 
qualquer orientação 
Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Grafo orientado (Digrafo) 
A relação definida por A não é simétrica pois se <v é pai/mãe de w>, não é o 
caso de <w é pai/mãe de v>. Há, portanto, uma orientação na relação, com 
um correspondente efeito na representação gráfica. Neste caso o grafo é 
dito ser um grafo orientado (ou digrafo) e as conexões entre os vértices de 
arcos 
10 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Adjacência 
• Em um grafo simples dois vértices v e w 
são adjacentes (ou vizinhos) se há uma 
aresta a=(v,w) entre os vértices v e w . Está 
aresta é dita ser incidente a ambos, v e w. 
É o caso dos vértices Maria e Pedro. No 
caso do grafo ser orientado, a 
adjacência (vizinhança) é especializada 
em: 
• Sucessor: um vértice w é sucessor de v se 
há um arco que parte de v e chega em w. 
Por exemplo, diz-se que Emerson e Antonio 
são sucessores de Alfredo. 
• Antecessor: um vértice v é antecessor de w 
se há um arco que parte de v e chega em 
w. Por exemplo, diz-se que Alfredo e Cecília 
são antecessores de Antonio. 
 
11 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Grau 
• O grau de um vértice é dado pelo número de 
arestas que lhe são incidentes. Por exemplo: 
grau(Pedro) = 3 e grau(Maria) = 2 
• No caso do grafo ser dirigido orientado, a 
noção de grau é especializada em: 
– Grau de emissão: o grau de emissão de um 
vértice v corresponde ao número de arcos que 
partem de v. Por exemplo: 
• grauDeEmissão(Antonio) = 1 
• grauDeEmissao(Alfredo) = 2 
• grauDeEmissao(Renata) = 0 
– Grau de recepção: o grau de recepção de um 
vértice v corresponde ao número de arcos que 
chegam a v. Por exemplo: 
• grauDeRecepção(Antonio) = 2 
• grauDeRecepção(Alfredo) = 0 
• grauDeRecepção(Renata) = 1 
 
12 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Fonte e sumidouro 
• FONTE Um vértice v é uma 
fonte se grauDeRecepção(v) = 
0. É o caso dos vértices Isadora, 
Alfredo e Cecília 
• SUMIDOURO Um vértice v é 
um sumidouro se 
grauDeEmissão(v) = 0. É o caso 
dos vértices Renata e Emerson 
13 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Laço 
• Um laço é uma aresta ou 
arco do tipo a=(v,v), ou 
seja, que relaciona um 
vértice a ele próprio. Na 
figura há três ocorrências 
de laços para um grafo 
não orientado  nos 
vértices A, C e B 
14 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Grafos regular e completo 
GRAFO REGULAR Um grafo é 
dito ser regular quando 
todos os seus vértices tem o 
mesmo grau. O grafo da 
figura abaixo, por exemplo, é 
dito ser um grafo regular-3 
pois todos os seus vértices 
tem grau 3. 
15 
GRAFO COMPLETO Um grafo é dito ser 
completo quando há uma aresta 
entre cada par de seus vértices. 
Estes grafos são designados por Kn, 
onde n é a ordem do grafo. 
Um grafo Kn possui o número máximo 
possível de arestas para um dados n. 
Ele é, também regular-(n-1) pois 
todos os seus vértices tem grau n-1. 
Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Grafo valorado 
• Um grafo G(V,A) é dito ser 
valorado quando existe uma 
ou mais funções relacionando 
V e/ou A com um conjunto de 
números. Para exemplificar, 
seja G(V,A) onde: 
– V = {v | v é uma cidade com 
aeroporto} 
– A = {(v,w,t) | <há linha aérea 
ligando v a w, sendo t o tempo 
esperado de vôo>} 
 
16 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Florianópolis 
Porto 
Alegre 
Curitiba São 
Paulo 
60 
20 
50 
45 
30 
Cadeia 
• Uma cadeia é uma seqüência qualquer de arestas adjacentes que ligam 
dois vértices. O conceito de cadeia vale também para grafos orientados, 
bastando que se ignore o sentido da orientação dos arcos. A seqüência de 
vértices (x6, x5, x4, x1) é um exemplo de cadeia 
• Uma cadeia é dita ser elementar se não passa duas vezes pelo mesmo 
vértice 
• É dita ser simples se não passa duas vezes pela mesma aresta (arco) 
• O comprimento de uma cadeia é o número de arestas (arcos) que a 
compõe 
 
17 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Caminho e Ciclo 
• CAMINHO Um caminho é uma cadeia na qual todos os arcos 
possuem a mesma orientação. Aplica-se, portanto, somente a 
grafos orientados. A seqüência de vértices (x1, x2, x5, x6, x3) éum exemplo de caminho 
• CICLO Um ciclo é uma cadeia simples e fechada (o vértice 
inicial é o mesmo que o vértice final). A seqüência de vértices 
(x1, x2, x3, x6, x5, x4, x1) é um exemplo de ciclo elementar 
18 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Grafos Conexo e Desconexo 
• GRAFO CONEXO Um grafo 
G(V,A) é dito ser conexo se 
há pelo menos uma cadeia 
ligando cada par de 
vértices 
19 
• GRAFO DESCONEXO Um 
grafo G(V,A) é dito ser 
desconexo se há pelo 
menos um par de vértices 
que não está ligado por 
nenhuma cadeia 
Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Raiz e Anti-raiz 
• RAIZ Se um vértice B é 
uma fonte e todos os 
demais vértices podem ser 
atingidos por um caminho 
partindo de B, então B é 
uma raiz 
• ANTI-RAIZ Se um vértice A 
é um sumidouro e todos os 
demais vértices podem 
atingir A por um caminho, 
então A é uma anti-raiz 
20 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Árvore e Arborescência 
• ÁRVORE É um 
grafo conexo 
sem ciclos 
21 
• ARBORESCÊNCIA 
É uma árvore que 
possui uma raiz. 
Aplica-se, portanto, 
somente a grafos 
orientados 
Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Rede 
• Uma rede é um grafo orientado e sem laços que possui 
exatamente uma raiz e uma anti-raiz. Na figura a rede é valorada 
22 
Raiz Anti - raiz 
Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Grafo planar 
23 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
ALGUMAS APLICAÇÕES EM 
LOGÍSTICA DE TRANSPORTE 
Teoria dos grafos 
24 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Problema de ciclo 
• Um transportador deseja verificar se é possível fazer 
um ciclo, ou seja, rodar por uma cadeia (seqüência 
qualquer de arestas adjacentes que ligam dois 
vértices) simples (não passa duas vezes pela mesma 
aresta) e fechada (o vértice inicial é o mesmo que o 
vértice final) 
• No exemplo a seguir constata-se que não é possível 
fazer o ciclo, mas em muitos outros casos constata-se 
a possibilidade de fazê-lo e como 
25 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Problema de ciclo: 7 pontes de 
Königsberg (enigma do Euler) 
• O rio Pregel divide o centro da cidade de Königsberg (Prússia no século 
XVII, atual Kaliningrado, Rússia) em quatro regiões. Essas regiões são 
ligadas por um complexo de sete (7) pontes, conforme mostra a figura 
26 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Problema de ciclo: grafo de Euler para 
7 pontes de Königsberg 
27 
Os arcos 
são as 
pontes 
Os vértices 
são as 
regiões 
• Discutia-se nas ruas da 
cidade a possibilidade de 
atravessar todas as 
pontes, voltando ao 
lugar de onde se saiu, 
sem repetir alguma. 
Havia-se tornado uma 
lenda popular a 
possibilidade da façanha 
quando Euler, em 1736, 
provou que não existia 
caminho possível para 
estas restrições 
Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Caminho de custo mínimo 
• De forma a reduzir seus 
custos operacionais, uma 
empresa de transporte de 
cargas deseja oferecer 
aos motoristas de sua 
frota um mecanismo que 
os auxilie a selecionar o 
melhor caminho (o de 
menor distância) entre 
quaisquer duas cidades 
por ela servidas, de forma 
a que sejam minimizados 
os custos de transporte 
28 
• Um possível modelo para este problema 
poderia ser: 
– G (V,A) V = { x | x é cidade } 
– A = { (xi, xj, d) | há uma conexão por estrada 
entre as cidades xi e xj, sendo d a distância 
que as separa } 
Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Localização em função do custo de 
transporte: método dos momentos 
29 
Os vértices são as 
localidades 
valorados com o 
peso da carga a ser 
transportada 
Os arcos são as 
estradas valoradas 
com a distância e o 
custo por unidade de 
distância 
O momento M para cada localidade é o produto do custo unitário de 
transporte pela quantidade a ser transportada e pela distancia a ser 
percorrida 
A localidade que tiver a menor soma de momentos será a escolhida 
Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Caminho crítico 
• Considere que tenhamos uma rede R(V,A), ou seja, um grafo orientado, sem laços 
e valorado, que contém exatamente uma fonte e um sumidouro. Nesta rede, os 
vértices representem eventos, os arcos representem atividades e os valores 
associados aos arcos representem a duração das atividades 
• A disposição dos eventos (vértices) e das atividades (arcos) no grafo exprimem 
uma relação de dependência: um evento não ocorre antes que todas as atividades 
a ele imediatamente precedentes (arestas incidentes) sejam encerradas; de forma 
similar, uma atividade não pode ser iniciada antes que ocorra o evento que 
representa o início da atividade 
• Nesta rede, o interesse maior é o de determinar o(s) caminho(s) do vértice inicial 
ao vértice final cuja soma das durações das atividades seja máxima. Este(s) 
caminho(s) é chamado de caminho crítico, suas atividades têm folga zero, e 
determina o prazo de realização das atividades do vértice inicial ao vértice final 
• As atividades do caminho crítico devem ser geridas para que não atrasem senão 
atrasa a realização da rede toda 
 
30 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
EXERCÍCIOS 
Teoria dos grafos 
31 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Exercícios sobre conceitos 
32 
• Identifique os grafos conforme seus vértices (V), 
arcos (A) e graus (g): 
a. b. 
c. d. 
Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Exercício de caminho de custo mínimo 
33 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Exercícios sobre conceitos 
• A partir dos dados [vértices (V), arcos (A) e graus 
(g)], monte os respectivos grafos: 
a. G(6,8) e g=(1,3,3,3,3,3), conexo 
b. G(6,2) e g=(0,0,1,1,1,1), desconexo 
c. G(6,3) e g=(0,1,1,1,1,2), desconexo 
d. G(6,9) e g=(3,3,3,3,3,3), conexo regular 
e. G(5,8) e g=(3,3,3,3,4), conexo completo 
34 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Exercício de localização 
35 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr. 
Bibliografia utilizada 
• BOAVENTURA NETTO, P. O. Teoria e modelos de grafos. São 
Paulo: Edgard Blucher, 1979. 249 p. 
• LIMAD, W. G. N., , CARVALHO, A. C.. B. D. Teoria dos Grafos. 
Métodos Quantitativos de Gestão. MGQ - 3o. Ciclo FATEC 
Carapicuíba. [s.l.], [200-]. Posse dos professores autores. 
• MARIANI, A. C. Livro eletrônico teoria dos grafos. Disponível 
em: <http://www.inf.ufsc.br/grafos/livro.html> Acesso em: 
27 mai. 2009. 
• PETRÔNIO, G. M., LAUGENI, F. P. Administração da produção. 
2 ed. São Paulo: Saraiva, 2006. 562 p. 
36 Setembro 2009 FATEC Carapicuíba – MQG - Augusto T. Cruz Jr.