UNIPAR
Universidade Paranaense
Campus Sede Umuarama
Tópicos Especiais em
Tecnologia da Computação
(TETC)
GERSTING, Judith
Fundamentos Matemáticos para a Ciência da Computação
Editora LTC, 1995, São Paulo, Cap.5
Sistemas de Informação
4º SI
Grafos
Definição, Terminologia e
Conceitos Elementares
Professora Elaine Augusto Praça
Fevereiro/2008
O que é um grafo?
Um grafo é uma representação gráfica de
elementos de dados e das conexões entre
alguns destes itens.
 Uma árvore é um caso particular de grafo.
 Outros exemplos: interesse de
desempregados por vagas em empresas,
rotas de uma companhia aérea.

Qual a importância computacional
do uso dos grafos?
É bastante abrangente o uso de grafos na
computação em áreas como:
 Análise de planejamento de projetos
 Cibernética
 Redes de Computadores
 Circuitos Eletrônicos.

Qual a importância computacional?
Definição
Definição
Um grafo é uma tripla (N, A, g) em que:
N = um conjunto não vazio de vértices (nós
ou nodos)
A = um conjunto de arestas (arcos)
g = uma função que associa cada aresta a
a um par não-ordenado x-y de vértices
chamados extremos de a

Adjacência

Dois vértices são vértices adjacentes se
forem os extremos de uma mesma reta.
5
a2
a3
a1
1
2
a4
a5
3
a6
1e3
4
(a5)
Adjacência

Duas arestas que possuem um extremo
em comum são ditas arestas adjacentes.
5
a2
a3
a1
1
2
a4
a5
3
a6
A1 e a4
4
(2)
Laços

Um laço é uma
aresta com
extremos n-n para
algum nó n.
5
a3
a1
a4
a5
3
4
a1
1
2
a6
Um grafo que não
possui laços é
chamado grafo
sem laços. 5
a2
a2
1

2
a4
a3
(2-2)
a5
3
a6
4
Paralelismo

Duas arestas que tem os mesmos
extremos são ditas arestas paralelas.
5
a2
a3
a1
1
2
a4
a5
3
a6
A1 e a2
4
(1-2)
Grafo Simples

Vértice isolado
não é adjacente a
qualquer outro
vértice. 5
a2
a3
a1
1
2
5
4
a1
2
a4
a5
3
Um grafo
simples é um
grafo que não
tenha arestas
paralelas nem
laços.
5
1
a4
a6

a5
3
a6
4
Outros grafos

Diagramas com
arestas paralelas
e laços são
chamados de
pseudografos.

Diagramas com
arestas
paralelas são
chamados de
multigrafos.
Tipos de Grafos
Grafo
Multigrafo
Pseudografo
Tipos de Grafos

Grafos simples e multigrafos são pseudografos,
Grafo

Multigrafo
Pseudografo
Um vértice isolado não é adjacente a qualquer
outro vértice.
Grau


O grau de um vértice é número de arestas que
o tem como ponto extremo.
Como a função g relaciona cada aresta a seus
extremos, cada aresta tem um único par de
5
pontos extremos.
a2
a3
Vértice 1: grau 3
Vértice 5: grau 0
Vértice 2: grau 5
a1
1
2
a4
a5
g(a1)= 1-2; g(a6)= 3-4; g(a3)= 2-2
3
a6
4
Grafos completos
Um grafo completo é aquele no qual
todos os vértices distintos dois a dois são
adjacentes.
 Kn é um grafo completo com n vértices.
Exemplo: K4

Grafos Completos
 Exemplos
K2
Kn (grafos completos)
K3
K4
K5
a2
a3
Subgrafo

Um subgrafo de um
grafo consiste em um
conjunto de vértices e
um conjunto de
arestas que são
subconjuntos de
vértices e arestas
originais, nos quais os
extremos de qualquer
aresta são os mesmos
que no grafo original.
a1
1
2
a4
5
a5
a6
3
4
a1
1
2
a5
a4
4
3
a3
a4
3
2
a6
5
2
Grafos e subgrafos
1
4

G1, G2, G3, G4 e G5 são subgrafos
de G com os vértices V={1,2,3,4}.
1
1
4
4
3
3
G1
G2
2
G3
4
4
4
3
2
1
1
1
G
2
2
2
3
3
3
G4
G5
Grafos e subgrafos

O grafo G1 se destaca dos demais pois este
possui todas as arestas que estão no grafo
G. O grafo G1 é chamado de sub-grafo
induzido pelo conjunto de vértices {1,2,3,4}.
2
2
1
4
5
1
4
3
3
G
G1
Grafos e subgrafos
H e J são subgrafos induzidos de G
sobre os conjuntos Vh={1,3,4,5,6} e
Vj={6,1,5}.
Q não é um subgrafo induzido por
V={1,3,4,5,6} pois a aresta 1-4 não
faz parte do subgrafo.


6
6
5
4
1
2
3
G
5
6
4
1
1
6
J
5
5
4
1
3
H
3
Q
Grafos e subgrafos


Definições: 1- Dado um grafo G=(V, a) dizemos
que o grafo G1=(V1,a1) é um subgrafo de G se
V1 é um subconjunto de V (podendo ser igual a
V) e as arestas de a1 são um subconjunto das
arestas a.
2- Dizemos que G1 é um subgrafo induzido por
V1 se todas as arestas V1V2 de a tais que V1 e
V2 pertencem a V1 então V1V2 também
pertence a a1.
Desconectando um grafo

O grafo Q foi obtido do grafo P
removendo-se o vértice 4 e suas arestas
incidentes. P é conexo e Q é desconexo
com duas componentes conexas e 4 é o
vértice de corte.
2
2
6
6
3
3
1
4
P
5
5
1
7
Q
7
Desconectando um grafo

O grafo N foi obtido de M removendo-se a
aresta 3-4. O grafo M é conexo e N é
desconexo. A aresta 3-4 é chamada de
aresta de corte ou ponte.
2
6
3
1
2
3
4
M
6
5
1
4
N
5
Desconectando um grafo

Muitas vezes, para se desconectar um
grafo é necessário remover um ou mais
vértices ou arestas e um conjunto mínimo
de vértices que desconecta um grafo é
chamado de vértices de corte.

De modo análogo, temos arestas de corte.
Desconectando um grafo

Nas figuras abaixo as arestas {4-7,5-6} são
arestas de corte e este conjunto é mínimo
pois removendo-se apenas uma das arestas
o grafo não desconecta.
3
3
8
4
2
8
7
1
5
4
2
1
6
5
7
6
Desconectando um grafo

As arestas {4-7,5-6,6-7} também
desconectam o grafo, mas elas não são
consideradas arestas de corte, pois este
não é um subconjunto mínimo de corte, já
que existe o subconjunto {4-7, 5-6} contido
em {4-7, 5-6, 6-7} que desconecta o grafo.
3
4
2
3
8
2
7
1
5
8
4
7
6
1
5
6
Caminho

Um caminho é uma seqüência de vértices e
arestas, onde para cada i, os extremos da
aresta ai são ni-ni+1.
Alguns Caminhos
possíveis vértices 2-4=
a2
a3
2, a1, 1, a2, 2, a4, 3, a6, 4
a1
1
2
a4
a5
3
a6
5
Ou
2, a4, 3, a6, 4
4
Ou...
Comprimento
a2

O comprimento
de um caminho é o
número de arestas
que ele contém.
a3
a1
1
2
a4
a5
3
a6
4
Caminhos \ comprimento
2, a1, 1, a2, 2, a4, 3, a6, 4 ►comprimento 4
2, a4, 3, a6, 4 ►comprimento 2
5
Conexão

Um grafo é conexo se houver um caminho
entre quaisquer dois vértices.
a2
a1
1
a2
a3
2
a4
a5
a3
a1
1
2
a4
5
a5
3
a6
4
Não conexo
(vértice 5 isolado)
3
Conexo (caminhos
entre 2 vértices)
Ciclos


Um ciclo é um caminho de algum vértice n até
n de novo de forma que nenhum vértice ocorra
mais de uma vez no caminho.
Um grafo sem ciclos é dito grafo acíclico.
a2
a3
a1
1
2
a4
5
a5
3
a6
4
Ciclo: 1, a1, 2, a4, 3, a5, 1
5
4
Complemento

Denomina-se
complemento de um
grafo G(V,E) ao grafo G,
o qual possui o mesmo
conjunto de vértices do
que G tal que para todo
par de vértices distintos
v, w de V, tem-se que
(v,w) é aresta de G se e
somente se não o for de
G.
6
3
2
1
5
4
6
3
1
2
Grafos Regulares e Completos
Um grafo é dito regular se todos os seus
vértices possuem o mesmo grau.
 Um grafo é dito completo se existe uma
aresta ligando todos os pares de vértices.
 Exemplos de grafos regulares:

Grafos Regulares

Um grafo cujos vértices têm o mesmo
grau é chamado de grafo regular.
Grau 1
Grau 2
Grau 3
Grau 4
Grafos Regulares e Completos

Dado um grafo kn (grafo completo com n
vértices), este possui o número máximo
de arestas.

Cada vértice tem grau n-1, logo todo grafo
completo é necessariamente regular.
PRÁTICA 1 (219)
Trace um grafo que tenha:
 os vértices {1,2,3,4,5},
 as arestas {a1, a2, a3, a4, a5, a6}
 e a função
g(a1)= 1-2,
g(a2)= 1-3,
g(a3)= 3-4,
g(a4)= 3-4,
g(a5)= 4-5,
g(a6)= 5-5.

PRÁTICA 2 (219)



Encontre:
a - dois vértices que não sejam adjacentes;
b - um vértice que seja adjacente a ele mesmo;
c - um laço;
d - duas arestas paralelas;
e - o grau do vértice 3;
f - um caminho de comprimento 5;
g - um ciclo;
h - o complemento deste grafo.
Este grafo é completo?
Este grafo é conexo?
Grafos Isomorfos 07-06
paramos aqui
B
e1
C
a1
a2
A
1
D
e2
3
C
B
a2
A
a1
4
f1:
f2:
1→a
a1→e2
2 →b
a2 →e1
3 →c
D
2
4 →d
Grafos Isomorfos

Dois grafos podem parecer muito diferentes
em suas representações gráficas, mas
serem, ainda assim, o mesmo grafo de
acordo com nossa definição de grafo.

Os grafos apresentados anteriormente são
os mesmos, pois tem os mesmos vértices, as
mesmas arestas e a mesma função de
associação de arestas e seus extremos.
Grafos Isomorfos

Para mostrar que dois grafos são
isomorfos é preciso produzir novos
rótulos (por meio de uma função injetiva e
sobrejetiva) e então mostrar que a lista de
quais arestas conectam quais vértices é
preservada.
Grafos Isomorfos
Dados G1={V1, a1} e G2={V2, a2}:
V1={A, B,C,D}
a1={AC, CD, DA, AB, CB, DB}
V2 = {A1,A2,A3,A4}
a2 = {A1A2,A2A3,A3A4,A1A4,A2A4,A3A1}


Ambos possuem 4 vértices e 6 arestas.
Desenhe G1 e G2
Grafos Isomorfos


Se trocamos no gráfico G1:
A  A1 D  A3 C  A2 B  A4
Cada aresta de G1 será transformada em uma
aresta de G2
AC  A1A2
DA  A3A1
CD  A2A3
CB  A2A4
AB  A1A4
DB  A3A4
A1
B
C
A
D
G1
A3
A4
A2
G2
Grafos Isomorfos

Dados dois gráficos G1=(V1, a1) e G2=(V2, a2)
são ditos isomorfos se existe uma função 1-1
f: V1  V2
de modo que dois vértices quaisquer de V1,
A e B são adjacentes se e somente se f(A) e
f(B) são vértices adjacentes em V2.
Grafos Isomorfos

A função f(Ui)=Vi, i=1, 2...,6, faz
corresponder a cada aresta de G1 uma
aresta de G2 e reciprocamente.
U1
U6
U2
V1
V2
V6
V5
U3
U5
V3
V4
U4
Condições que garantem que dois
grafos não são isomorfos







Um grafo tem mais vértices que o outro;
Um grafo tem mais arestas que o outro;
Um grafo tem arestas paralelas e outro não;
Um grafo tem um laço e o outro não;
Um grafo tem um vértice de grau k e o outro
não;
Um grafo é conexo e o outro não;
Um grafo tem um ciclo e o outro não.
Grafos Isomorfos
PRÁTICA 6 (222): Os grafos abaixo são
isomorfos?
(a)
(b)
Grafos Isomorfos
EXEMPLO 5
(222): Os grafos
(a) e (b) são
isomorfos?
(a)
(b)
Verifique o grau de cada aresta, quantidade
de vértices e arestas, adjacência entre os
vértices ...
Grafos Isomorfos
Os dois grafos apresentados anteriormente
não são isomorfos. Ambos tem 6 vértices e 7
arestas, não tem arestas paralelas nem
laços, são conexos, tem 3 ciclos e 4 vértices
de grau 2 e 2 vértices de grau 3.
 No entanto, o grafo (b) tem um vértice de
grau 2 que é adjacente a dois vértices de
grau 3, o que não ocorre no grafo (a),
portanto os grafos não são isomorfos.

Grafos Isomorfos

Grafos isomorfos
podem ter
representações
gráficas diferentes
mas são
essencialmente o
mesmo grafo.
Portanto, na teoria
dos grafos, quaisquer
dois grafos isomorfos
são considerados um
mesmo grafo.
PRÁTICA 5 (221): Os
grafos (a) e (b) são
isomorfos? Se forem,
descreva as bijeções.
a
1
b
5
4
c
f
3
2
6
(a)
d
e
(b)
Grafos Isomorfos
1
5
4
PRÁTICA 5 (221):
(a)
1→d
2 →e
6
3 →f
4 →c
5 →b
3
2
a
b
c
(b)
6 →a
f
d
e
8
Grafos Homeomorfos

Serão quando ambos
puderem ser obtidos do
mesmo grafo por uma
seqüência de subdivisões
elementares, nas quais
uma única aresta x-y é
substituída por duas
novas arestas x-v e v-y,
conectando-se em um
novo vértice v.
7
6
8
9
7
5
6
9
8
7
5
6
Grafos Bipartidos Completos
Seus vértices podem ser particionados em
dois conjuntos não-vazios N1 e N2, tais que
dois vértices x e y sejam adjacentes se, e
somente se, x Є N1, e y Є N2.
 Se |N1| = m e |N2|= n, então este grafo é Km,n

1
3
N1 = {1,2}
 N2 = {3,4,5}
 K2,3

2
4
5
Grafos Bipartidos Completos

Desenhe K3,3
Grafos bipartidos

Se podemos repartir os vértices de um grafo
em dois subconjuntos V1 e V2 de modo que
todas as arestas do grafo ligam um vértice de
V1 com um vértice de V2, chamamos este
grafo de grafo bipartido ou bipartite.
2
1
V1= {1,2}
V2= {3,4,5,6,7}
3
4
5
6
7
Grafos bipartidos completos

O grafo abaixo é também bipartite e além
disso todos os vértices de V1 estão ligados
com todos os vértices de V2. Este tipo de
grafo é chamado de bipartido (ou bipartite)
completo.
2
1
3
4
5
V1= {1,2}
6
7
V2= {3,4,5,6,7}
Grafos Bipartidos Completos
1
3
N1 = {1,2}
 N2 = {3,4,5}
 K2,3

2
4
5
Grafos Bipartidos Completos
Existe algum processo eficiente para se
reconhecer grafos bipartidos?
 Teorema:
Um grafo G(V,E) é bipartido se e somente
se todo ciclo de G possuir comprimento
par.

Grafos Bipartidos Completos

Prova:
Seja v1, ..., vk um ciclo de comprimento K
do grafo bipartido G e seja v1 um vértice
de V1. Logo, v2 pertence a V2, v3 pertence
a V1, v4 pertence a V2, e assim por diante.
Como (vk,v1) pertence a E, vK pertence a
V2.
Exercício
O grafo abaixo é um grafo bipartite?
 Se sim, ele é um grafo bipartite completo?
 Qual uma outra forma de se desenhar este
grafo?

6
5
1
4
2
3
Grafos Planares (planaridade)

É um grafo que pode ser desenhado em um
plano (folha de papel) e forma que suas
arestas se interceptem apenas em vértices.

PRÁTICA 9 (223): Demonstre planaridade em
K4
Grafos Planares (planaridade)

Planaridade em K5
1
1
2
5
4
1
3
2
5
2
5
4
4
3
3
PRÁTICA 10 (224): Mostre que se colocássemos
As arestas 1-3 e 1-4 como exteriores ao
construir K5, seríamos levados, novamente a
uma situação de interceptação das arestas.
Fórmula de Euler paramos 2705

Um grafo simples, conexo e planar (sem
intersecção de arestas, divide o plano em um
número de regiões, incluindo as regiões
totalmente fechadas e uma região infinita
exterior. Euler observou a relação entre o
número n de vértices, o número a de arestas
e o número r de regiões neste tipo de grafos,
sendo como:
n-a+r=2
n-a+r=2
Fórmula de Euler

PRÁTICA 11 (224): Verifique a fórmula de
Euler para o grafo conexo abaixo:
a
b
c
f
d
e
Ordem, Tamanho e Distância
Dado um grafo G=(V,a), o número de
vértices de G é chamado de ordem de G e é
denotado por |V|.
 O número de arestas de um grafo é
chamado de tamanho do grafo e é denotado
por |a|.
 A distância entre dois vértices V1 e V2 de G
é o comprimento do menor caminho entre
V1 e V2.

Ordem, Tamanho e Distância
A
G=(V,a)
V={A,B,C,D,E,F}
Ordem de G
Tamanho de G
Distância
Distância
F
|V|=6
|a|=9
d(B,E)=1
d(B,D)=2
B
C
E
D
1º Teorema da Teoria dos Grafos


“Dado um grafo G então a
soma dos graus de seus
vértices é igual ao dobro
do número de arestas.”
Este resultado é claro pois,
ao contarmos o número de
arestas de cada vértice
estamos contando cada
aresta duas vezes.
V3
V4
V2
V1
1º Teorema da Teoria dos Grafos

Este teorema pode ser traduzido numa
fórmula. Sejam V1, V2, ...,Vn os vértices,
grau(V1) o grau do vérticeV1 e |a| o tamanho
do grafo, então:
grau(V1)+grau(V2)+...+grau(Vn) = 2 |a|
1+3+2+2 = 2*4
V3
V4
V2
V1
8=8
1º Teorema da Teoria dos Grafos

É possível construir um grafo com 3 vértices
ímpares e outros pares?
Não, pois se existe tal gráfico então a soma
dos graus dos vértices ímpares será ímpar e a
soma dos graus dos vértices pares será um
número par. Logo a soma total dos graus será
um número ímpar somado a um número par
que é ímpar. Isto contraria o 1º Teorema.
Logo tal grafo não existe.
Caminhos e Ciclos Eulerianos

Um caminho é dito euleriano se este
passa uma única vez em cada aresta de
um grafo.

Um ciclo que percorre todas as arestas de
um grafo uma única vez é chamado de
ciclo euleriano em homenagem a Euler.
Caminhos e Ciclo Eulerianos

Dado o grafo abaixo, o caminho 123413 é
um caminho euleriano, porém não é um
ciclo euleriano, já que os vértices de início
e fim do caminho não coincidem.
1
2
4
3
Caminhos e Ciclos Eulerianos
4
1
3
2

Não existem caminhos eulerianos
para o multigrafo acima.
Caminhos e Ciclos Eulerianos


Suponhamos, por absurdo, que existe um caminho C
euleriano. Neste caso, existem pelo menos dois
vértices X e Y que não são nem início nem fim do
caminho C. Cada vértice tem grau 3. Logo, quando C
entra em X este deve sair por uma aresta diferente
restando, portanto, uma aresta incidente a ser
percorrida.
Quando esta aresta for percorrida, ela deve entrar em
X e não pode mais sair. Isto só pode ocorrer se X for
um ponto final, mas X foi escolhido como não final.
Isto é uma contradição.
Logo, este caminho euleriano não existe.
Caminhos e Ciclos Eulerianos
Teorema: “Um grafo G conexo possui um
ciclo euleriano se e somente se todo
vértice de G possui grau par.”
 Este teorema é nos dois sentidos:

 Se
o grafo possui ciclo euleriano então o grau
dos vértices é par.
 Se o grau dos vértices é par então o grafo
possui ciclo euleriano.
Caminhos e Ciclo Eulerianos
O grafo abaixo possui pelo menos um
vértice de grau 3, logo não possui um ciclo
euleriano.
 Isto não o impede de possuir um caminho
euleriano que não seja um ciclo.

1
2
4
3