capitulo-06 (2)

Prévia do material em texto

Algoritmos e Estruturas 
de Dados
Introdução à Teoria de Grafos
Desenvolvimento do material
Miguel Carvalho
1ª Edição
Copyright © 2022, Afya.
Nenhuma parte deste material poderá ser reproduzida, 
transmitida e gravada, por qualquer meio eletrônico, 
mecânico, por fotocópia e outros, sem a prévia 
autorização, por escrito, da Afya.
Sumário
Introdução à Teoria de Grafos
Para Início de Conversa... ............................................................................... 3
Objetivos .................................................................................................... 3
1. Teoria de Grafos ............................................................................................ 4
2. Conceitos, Definições e Notações 
Básicas de Grafos ........................................................................................ 4
3. Grafos Orientados ........................................................................................ 11
Referências .................................................................................................... 12
Para Início de Conversa...
O estudo sobre a Teoria de Grafos é muito importante para o profissional 
de computação, pois existem centenas de soluções computacionais 
que utilizam esses conceitos, sendo aplicadas em vários ramos da 
computação, como banco de dados, análises de redes e inteligência 
artificial. 
Vamos descrever os conceitos da Teoria de Grafos, sob o enfoque 
computacional, permitindo a sua aplicação em diversas soluções 
desenvolvidas. 
Entre os conceitos que serão descritos ao longo deste estudo, estão os 
grafos conexo, desconexo, cíclico, acíclico, regular, completo, ponderado, 
planar, orientado, multigrafo etc. Todos eles são de suma importância 
para o entendimento da área de Teoria de Grafos.
Objetivos
 ▪ Compreender os conceitos da Teoria de Grafos; 
 ▪ Conhecer as aplicações e problemas clássicos da Teoria de Grafos; 
 ▪ Propor soluções utilizando grafos.
Algoritmos e Estruturas de Dados 3
1. Teoria de Grafos
Os conceitos da Teoria de Grafos são empregados em diversos problemas 
e soluções de muitas áreas do conhecimento. Segundo Ascencio e 
Araújo (2010), a Teoria de Grafos permite resolver qualquer problema 
de conexão entre elementos, como: malha de estradas que conectam 
cidades, conjunto de links, circuitos eletrônicos, entre outros. 
Na área de computação, a Teoria de Grafos possui grande relevância por 
sua contribuição ao desenvolvimento de soluções, principalmente, com 
o atual aumento exponencial dos dados e a gradativa necessidade de 
análise e pesquisas nesses conjuntos de dados em rede.
Figura 1: Ponte de Königsberg. Fonte: Do autor.
Uma das primeiras soluções obtidas utilizando conceitos e teoremas 
da Teoria de Grafos foi o problema da Ponte de KÖNIGSBERG, grafo 
representado na Figura 1. Atualmente, em função da tendência de 
análise e pesquisa de dados disponibilizados pela nuvem, os conceitos 
da Teoria de Grafos ganharam grande relevância. Isso ocorre por causa 
da possibilidade de um grafo ser utilizado para representar os dados de 
uma rede, permitindo que seus teoremas e aplicações desenvolvidas ao 
longo de várias décadas sejam utilizados para análise dessas redes.
2. Conceitos, Definições e Notações Básicas de 
Grafos 
Vamos ver alguns conceitos que permitirão uma base mais sólida para o 
nosso estudo da Teoria de Grafos. 
Grafo, Vértices e Arestas 
Um grafo pode ser definido como um conjunto G (V, E) formado pelo 
conjunto de vértices (V) e arestas (E). Em sua apresentação geométrica, 
um grafo pode ser representado por um vértice, um círculo ou um ponto 
e uma aresta, por meio de uma linha que liga dois vértices, conforme 
podemos observar na Figura 2.
Algoritmos e Estruturas de Dados 4
Vértice
Aresta
Figura 2: Grafo exemplo de vértices e arestas. Fonte: Do autor.
Utiliza-se a letra E para representar arestas por ser uma notação padrão, 
uma vez que arestas, em inglês, é chamada de edge.
Vértices Adjacentes 
Quando dois vértices estão ligados diretamente por uma aresta, dizemos 
que esses vértices são adjacentes. Considere uma aresta e E, que ligue 
os vértices m V e n V. Nesse cenário, dizemos que m e n são vértices 
adjacentes, como pode ser visto na Figura 3.
Vé
rti
ce
s A
dja
ce
nte
s
n a
m h
Figura 3: Vértices adjacentes. Fonte: Do autor.
Matriz de Adjacências 
Uma matriz de adjacências (Figura 4) representa as ligações entres os 
vértices de um grafo. Nela, as linhas e as colunas são os vértices; e os 
elementos da matriz representam as ligações entre tais vértices. Esse 
tipo de estrutura é muito utilizado, computacionalmente, para análises, 
permitindo verificar vértices adjacentes e caminhos no grafo.
b d
a c a b c d
a 0 1 1 0
b 1 0 0 0
c 1 0 0 1
d 0 0 1 0
Figura 4: Grafo e sua matriz de adjacências. Fonte: Do autor. 
Algoritmos e Estruturas de Dados 5
Matriz de Incidências 
Uma matriz de incidências (Figura 5) mostra se uma aresta é incidente 
a um vértice. Nela, as linhas representam os vértices e as colunas, as 
arestas. Dessa forma, os elementos da matriz são preenchidos, caso uma 
aresta seja incidente em um vértice. Esse tipo de representação também 
pode ser utilizado, computacionalmente, para guardar dados de um 
grafo.
b d
a c AB AC CD
a 1 1 0
b 1 0 0
c 0 1 1
d 0 0 1
AC
AB CD
Figura 5: Grafo e sua matriz de incidências. Fonte: Do autor.
Laço 
Um laço é uma aresta que possui o mesmo vértice em suas extremidades. 
A Figura 6 representa um grafo com laço.
Laço
Figura 6: Laço. Fonte: Do autor.
Arestas Múltiplas
Um grafo pode possuir mais de uma aresta entre um mesmo par de 
vértices (arestas múltiplas). Quando isso ocorre, dizemos que o grafo é 
um multigrafo. Veja um exemplo de multigrafo, por meio da Figura 7.
Figura 7: Grafos com arestas múltiplas (multigrafo). Fonte: Do autor. 
Algoritmos e Estruturas de Dados 6
Grau de um Vértice 
O grau de um vértice é calculado pelo número de arestas que incide 
nesse vértice. Dessa forma, no grafo da Figura 8, os graus dos vértices a, 
b, c e d são, respectivamente, 3, 1, 2 e 2 .
b d
a c
g(a) = 3
g(b) = 1
g(c) = 2
g(d) = 2
Figura 8: Cálculo do grau de um grafo. Fonte: Do autor.
Grafo Simples 
É um grafo que não possui laço nem arestas múltiplas. Veja um exemplo 
por meio da Figura 9.
Figura 9: Grafo simples. Fonte: Do autor.
Grafo Trivial 
Um grafo é trivial quando possui um único vértice, conforme pode ser 
visto na Figura 10.
Figura 10: Grafo trivial. Fonte: Do autor.
Caminho 
Um caminho é formado por uma sequência de vértices v1 até vn , e o seu 
tamanho é calculado pelo seu número de arestas. Se o caminho não tiver 
repetição de vértices, ele recebe o nome de caminho simples ou elementar; 
se não tiver repetição de arestas diferentes, recebe o nome de trajeto.
Na Figura 11, temos um exemplo de caminho simples (abcde), e na 
Figura 12, um exemplo de trajeto (acedcb).
abcde
b
da
c
e
acedcb
b
da
c
e
f
Figura 11: Caminho simples ou elementar. Fonte: Do autor. 
Figura 12: Trajeto. Fonte: Do autor.
Algoritmos e Estruturas de Dados 7
Ciclo 
Um ciclo é um caminho em que o vértice inicial vi é o vértice final vf , ou 
seja, vi = vf. A Figura 13 representa um grafo com um ciclo no caminho.
acdeba
b
da
e
c
Figura 13: Ciclo. Fonte: Do autor.
Grafos Cíclico e Acíclico 
Quando um grafo possui um ciclo, é chamado de cíclico; já o grafo que 
não possui um ciclo é chamado de acíclico. A Figura 14 ilustra um gráfico 
cíclico, e a Figura 15, um grafo acíclico. 
Figura 14: Grafo cíclico. Fonte: Do autor.
Figura 15: Grafo acíclico. Fonte: Do autor.
Subgrafo 
Um subgrafo é formado por um conjunto de vértices e arestas de um 
grafo original. Na Figura 16, o grafo da verde é subgrafo do grafo do 
grafo azul.
b
da
c
e
f
g
Subgrafo
b
da
c
e
f
Figura 16: Subgrafo. Fonte: Do autor.
Algoritmos e Estruturas de Dados 8
Grafos Conexo e Desconexo 
Um grafo é conexo quando existe, pelo menos, umcaminho entre todos 
os pares de vértices, e desconexo, quando não existe um caminho 
entre, pelo menos, um par de vértices. Um grafo desconexo é formado 
por componentes conexos. A Figura 17 ilustra um exemplo de um grafo 
conexo, e a Figura 18, de um grafo desconexo.
Figura 17: Grafo conexo. Fonte: Do autor.
Figura 18: Grafo desconexo. Fonte: Do autor.
Grafo Completo 
Um grafo é completo quando cada vértice possui uma aresta para 
todos os outros vértices, ou seja, é adjacente a todos os outros vértices. 
O número de arestas em um grafo completo pode ser calculado pela 
seguinte fórmula da combinação:
 Número de arestas Cn,2 = n!
 (n-2) ! 2!
n: número de vértices do grafo. 
Um grafo completo é representado pela letra K. A Figura 19 ilustra 
exemplos do K1, K2 , K3 e K4.
K1 K2 K3 K4
Figura 19: Grafos K1 , K2 , K3 e K4. Fonte: Do autor.
Grafo Regular 
Um grafo é regular quando todos os vértices possuem um mesmo grau. A 
Figura 20 ilustra um grafo regular de grau 3. Perceba que, nesta imagem, 
todos os vértices possuem grau 3
Algoritmos e Estruturas de Dados 9
Figura 20: Grafo regular. Fonte: Do autor.
Grafos Isomorfos 
Dois grafos são isomorfos quando há correspondência entre suas 
arestas, vértices e graus de seus vértices. Em outras palavras, nos grafos 
isomorfos, existe uma correspondência perfeita entre seus vértices 
e arestas, de tal maneira que suas representações podem se tornar 
coincidentes. A Figura 21 representa dois grafos isomorfos, com as 
correspondências de vértices: h=a, i=b, j=c, k=d, l=e, m=f, n=g.
b
da
c
e
f
g
li m
kn
j
h
h=a, i=b, j=c, k=d, l=e, m=f, n=g,
Figura 21: Grafos isomorfos. Fonte: Do autor.
Grafo Bipartido 
Em um grafo bipartido, é possível dividir seus vértices em dois conjuntos, 
de modo que os vértices do mesmo conjunto não possuem ligações 
diretas entre eles, ou seja, os vértices de um conjunto só podem estar 
diretamente ligados aos vértices do outro conjunto. A Figura 22 ilustra 
um exemplo de um grafo bipartido.
Figura 22: Grafo bipartido. Fonte: Do autor.
Grafo Ponderado 
Um grafo é ponderado quando suas arestas possuem um peso. Veja um 
exemplo por meio da Figura 23
Algoritmos e Estruturas de Dados 10
1 7
3
5
410
1
Figura 23: Grafo ponderado. Fonte: Do autor. 
Grafo Planar 
Um grafo é dito planar quando possui uma representação geométrica 
que pode ser desenhada no plano sem o cruzamento de arestas, como 
pode ser visto na Figura 24, que ilustra o grafo planar K4.
Figura 24: Grafo planar. Fonte: Do autor.
3. Grafos Orientados
Um grafo orientado, também chamado de direcionado ou dígrafo, 
possui um conjunto de vértices e arestas, de forma que todas as arestas 
possuem uma única direção. No dígrafo, cada vértice possui um grau de 
entrada e um grau de saída.
Um vértice que possui grau de entrada igual a zero é denominado fonte, 
e um vértice que possui grau de saída zero é denominado sumidouro ou 
poço. Na Figura 25, o vértice c é uma fonte, e o vértice b é um sumidouro.
b
da
e
cfonte
sumidouro
Figura 25: Dígrafo – fonte e sumidouro. Fonte: Do autor. 
Os grafos orientados possuem uma grande relevância nos estudos de 
redes, e também, para análise e representação de triplas RDF (sujeito-
predicado-objeto) na Web Semântica.
Algoritmos e Estruturas de Dados 11
Em um dígrafo, a aresta mn é diferente da aresta nm, pois as arestas 
possuem direção.
Foram descritos diferentes conceitos que formam a base da Teoria 
de Grafos, entre eles: grafos orientados e não orientados, conexos e 
desconexos, cíclicos e acíclicos, completo, regular e isomorfos. 
Todos os conceitos aprendidos podem ser aplicados na construção e 
na análise de diversas soluções computacionais, como a conectividade, 
partição de grafos etc., que possuem aplicações utilizadas para a 
resolução de inúmeros problemas. 
É importante frisar que os conhecimentos da Teoria de Grafos se aplicam 
em diversas áreas do saber, auxiliando em diversos aspectos com seus 
teoremas e conceitos consolidados.
Referências
ASCENCIO, A. F. G; ARAÚJO, G. S. Estruturas de dados: algoritmos, análise 
da complexidade e implementações em Java e C/C++. São Paulo: Pearson, 
2010.
Algoritmos e Estruturas de Dados 12
	Introdução à Teoria de Grafos
	Para Início de Conversa...
	Objetivos
	1. Teoria de Grafos
	2. Conceitos, Definições e Notações Básicas de Grafos 
	3. Grafos Orientados
	Referências