Teoria de Grafos - apostila

Prévia do material em texto

Introdução à Teoria dos Grafos
OBJETIVO
Apresentar alguns conceitos basilares da Teoria dos Grafos.
REFERÊNCIAS
SUMÁRIO
• Histórico;
• Aplicações;
• Grafo;
• Grafo orientado;
• Ordem e adjacência;
• Graus;
• Vértices isolados, laços, arestas paralelas;
• Vértice pendente;
• Multigrafos, grafos simples, grafos completos;
• Subgrafo;
• Clique;
• Grafo complementar;
• Grafo bipartido;
• Grafo rotulado;
• Grafo valorado;
• Caminho;
• Ciclo e circuito;
• Grafos conexos e não conexos;
• Árvore;
• Caminho e ciclo euleriano;
• Caminho e ciclo hamiltoniano;
• Lista de adjacência;
• Matriz de adjacência;
• Matriz de incidência (Grafos orientados);
• Grafos isomorfos;
• Algoritmos;
• Algoritmos gulosos;
• Heurísticas; e
• Exercícios.
A
D
C
B
HISTÓRICO
No século XVIII, na cidade de Königsberg (antiga Prússia), um
conjunto de sete pontes cruzavam o rio Pregel. Elas
conectavam duas ilhas entre si (A e D) e as ilhas com as
margens (C e B).
Os habitantes perguntavam: 
É possível cruzar as sete pontes numa 
caminhada contínua sem passar duas 
vezes por qualquer uma delas?
Em 1736, Euler apresenta a solução deste problema na
Academia de São Petersburgo, sendo este o primeiro trabalho
sobre Grafos.
APLICAÇÕES
Trata-se de uma ferramenta de estrutura simples, mas extremamente
poderosa para a construção de modelos e resolução de diversos
problemas práticos relativos a:
Processos industriais
Logística
Sistemas de comunicação
Redes de computadores
Engenharia
Jogos
Tomada de decisão
APLICAÇÕES
TEORIA DOS GRAFOS 
A Teoria dos Grafos é uma área da Pesquisa Operacional que
praticamente permeia todas as outras áreas. Daí a sua extrema
importância.
Simulação a Eventos Discretos
Programação Matemática
Teoria das Filas
Apoio Multicritério à Decisão
Estatística
Entre outras
2 4
3
1
TEORIA DOS GRAFOS 
A Teoria dos Grafos é um ramo da matemática que estuda as relações
entre os objetos de um determinado conjunto. Para tal, são empregadas
estruturas chamadas de grafos, G(V,E), onde V é um conjunto não vazio
de elementos denominados vértices (ou nós) e E é um subconjunto de
pares não ordenados de V.
Exemplo:
V = {p | p é uma pessoa}
A = {(v,w) | v é amiga de w}
V = {Maria, José, Ana, Luiz}
A = {(Maria, José), (Maria, Ana), (José, Luiz), (José, Ana)}
Maria José
Ana
Luiz
GRAFO ORIENTADO 
Maria
João Ana
Joana
Exemplo:
V = {p | p é uma pessoa}
A = {(v,w) | v é pai ou mãe de w}
Paulo
Ordem
Adjacência
É o número de vértices do grafo.
Ordem(G1) = 4
Dois vértices - v e w de um grafo - são adjacentes se há uma aresta
a=(v,w) em G.
Ex: José e Luiz em G1
Duas arestas são adjacentes se incidem sobre o mesmo vértice.
Ex: (Ana, Maria) e (Ana, José) em G1
Maria José
Ana
Luiz
Grau de um vértice
É o número de arestas incidentes no vértice. 
Grau(b)=4
Grau de saída (outdegree)
Número de arestas que têm ponta inicial no vértice. 
Gs(b) = 2
Grau de entrada (indegree)
Número de arestas têm ponta final no vértice. 
Ge(b) = 3
Vértice isolado
É aquele que possui grau igual a zero.
Laço
É uma aresta do tipo a=(v,v).
Arestas paralelas
Possuem os mesmos vértices terminais: 
ci=(v,w) e cj=(v,w)
Vértice pendente
Dizemos que um vértice é “pendente” quando Gr(V) = 1.
B
E
A C
DF
Vértice
Aresta
Ponte
Dizemos que uma aresta é uma ponte quando ao removê-la, o grafo deixa de ser conexo.
Multigrafo
É o grafo que possui laços e/ou arestas paralelas.
Grafo simples
Não possui laços e/ou arestas paralelas.
Grafo completo
Um grafo é dito completo quando cada par distinto de vértice é adjacente
Kn = grafo completo de ordem n, possui m arestas, onde:
k1 k2 k3 k4
!
( 2)!2!
n
m
n
 
=  
− 
Subgrafo
Um grafo Gs(Vs, As) é dito ser subgrafo de G(V, A) se Vs está contido em V e se As está contido em A.
Clique
É um subgrafo completo de um grafo.
Grafo complementar
O complemento ou inverso de um grafo G é um grafo H nos mesmos vértices tais que dois vértices 
de H são adjacentes se e somente se eles não são adjacentes em G. 
Isso é para encontrar o complemento de um grafo, você preenche todas as arestas que faltavam para
obter um grafo completo, e remove todas as arestas que já estavam lá.
Grafo bipartido
Um grafo é considerado bipartido quando seu
conjunto de vértices V puder ser particionado
em dois subconjuntos V1 e V2, tal que toda
aresta de G une um vértice de V1 a outro de
V2.
Grafo rotulado
Grafo em que cada vértice está associado a um rótulo.
SP (São Paulo) RN (Natal)
CE (Fortaleza) PA (Belém)
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.
SP (São Paulo) RN (Natal)
CE (Fortaleza) PA (Belém)
1850
1500
900
1900
2100
Caminho
É uma sequência de arestas onde o vértice final de uma aresta é o vértice inicial da próxima.
Um caminho de k vértices tem k-1 arestas: v1v2, v2v3,...,vk-1vk e o comprimento do caminho é k-1.
V1
V2 V3 V4
V5
C1
C2 C3
C4
C5
Ciclo e circuito
Grafo conexo
Existe um caminho entre quaisquer dois de seus vértices.
OBS: pense no que acontece quando o governo constrói mais uma rodovia, um túnel ou um viaduto.
B
E
A
C
D
F
F
F
F
F
F
F
F
Árvores
É um grafo conexo (existe caminho entre quaisquer dois de seus vértices) e acíclico (não possui ciclos).
1
3
2 4
5 6 7 8 9
Teorema
Seja T uma árvore com n vértices, então:
I. T é conexo e sem ciclos;
II. T é conexo e possui (n – 1) arestas;
III. Cada aresta é uma ponte.
Relembrando: Uma ponte é uma aresta cuja retirada desconecta o grafo.
F
F
F
F
F
F
Removendo a PONTE
Organograma
Presidente
VIP 
Produção
VIP 
Financeiro
VIP 
Pessoal
Gerência 
Produção
Engenharia
Gerência 
Estoque
Recursos 
Humanos
TreinamentoOficina
Projeto
Controladoria
Contabilidade
Árvore de Decisão
Caminho e Ciclo Euleriano
Um Caminho Euleriano é um caminho em um grafo que visita cada aresta apenas uma vez. Um Circuito
Euleriano é um caminho Euleriano que começa e termina no mesmo vértice. O conceito foi introduzido
por Leonard Euler para a resolução do famoso problema das sete pontes de Königsberg em 1736
Problema do Carteiro Chinês.
1
2
3
7
4
6 5
A K
D J
C I
E G
B H
F
Caminho e Ciclo Euleriano
Aplicação
Caminho e Ciclo Hamiltoniano
Um caminho hamiltoniano é um caminho que permite passar por todos os vértices de um grafo G, não
repetindo nenhum, ou, seja, passar por todos uma e uma só vez por cada. Caso esse caminho seja
possível descrever um ciclo, este é denominado ciclo hamiltoniano (ou circuito hamiltoniano) em G.
Um grafo que possua tal circuito é chamado de grafo hamiltoniano ➔ Problema do Caixeiro Viajante.
F F
F F
F F
F F
Caminho e Ciclo Hamiltoniano
II Guerra Mundial – bombardeio de cidades
Lista de Adjacência
Matriz de Adjacência
E
D
B
A
C
Matriz de Incidência
E CD
A
B
(Grafos orientados)
Grafos Isomorfos
Dois grafos G1(V1,E1) e G2(V2,E2) são ditos isomorfos entre si se existe uma correspondência entre os
seus vértices e arestas de tal maneira que a relação de incidência seja preservada. Em outros termos,
temos |V1|= |V2| e existe uma função unívoca f: V1->V2, tal que (i,j) é elemento de E1 se e somente se
(ƒ(i),f(j)) é elemento de E2.
ALGORITMOS
Sequência finita de regras, raciocínios ou operações que, aplicada a um número finito de dados, permite
solucionar classes semelhantes de problemas.
Exemplos:
a) Multiplicação
b) Radiciação
c) MMC
ALGORITMOS
Sequência finita de regras, raciocínios ou operações que, aplicada a um número finito de dados, permite
solucionar classes semelhantes de problemas.
Algoritmo Guloso:
Um algoritmo guloso é míope: ele toma decisões com base na melhor solução imediata ou local, sem
olhar as consequências que essas decisões terão no futuro.
A
D
E B
C
205 500
340
302 305
185 200
360165
320
HEURÍSTICAS
É um método ou processo criadocom o objetivo de encontrar soluções para um problema. É um
procedimento simplificador (embora não simplista) que, em face de questões difíceis, envolve a
substituição destas por outras de resolução mais fácil a fim de encontrar respostas viáveis, ainda que
“não ótimas”.
Mão na massa!
EXERCÍCIO 1
A partir do grafo abaixo, responda:
a. Qual é a ordem do grafo?
b. Gr(d) = ?
c. O grafo é conexo? Por quê?
d. É um grafo simples? Por quê?
e. Construa a Matriz de Adjacência do grafo.
f. O grafo possui alguma ponte? O que é uma ponte?
g. Existe algum vértice isolado?
A
E
B D
F
C
EXERCÍCIO 2
Calcule o número de arestas de um grafo K15.
!
( 2)!2!
n
m
n
 
=  
− 
EXERCÍCIO 3
No grafo abaixo, é possível identificar um Ciclo Hamiltoniano? Caso afirmativo,
destaque-o.
F F
F
FF
F
F F
F
FF
F
F F
F
FF
F F F
F
F F
F
FF
F
FF
F
EXERCÍCIO 4
Monte a matriz de adjacência do grafo a seguir.
5
2
6
4
1
3
EXERCÍCIO 5
Desenhe o grafo a partir da matriz de adjacência.
EXERCÍCIO 6
Construa a matriz de incidência do grafo a seguir:
43
1 2
EXERCÍCIO 7
Um vértice de um grafo, onde Gr(v) = 0, chamamos de:
a) Laço
b) Isolado
c) Paralelo
d) Adjacente
e) Pendente
EXERCÍCIO 8
Um vértice cujo Gr(v) = 1, chama-se:
a) Laço
b) Paralelo
c) Pendente
d) Incidente
e) Nulo
EXERCÍCIO 9
Dados dois vértices A e A’, um par de arestas a1 = (A, A’) e a2 = (A, A’) são
chamadas de:
a) laços.
b) isomorfas.
c) nulas.
d) pendentes.
e) paralelas.
Introdução à Teoria dos Grafos
marcosdossantos_doutorado_uff@yahoo.com.br
researchgate.net/profile/Marcos_Dos_Santos6
linkedin.com/in/marcos-santos-45909763