Universidade Federal de Pernambuco
Anjolina Grisi de Oliveira
Obs: Muitos slides foram cedidos por
Adolfo Almeida Duran (UFBA)
Introdução
• Porque estudar Grafos
– Importante ferramenta matemática com aplicação
em diversas áreas do conhecimento
• Genética, química, pesquisa operacional,
telecomunicações, engenharia elétrica, redes de
computadores, conexão de vôos aéreos, restrições de
precedência, fluxo de programas, dentre outros
– Utilizados na definição e/ou resolução de
problemas
Grafos / Matemática Discreta/ Cin / UFPE
2
• Porque estudar Grafos
– Em computação: estudar grafos é mais uma
forma de solucionar problemas computáveis
– Os estudos teóricos em grafos buscam o
desenvolvimento de algoritmos mais eficientes.
Grafos / Matemática Discreta/ Cin / UFPE
3
• O que são Grafos
• Tipicamente um grafo é representado como um conjunto
não vazio de pontos ou vértices ligados por retas, que são
chamadas de arestas
• Ferramenta de modelagem
• Abstração matemática que representa situações reais
através de um diagrama.
Grafos / Matemática Discreta/ Cin / UFPE
4
As pontes de Königsberg
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.
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 que possibilitasse tais restrições.
Grafos / Matemática Discreta/ Cin / UFPE
5
• As pontes de Königsberg
– Resolvido em 1736 por Leonhard Euler
– Necessário um modelo para representar o
problema
– Abstração de detalhes irrelevantes:
• Área de cada ilha
• Formato de cada ilha
• Tipo da ponte, etc.
Grafos / Matemática Discreta/ Cin / UFPE
6
• As pontes de Königsberg
– Euler generalizou o problema através de um
modelo de grafos
Grafos / Matemática Discreta/ Cin / UFPE
7
• As pontes de Königsberg
– Euler mostrou que não existe o trajeto proposto
utilizando o modelo em grafos
• Verifique nos grafos abaixo se o trajeto proposto é possível
Grafos / Matemática Discreta/ Cin / UFPE
8
• O problema das 3 casas
– É possível conectar os 3 serviços às 3 casas sem
haver cruzamento de tubulação?
água
Grafos / Matemática Discreta/ Cin / UFPE
luz
telefone
A teoria
dos
grafos
mostra
que não
é
possível
9
Quantas
cores são
necessárias
para colorir o
mapa do
Brasil, sendo
que estados
adjacentes
não podem
ter a mesma
cor?
Grafos / Matemática Discreta/ Cin / UFPE
10
Questões sobre o caminho 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.
Grafos / Matemática Discreta/ Cin / UFPE
11
Grafos / Matemática Discreta/ Cin / UFPE
12
• Modelagem com grafos
–Estamos interessados em objetos e nas relações entre
eles
–Quem são eles nos problemas apresentados?
–Como representar graficamente?
Grafos / Matemática Discreta/ Cin / UFPE
13
• Modelagem com grafos
– No problema das casas
• Vértices são casas e serviços
• Arestas são as tubulações entre casas e serviços
– No problema da coloração de mapas
• Vértices são estados
• Arestas relacionam estados vizinhos
– No problema do caminho mais curto
• Vértices são as cidades
• Arestas são as ligações entre as cidades
Grafos / Matemática Discreta/ Cin / UFPE
14
•Três desenvolvimentos isolados despertaram
o interesse pela área
1) Formulação do problema das 4 cores (De
Morgan 1852).
Qual a quantidade mínima de cores para colorir um
mapa de tal forma que países fronteiriços possuam
cores diferentes?
Apresenta-se um exemplo em que 3 cores não são
suficientes. Uma prova de que 5 cores é suficiente foi
formulada. Conjecturou-se então que 4 cores seriam
suficientes. Esta questão ficou em aberto até 1976
quando Appel e Haken provaram para 4 cores
Grafos / Matemática Discreta/ Cin / UFPE
15
• Três desenvolvimentos isolados despertaram o interesse
pela área
2) Problema do ciclo Hamiltoniano (Hamilton 1859)
Existem n cidades. Cada par de cidades pode ser
adjacente ou não arbitrariamente. Partindo de uma
cidade qualquer, o problema consiste em determinar um
trajeto que passe exatamente uma vez em cada cidade
e retorne ao ponto de partida.
Grafos / Matemática Discreta/ Cin / UFPE
16
• Três desenvolvimentos isolados despertaram o interesse
pela área
3) Teoria das árvores
- Kirchoff (1847) - problemas de circuitos elétricos
- Cayley (1857) - Química Orgânica
H
H
H
C
C
H
H
Grafos / Matemática Discreta/ Cin / UFPE
O
H
17
Definições
• Dois tipos de elementos
– Vértices ou nós
– Arestas
v1
v3
v4
v5
Grafos / Matemática Discreta/ Cin / UFPE
v2
v6
18
Grafo Simples
• G = (V,E)
– V é um conjunto finito não-vazio de vértices (ou nós)
– E é um conjunto de pares não ordenados de elementos
distintos de V, chamados de arestas
– Cada aresta e pertencente ao conjunto E será denotada pelo
par de vértices {x,y} que a forma
– Dizemos que os vértices x e y são extremos (ou
extremidades) da aresta e.
Grafos / Matemática Discreta/ Cin / UFPE
19
Dois vértices x e y são ditos adjacentes ou vizinhos se
existe uma aresta e unindo-os.
Os vértices u e v são ditos incidentes na aresta e, se
eles são extremos de e.
Duas arestas são adjacentes se elas têm ao menos um
vértice em comum.
A aresta e={x,y} é incidente a ambos os vértices x e y.
Grafos / Matemática Discreta/ Cin / UFPE
20
Grafo simples
v1
v3
v4
v2
V = {v1, v2, v3, v4, v5, v6}
e1
v5
v6
E = {{v1,v2},{v1,v3},{v1,v4},{v2,v4},{v3,v4},{v4,v5}}
e1 é incidente a v4 e v5
Grafos / Matemática Discreta/ Cin / UFPE
21
Exercício
Desenhe a representação geométrica do seguinte
grafo simples:
V = {1,2,3,4,5,6};
E ={{1,2},{1,3},{3,2},{3,6},{5,3},{5,1},{5,6},{4,6},
{4,5},{6,1},{6,2},{3,4}}
Grafos / Matemática Discreta/ Cin / UFPE
22
Mais definições
• Multigrafo G=(V,E)
– Função f de E em {{u,v } | u,v V,u  v }
– As arestas e1 e e2 são chamadas de arestas múltiplas ou
paralelas se f(e1) = f(e2)
• Laço
– É uma aresta formada por um par de vértices idênticos.
• Pseudografo G=(V,E)
– Função f de E em {{u,v } | u,v V}
– Permitem laços: f(e) = {u,u}={u}
Grafos / Matemática Discreta/ Cin / UFPE
23
Exercício
Defina formalmente o grafo abaixo e identifique os
conceitos de laço, aresta múltipla e multigrafo no
mesmo:
Grafos / Matemática Discreta/ Cin / UFPE
24
G=(V,E) V = {1,2,3,4,5} e E={e1,e2,e3,e4,e5,e6,e7,e8,e9,e10}
f: E → P(V);
f(e1) ={2,3}; f(e2)={1,2}; f(e3)={1}, f(e4)={1,3), f(e5)={1,2},
f(e6)={1}, f(e7)={1,3}, f(e8)={2,3}, f(e9)={4,3}, f(e10)={3}
e1
LOOPS:
e2
Qdo a imagem de e
tiver cardinalidade
1
e5
e3
e8
e4
e6
e7
Arestas múltiplas
f(ei) = f(ej)
Grafos / Matemática Discreta/ Cin / UFPE
e9
e10
25
Grau de um vértice
Grau de um vértice v (grau(v))é o número de arestas
que incidem em v.
O grau de um vértice v também pode ser definido
como o número de arestas adjacentes a v.
Obs.: Um laço conta duas vezes para o grau de um
vértice
Grau(b) = 3
Grau(d) = 2
Grau(a) = 2
Grafos / Matemática Discreta/ Cin / UFPE
26
– Qualquer vértice de grau zero é um
vértice isolado
– Qualquer vértice de grau 1 é um
vértice pendente
– Um vértice ímpar tem um número ímpar de arestas
– Um vértice par, tem um número par de arestas
Grafos / Matemática Discreta/ Cin / UFPE
27
Grafo Regular (k-regular)
– todos os vértices têm o mesmo grau (k)
v1
v2
Grafos / Matemática Discreta/ Cin / UFPE
v4
v3
28
V6 é um vértice isolado,
grau(v6)=0
v1
v3
v4
v2
V5 é um vértice pendente,
grau(v5)=1
e1
v5
v6
V2 é um vértice par,
grau(v2)=2
V1 é um vértice ímpar,
grau(v1)=3
Grafos / Matemática Discreta/ Cin / UFPE
29
Exercício
Identificar no grafo abaixo os vértices isolados,
pendentes, ímpares e pares.
Reflexão
O que podemos concluir sobre a soma dos graus de
um grafo?
Grafos / Matemática Discreta/ Cin / UFPE
30
Soma dos graus de um grafo:
O resultado é sempre par, e corresponde à formula
abaixo:
A prova é inspirada no Teorema do Aperto de Mãos que
diz:
Se várias pessoas se apertam a mão o número total de
mãos apertadas tem que ser par. Precisamente porque
duas mãos estão envolvidas em cada aperto.
Grafos / Matemática Discreta/ Cin / UFPE
31
Soma dos graus de um grafo:
Em grafos, cada aresta contribui duas unidades para o
cômputo geral do grau dos vértices, pois cada aresta
possui dois extremos. Portanto, a soma total é par e
duas vezes o número de arestas do grafo.
Se o grafo for regular de grau r, a soma dos graus dos
vértices também é igual a r vezes o número de vértices
Grafos / Matemática Discreta/ Cin / UFPE
32
A soma dos graus de um grafo é sempre par:
Quando o grafo é regular de grau r, temos:
Grafos / Matemática Discreta/ Cin / UFPE
33
Corolário
Em qualquer grafo, o no de vértices com grau ímpar deve
ser PAR
Prova
Para a soma ser par, o primeiro somatório tem que gerar
um resultado par, portanto |Vímpar| é par.
Grafos / Matemática Discreta/ Cin / UFPE
34
Exercícios
Existe um grafo simples com 5 vértices cujos graus são
dados a seguir? Em caso afirmativo, desenhe o grafo.
a) 3,3,3,3,2
3
2
3
3
3
b) 1,2,3,4,5
c) 1,1,1,1,1
Grafos / Matemática Discreta/ Cin / UFPE
35
Outros tipos de grafos
Grafo Nulo (vazio)
Grafo cujo número de arestas é zero. Ou, grafo regular
de grau zero.
Nn é um grafo nulo com n vértices
1
3
Exemplo: N4
V={1,2,3,4}; E={ }.
Grafos / Matemática Discreta/ Cin / UFPE
2
4
36
Grafo Completo
Grafo simples em que existe exatamente uma aresta
entre cada par de vértices distintos. Ou, grafo regular
de grau n-1, onde n=|V|.
Kn é um grafo completo com n vértices.
Exemplo: K4
Grafos / Matemática Discreta/ Cin / UFPE
37
Quantas arestas tem o Kn?
Veja que |E| = ( r * |v| ) / 2, onde r é o grau e v o número de
vértices.
Logo |E| = (( n - 1 ) n ) / 2
Grafos / Matemática Discreta/ Cin / UFPE
38
Complemento de um grafo
Seja G um grafo simples com um conjunto de vértices
V.
G´ é complemento de G se
V´ = V
e
dois vértices são adjacentes em G´, se e
somente se, não o são em G
Grafos / Matemática Discreta/ Cin / UFPE
39
Complemento de um grafo
Grafos / Matemática Discreta/ Cin / UFPE
40
Complemento de um grafo
Propriedade 1
Um grafo regular tem complemento regular
Propriedade 2
O complemento de Kn é Nn
Exercício:
Dê exemplos que confirmem as propriedades
acima
Grafos / Matemática Discreta/ Cin / UFPE
41
Outros tipos de grafos
Grafo cíclico (ou simplesmente Ciclo)
Um grafo conectado que é regular de grau 2 é
um grafo cíclico (= ciclo)
Cn é um grafo cíclico com n vértices
C6
Grafos / Matemática Discreta/ Cin / UFPE
42
Grafo roda
O grafo obtido a partir de Cn através da
ligação de cada vértice a um novo vértice v é
um grafo roda.
C5
Grafos / Matemática Discreta/ Cin / UFPE
W5
43
Grafos n-cúbicos
Os grafos n-cúbicos, denotados por Qn, são
grafos cujos vértices representam as 2n
cadeias de bits de tamanho n.
Dois vértices são adjacentes se e somente se
as cadeias de bits que eles representam
diferem em exatamente uma posição de bit.
Grafos / Matemática Discreta/ Cin / UFPE
44
Grafos n-cúbicos
110
111
101
100
010
000
Grafos / Matemática Discreta/ Cin / UFPE
011
001
45
Grafos Orientados ou Dígrafos
Um dígrafo G(V,A) é um conjunto finito não vazio V de
vértices, e um conjunto A de pares ordenados de
elementos de V. Chamamos o conjunto A de arcos
(também podemos chamar de arestas).
Multigrafo Orientado G(V,A)
Consiste de um conjunto V não vazio de vértices, um
conj. A de arestas e uma função f de A em {(u,v) | u,vV}.
As arestas e1 e e2 são múltiplas se f(e1) = f(e2).
Grafos / Matemática Discreta/ Cin / UFPE
46
• Os vértices de um dígrafo possuem:
– Grau de entrada: número de arcos que chegam no vértice
(grauent(v))
– Grau de saída: número de arcos que partem do vértice
(grausai(v))
Proposição
 grauent(vi) =  grausai(vi) = | A |
Grafos / Matemática Discreta/ Cin / UFPE
47
Revisando
Tipo
Arestas Múltiplas?
Laços?
------------------------------------------------------------------Simples
não dir. Não
Não
Multigrafo
não dir. Sim
Não
Pseudografo
não dir, Sim
Sim
Direcionado
dir.
Não
Sim
Multigrafo dir.
dir.
Sim
Sim
Grafos / Matemática Discreta/ Cin / UFPE
48
Exemplos
1. Quantos nós possui um grafo regular de grau 4
com 10 arestas?
Pelo teorema do aperto de mão: 2.|E|= r.|V|.
Logo, 2.10 = 4.|V|, assim |V| = 5.
Forma alternativa de responder:
O grafo regular de grau 4 é o K5,
logo a resposta é 5.
Grafos / Matemática Discreta/ Cin / UFPE
49
Exemplos
2. Se G é um grafo simples com 15 arestas e G´
possui 13 arestas, quantos nós G possui?
A união de G e G´ é um grafo completo.
Assim, basta responder qual a quantidade de nós de
um grafo completo com 28 arestas.
Resolvemos o sistema 2.28 = n.(n-1), achamos
n = 8 (a solução positiva).
Resposta: 8.
Grafos / Matemática Discreta/ Cin / UFPE
50
Grafo Bipartido
Um grafo é dito ser bipartido quando seu conjunto
de vértices V puder ser particionado em dois
subconjuntos V1 e V2, tais que toda aresta de G une
um vértice de V1 a outro de V2.
5
1
V1
3
2
Grafos / Matemática Discreta/ Cin / UFPE
4
6
V2
51
Grafo Bipartido
Sejam os conjuntos H={h | h é um homem} e M={m |
m é um mulher} e o grafo G(V,E) onde:
V=HUM
E = {{v,w} | (v  H e w  M) e <v foi namorado de
w>}
Grafos / Matemática Discreta/ Cin / UFPE
52
• Determine se os seguintes grafos são bipartidos
• G: V1={1.. V2={2.. e 6? Não é bipartido
• G-{3,5} e G+{1,4} : Não são bipartidos pelo mesmo motivo
Grafos / Matemática Discreta/ Cin / UFPE
53
Grafo bipartido?
v1
v2
v4
v3
V1= {v1,v4} e V2={v2,v3}
É bipartido.
Grafos / Matemática Discreta/ Cin / UFPE
54
Determine se os seguintes grafos são bipartidos
G: V1={a, V2={b, e f? Não é bipartido
G´: por causa das ligações entre e,c e a Não é bipartido
Grafos / Matemática Discreta/ Cin / UFPE
55
Exemplos
1. Para que valores de n os seguintes grafos são
bipartidos?
a) Kn
Para n=2
b) Cn
Para n par e maior que 2
Grafos / Matemática Discreta/ Cin / UFPE
56
Grafo Bipartido Completo – Km,n
É um grafo bipartido em V1 e V2, sendo que cada
elemento de V1 é adjacente a cada elemento de V2.
|V1| = m e |V2|=n
V1
V2
K3,3
Grafos / Matemática Discreta/ Cin / UFPE
57
Subgrafo
Um grafo Gs(Vs, As) é dito ser subgrafo de um grafo
G(V,A) quando Vs  V e As  A. O grafo G2, por
exemplo, é subgrafo de G1
G1
Grafos / Matemática Discreta/ Cin / UFPE
G2
58
Subgrafo Próprio
Um subgrafo G2 é dito próprio, quando G2 é
subgrafo distinto de G1
Subgrafos podem ser obtidos através da
remoção de arestas e vértices.
Grafos / Matemática Discreta/ Cin / UFPE
59
Subgrafo Induzido
Se G2 é um subgrafo de G1 e possui toda a aresta (v, w)
de G1 tal que ambos, v e w, estejam em V2, então G2 é o
subgrafo induzido pelo subconjunto de vértices V2.
3
G1
3
2
G2
1
5
4
V1= {1,2,3,4,5}
2
1
4
V2= {1,2,3,4}
V2 induz G2
Grafos / Matemática Discreta/ Cin / UFPE
60
Clique
Denomina-se clique de um grafo G a um subgrafo
(induzido) de G que seja completo
Grafos / Matemática Discreta/ Cin / UFPE
61
Exemplos
1. Qual é o grafo complementar de Km,n?
A união disjunta de Km com Kn
2. Para que valores de m e n o grafo Km,n é regular?
Para m=n e maior que zero
Grafos / Matemática Discreta/ Cin / UFPE
62