EDII C1 Introdução Grafos

Prévia do material em texto

Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
1 
1- Introdução a Grafos 
 
O objetivo deste estudo é mostrar o que representam os grafos observando o aspecto 
matemático, bem como sua importância para as diversas áreas, mas em destaque a de 
computação. Com este estudo o aluno poderá saber a história e origem dos grafos, bem 
como a aplicabilidade na computação nos dias atuais. 
 
1.1- A História dos Grafos 
 
De forma bem simples pode-se dizer que os grafos possuem uma história muito rica 
que vem desde um trabalho de longa data conforme cita Wikipédia (2014, p. 01) como 
segue: 
 
O artigo de Leonhard Euler, publicado em 1736, sobre o problema 
das sete pontes de Königsberg, é considerado o primeiro resultado da 
teoria dos grafos.1 É também considerado um dos primeiros resultados 
topológicos na geometria; isto é, não dependente de quaisquer medidas. 
Isso ilustra a profunda conexão entre a teoria dos grafos e topologia. 
 
 
 Mas quem foi Leonhard Euler? Conforme Wikipédia (2014, p. 01) ele foi um 
grande matemático que deu os primeiros passos nessa teoria dos grafos, como segue: 
 
 Euler fez importantes descobertas em campos variados em cálculo e 
grafos. Também fez muitas contribuições para a matemática moderna no 
campo da terminologia e notação, em especial para a análise matemática, 
como a noção de uma função matemática. 
 
 Além disso tornou-se célebre por seus trabalhos em mecânica, óptica, e 
astronomia. Euler é considerado um dos mais proeminentes matemáticos 
do século XVIII. Uma declaração atribuída a Pierre-Simon Laplace 
manifestada sobre Euler na sua influência sobre a matemática: "Leiam 
Euler, leiam Euler, ele é o mestre de todos nós. 
 
 Euler foi um dos mais prolíficos matemáticos, calcula-se que toda a sua 
obra reunida teria entre 60 e 80 volumes. 
 
 
Dentre muitos trabalhos desenvolvidos por Euler, obviamente destaca-se a teoria 
dos grafos, foco deste estudo, através do famoso problema conhecido como sete pontes de 
Königsberg , como segue, conforme Wikipédia (2014, p 01): 
 
 
 Em 1736, Euler resolveu o problema conhecido como sete pontes de 
Königsberg. A cidade de Königsberg, Prússia, foi construída no rio 
Pregel, e incluiu duas grandes ilhas que estavam conectadas entre si e ao 
continente por sete pontes. O problema era o de decidir se é possível 
seguir um caminho que atravessa cada uma das pontes exatamente uma 
vez e retornar ao ponto de partida. Esta solução é considerada como sendo 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
2 
o primeiro teorema da teoria dos grafos, especificamente da teoria gráfica 
planar. 
 
 Euler também descobriu a fórmula V - E + F = 2 relacionando o número 
de vértices, arestas e faces de um poliedro convexo e, portanto, de um 
grafo planar. A constante nesta fórmula é agora conhecida como a 
característica de Euler para o gráfico (ou objeto de cálculo), e está 
relacionada ao gênero do objeto. O estudo e generalização desta fórmula 
foram, especificamente através de Augustin-Louis Cauchy, Simon 
Antoine Jean L'Huillier, estando na origem da topologia. 
 
 
Na sequência uma figura do famoso problema que trata do mapa de Könogsber na 
época de Euler mostrando o layout das sete pontes, destacando o rio Pregel e suas pontas, 
que será abordado posteriormente. 
 
Figura 01 – Problema das Sete Pontes de Euler 
 
 
 
Fonte: Wikipédia (2014, p. 02) 
 
Como visto a fundamentação dos grafos esta na sua constituição matemática, 
possuindo diversas aplicabilidades que serão vistas futuramente neste estudo. 
 
Portanto neste estudo será usada a visão Euleriana quanto aos grafos, sabendo-se 
que possui varias outras como Hamiltonianos e outras escolas em relação ao assunto. 
 
1.1.1 Porque das Sete Pontes de Euler? 
 
Conforme Sá e Silva (2012, p. 09), 
 
Para iniciar esse resgate histórico, lembremos que numa cidade chamada 
Konisberg (atual Kaliningrado, na Rússia) havia sete pontes cruzando o 
Rio Pregel, conforme o mapa apresentado na Figura 1. Muitos moradores 
dessa cidade se questionavam sobre a existência de um caminho no qual 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
3 
alguém pudesse sair de algum ponto da cidade, percorrer as sete pontes 
uma única vez e voltar ao ponto inicial. Essa dúvida ficou no ar até que 
Leonard Euler, em 1736, resolveu esse problema inaugurando um novo 
ramo da matemática: a Teoria dos Grafos. Para solucionar o problema, 
Euler criou um desenho que esboçasse a cidade. Para tanto, ele 
representou as pontes por linhas e as porções de terra (ilhas e margens) 
por pontos, conforme apresentado na Figura 2. Esse foi o primeiro Grafo 
da história. 
 
 
Figura 1. Mapa com as Pontes de Konisberg. 
 
 
Figura 2. Grafo que representa a cidade de Konisberg. 
 
Sá e Silva (2012, p. 09) citam que, 
 
Após chamar cada linha de aresta e cada ponto de vértice, Euler passou a 
analisar o número de arestas que incide em cada vértice. Esse número é 
chamado de Grau de um vértice e é escrito como G(v), onde v é o vértice 
analisado. O que se procurava, então, era o que hoje chamamos de 
caminho euleriano fechado (no qual os pontos inicial e final coincidem). 
Determinamos um caminho desse tipo por meio do Teorema que diz que 
um grafo conexo admite caminho euleriano fechado se, e somente se, 
todos os vértices têm grau par. Vale lembrar que, analogamente, há os 
caminhos eulerianos abertos, nos quais é possível realizar um trajeto em 
que os pontos inicial e final são distintos, como no Grafo abaixo. 
 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
4 
 
Figura 3. Grafo com caminho euleriano aberto. 
 
Para que um caminho seja euleriano aberto, o grafo deve ter exatamente 
dois vértices de grau ímpar, que serão a partida e a chegada do caminho. 
No grafo da figura 3, temos que esses pontos são os vértices A e E. 
 
Voltando ao problema das sete pontes de Konisberg, verificamos no grafo 
da figura 1 que G(A) = 5, G(B) = 3, G(C) = 3 e G(D) = 3. Dessa forma, 
concluímos que há mais de dois vértices com grau ímpar e, assim, não 
é possível estabelecer nenhum tipo de caminho por todas as pontes de 
Konisberg. (Grifo Nosso). 
 
A pergunta eraa seguinte: 
 
Haveria possibilidade de transitar pela cidade de Konisberg, iniciando e 
terminando no mesmo lugar, passando cada ponte exatamente uma vez? 
 
A representação de Euler foi seguinte conforme figura abaixo: 
 
Figura 02 – Representação Gráfica das sete pontes de Euler 
 
 
 
Fonte: Fontes (2009, p. 04) 
 
Conforme Fonte (2009, p. 04), “Euler representou as relações graficamente. A cada 
margem e ilha associou um nó e a cada ponte um arco.” 
 
Como visto nesta explanação foi resolvido um problema onde citam que muitos 
moradores dessa cidade se questionavam sobre a existência de um caminho no qual alguém 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
5 
pudesse sair de algum ponto da cidade, percorrer as sete pontes uma única vez e voltar ao 
ponto inicial. 
 
Conforme citado acima a dúvida ficou no ar até que Leonard Euler, em 1736, 
resolveu esse problema inaugurando um novo ramo da matemática: a Teoria dos Grafos. 
 
Por isto se tem hoje os Grafos Eulerianos, em homenagem a este grande 
matemático que desvendou este enigma conhecido como as Sete Pontes de Konisberg, mas 
sabe-se que existem os hamiltonianos, dentre outros. 
 
1.2 O que são grafos? 
 
Vários conceitos podem ser dados quanto aos grafos, mas segundo a Wikipédia 
(2014, p. 05) pode-se dizer que grafos são: 
 
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,A), onde V é um conjunto não vazio 
de objetos denominados vértices e A é um conjunto de pares não 
ordenados de V, chamado arestas. 
 
Dependendo da aplicação, arestas podem ou não ter direção, 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 uma 
direção associada (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. 
 
 
Outro conceito pode ser da seguinte forma segundo Ribeiro (2012, p.03), como 
segue: 
 
Um grafo é uma representação abstrata de um conjunto de objetos e das 
relações existentes entre eles. É definido por um conjunto de nós ou 
vértices, e pelas ligações ou arestas, que ligam pares de nós. Uma grande 
variedade de estruturas do mundo real podem ser representadas 
abstratamente através de grafos. 
 
A figura seguinte ilustra um grafo com 5 nós. 
 
 
 
 
 
 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
6 
Um grafo é descrito por um par (V,E), onde V é o conjunto de vértices 
e E o conjunto das arestas que ligam pares de vértices. Um grafo pode 
ser dirigido ou direcionado, se as arestas tiverem uma direção, ou não 
dirigido, se as arestas não tiverem direção. A figura seguinte ilustra um 
grafo dirigido. 
 
 
 
 
Se as arestas tiverem associado um peso ou custo, o grafo passa a chamar-
se de grafo pesado. A figura seguinte ilustra um grafo pesado não 
dirigido. 
 
 
 
 
 
 
Os nós podem ser de diferente tipos, representados por cores ou etiquetas. 
Nesse caso, o grafo diz-se colorido. A figura seguinte ilustra um grafo 
colorido não dirigido. 
 
 
 
 
 
Quando apenas é admitida no máximo uma aresta entre dois nós, diz-se 
que o grafo é simples. 
 
 
Como visto então os grafos são representações de objetos das mais variadas formas 
que se relacionam entre si formando uma verdadeira “rede”, possuindo vários tipos neste 
contexto que serão vistos posteriormente. 
 
A seguir algumas aplicabilidades iniciais dos grafos. 
 
 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
7 
1.3 Algumas das aplicabilidades dos grafos 
 
Conforme Ribeiro (2012, p.03), os grafos podem ter várias aplicabilidades como 
segue: 
 
Um vasto leque de sistemas naturais ou artificiais pode ser representado 
através de grafos. Por exemplo, no campo da biologia podemos ter uma 
cadeia alimentar, com os animais a serem os nós, e as relações de 
predador-presa entre eles a serem as arestas. Podemos ter também outras 
estruturas biológicas, tais como uma rede neuronal (ligações entre 
neurónios) ou uma rede interação entre proteínas. Na sociologia podemos 
ter uma rede social de amigos com ligações representando amizades. 
 
No software podemos ter uma rede representando heranças entre objetos. 
Num patamar de existência mais física podemos ter grafos representando 
uma rede de auto-estradas ligando cidades, uma rede elétrica ligando 
casas, uma rede computadores, ou uma rede de páginas da internet com 
hiperligações entre si. Muitos mais exemplos poderiam ser dados, mas o 
essencial é perceber que os grafos são uma representação abstrata muito 
poderosa e flexível. (Grifo nosso). 
 
 
Outras aplicabilidades observando seus vértices e suas arestas conforme Fontes 
(2009, p. 7) seriam: 
 
Motores de busca de páginas Web: 
 
- Vértices são as páginas HTML e as arestas (direcionadas) são links 
ligando as páginas 
- Identificar proximidade entre duas páginas quaisquer 
- Identificar se uma página é acessível a partir de outra 
- Identificar o número de links para uma página (grau do vértice) 
 
Roteamento de Carga: 
 
- Vértices são pontos de entrega e as arestas (com pesos) são estradas 
- Descobrir a rota de entrega com menor custo 
- Identificar a rota mais rápida. 
 
Problema de Fluxo de redes. 
: 
Desta forma como foi citado anteriormente ficam bem evidentes e claras as 
aplicabilidades dos grafos e a sua importância para a vida das pessoas, como visto não 
param por ai sendo muito vasta, principalmente nos dias atuais com o crescimento da 
computação e todas as suas possibilidades. 
 
Conforme Ribeiro (2012, p. 04) as aplicabilidades se mostram bem constantes na 
informática ou na ciência da computação, como segue: 
 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
8 
Dada a enorme utilidade dos grafos como representações de 
conhecimento, existe toda uma área de Ciência de 
Computadores dedicada ao seu estudo e são inúmeros e muito importantes 
os algoritmos que manipulam grafos.Um exemplo é o Algoritmo de 
Dijkstra, que encontra o caminho mais curto entre um nó e todos os outros 
nós, num grafo pesado. Existem muitos outros algoritmos para outras 
tarefas tais como maximizar o fluxo entre nós ou encontrar a árvore 
mínima de suporte. 
 
Ribeiro (2012, p. 05) cita que que: 
 
Do ponto de vista da Programação, um grafo é uma estrutura de dados e 
existem duas maneiras base de o implementar na prática: 
 
 Matriz de Adjacências: uma matriz de V por V células, onde a 
célula na linha i e coluna j nos dá informação sobre a ligação entre os 
nós i e j. Por exemplo, se o grafo não for pesado, a célula podia conter o 
valor verdadeiro (ou um) quando existisse uma ligação entre i e j e o 
valor falso (ou zero) quando tal não acontecesse. Se o grafo for pesado, 
cada célula pode conter um número representando o peso da aresta. A 
figura seguinte ilustra um grafo não dirigido e a sua correspondente matriz 
de adjacências. 
 
 
 
 
 
 Lista de Adjacências: um vetor de listas onde a posição i do vetor 
contém uma lista dos nós aos quais o nó i se encontra ligado. Se o grafo 
for pesado, cada elemento da lista contém também o peso da ligação. A 
figura seguinte ilustra um grafo não dirigido e a sua correspondente lista 
de adjacências. 
 
 
 
 
 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
9 
A matriz permite verificar em tempo constante se uma dada ligação existe 
ou não. Por oposição, no caso da lista, tal não acontece e é necessário 
percorrer a lista para saber se um dado nó está ou não ligado. Em 
contrapartida, se for necessário percorrer todos os nós ligados a um dado 
nó, a lista é mais eficiente, pois permite percorrer apenas os nós ligados, e 
não andar a percorrer toda uma linha da matriz, verificando se a ligação 
existe ou não. 
 
Para gravar, na Matriz de Adjacências a pergunta é “A” tem ligação com ? Na Lista de 
Adjacências a pergunta é “A” esta para ? 
 
Sendo assim as aplicabilidades são muitas conforme foi referenciado no exemplo 
acima indo desde sistemas naturais até sistemas artificiais, como os da computação, sendo 
nestes a solução ser resolvida por elementos matemáticos como matrizes e listas (vetores). 
 
1.4 Entendendo os grafos 
 
Os grafos após este pequeno entendimento inicial possuem uma visão matemática 
bem forte e se constituem na seguinte sistemática que será apresentada, contendo elementos 
como Vértices e Arestas. 
 
Os grafos podem ser orientados e não orientados. Na sequência deste estudo irá se 
tratar melhor deste aspecto. 
 
Conforme Fortes (2009, 08) Grafo, na verdade é, 
 
(...) é uma noção simples, abstrata e intuitiva, usada para representar a 
idéia de alguma espécie de relação entre os objetos. Graficamente, 
aparece representado por uma figura com nós ou vértices, significando os 
objetos, unidos por um traço denominado aresta configurando a relação 
imaginada. 
 
Na figura a seguir esta representada um grafo baseado nas pontes de Euler, como 
segue: 
 
Figura 03 – Representação de grafos baseada nas sete pontes de Euler 
 
 
Fonte: Fontes (2009, p. 09) 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
10 
Veja nesta figura acima que os Vértices as letras de “A” até “D” e as Arestas são as 
ligações entre as letras citadas. 
 
A representação matemática segundo Fonte (2009, p. 09) é a seguinte: 
 
Como visto a representação é bem simples resultando G = (V, E). 
 
Quadro 01 – Representação matemática de um grafo 
 
 
 
 
 
 
 
 
 
 
Fonte: Fonte (2009, p. 09) 
 
A seguir será mostrado exemplos de grafo para melhor elucidar o contexto acima 
descrito: 
 
Exemplo 1: 
 
Conforme Fontes (2009, p. 10) seria da seguinte forma como no exemplo 1: 
 
 
 
A figura acima mostra o grafo G(V,E). Observe que laços (self-loops) são 
permitidos pela definição. Múltiplas linhas não são permitidas. Neste 
exemplo, V = {1, 2, 3, 4, 5, 6} e E = {{1,3}, {2,3},{3,4},{3,5},{6,6}}. È 
comum a utilização da variável vi ou xi, i = 1, 2, ..., n para a distinção dos 
nós (vértices). |V| = 6, |E| =5. 
Um grafo é representado matematicamente por: G = (V, E) 
 
 Onde V é o conjunto de vértices e E é o conjunto de 
arestas ou ligações entre os vértices. (|V| = n, |E| = m). 
 
 Onde: n = |V| é a ordem do grafo 
 m = |E| é o tamanho do grafo. 
 Se m = 0 o grafo é dito trivial. 
 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
11 
Como visto no exemplo 1 acima os Vértices são as bolinhas numeradas que serão 
chamadas de números de (1 a 6) e Arestas são as ligações por exemplo (1 a 3) (2 a 3) e 
assim sucessivamente. 
 
Exemplo 2: 
 
Neste outro exemplo conforme Fontes (2009, p. 10), têm-se: 
 
 Seja o grafo G(V,A) dado por: 
 
 V = {p | p é uma pessoa } 
 A = {(u,v) | < u é amigo de v > } 
 
 Seja o exemplo: 
 
 V = {Maria, Pedro, Joana, Luiz } 
 A = {(Maria, Pedro), (Joana, Maria), (Maria, Luiz), (Pedro, Luiz) , (Joana, 
Pedro) } 
 
 Construa o grafo do exemplo acima. 
A construção deste grafo dar-se-ia da seguinte forma conforme figura abaixo: 
 
Figura 04 – Representação de grafos do problema 
 
 
 
Fonte: Fontes (2009, p. 11). 
 
Como visto então fica fácil encontrar o formato do grafo, pois se analisando o 
enunciado dado pelo autor acima: 
 
V = {Maria, Pedro, Joana, Luiz } 
 
A = {(Maria, Pedro) , (Joana, Maria) , (Maria, Luiz), (Pedro, Luiz) , (Joana, Pedro) } 
 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
12 
Observa-se que os vértices são as pessoas e as arestas são as ligações, portanto o 
grafo esta pronto. 
 
Exercício: 
 
Dado o seguinte enunciado na mesma linha de raciocínio do grafo acima, obervando 
que os vértices são pessoas e as arestas são as ligações solicitadas, construa o grafo 
seguindo os dados abaixo: 
 
V = {Maria, Pedro, Tiago, Ana, Luiz } 
 
A = {(Maria, Pedro) , (Pedro, Tiago) , (Maria, Ana), (Maria, Luiz) , (Pedro, Ana), (Pedro, 
Luiz), (Ana, Tiago), (Tiago, Luiz) } 
 
Solução deste grafo: 
 
Figura 05 – Representação da solução de grafos 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Fonte: Alcântara(2014, p. 12). 
 
Como visto então basta seguir os relacionamentos solicitados e terá o grafo montado 
conforme o exemplo acima. 
 
 
1.4.1 Vértices e Arestas, elementos básicos dos grafos 
 
Os grafos possuem basicamente dois elementos que se destacam num primeiro 
momento, que são os Vértices e as Arestas, sendo estes últimos os elementos que irão 
ligar-se entre si e formar o grafo e os primeiros são os elos do mesmo, podendo ser 
representado por números, nomes, etc. 
 
 
Maria 
Ana 
Luiz 
Pedro 
Tiago 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
13 
Conforme Fontes (2009, p. 12) têm-se: 
 
Em um grafo não orientado G=(V,E), o conjunto de arestas E consiste 
em pares de vértices não ordenados. 
 
V={1,2,3,4,5,6} 
 
E={(1,2),(1,5),(2,5),(3,6)} 
 
 
 
 
 Fonte: Fontes (2009, p. 12), 
 
Neste exemplo dado pelo autor acima citado observa-se que “E” representa as 
arestas, ou seja, as ligações entre os vértices, representados por “V”. 
 
Exercício: 
 
Observando-se o mesmo grafo, quais as arestas completariam o grafo em ordem, 
através de ligações com retas, sendo que o mesmo não poderia cruzar por cima de 
nenhuma aresta novamente? 
 
V={1,2,3,4,5,6} 
E={(1,2),(1,4),(1,5),(2,3),(2,5),(2,6),(3,6),(4,5),(5,6)} 
 
 
Figura 06 – Solução da representação de elementos de grafos 
 
 
 
Fonte: Adaptado de Fontes (2009, p. 13), 
 
 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
14 
1.5 Aspectos gerais dos grafos 
 
Como visto até então se entendeu claramente o que são os grafos, bem como suas 
aplicabilidades, neste item em diante serão mostrados os aspectos gerais dos grafos, como 
tipos, características, dentre outras, como segue, para proporcionar um melhor 
entendimento. 
 
1.5.1 Grafos 
 
Conforme Conceito...(2014, p. 14) um grafo tem a seguinte sistemática, 
 
Um grafo G(V,A) é definido pelo par de conjuntos V e A, onde: 
 
V - conjunto não vazio: os vértices ou nodos do grafo; 
A - conjunto de pares ordenados a=(v,w), v e w ∈ V: as arestas do 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 (ver G1) é dado por: 
 
V = { Maria, Pedro, Joana, Luiz } 
A = { (Maria, Pedro), (Pedro, Maria), (Joana, Maria), (Maria, Joana), 
(Pedro, Luiz), (Luiz, Pedro), (Joana, Pedro) , (Pedro, Joana)}. 
 
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. 
 
Na figura a seguir mostra um simples grafo denominado G1. 
 
 
 
Fonte: Conceito... (2014, p. 14) 
 
Como visto então nenhuma novidade do que já foi passado até aqui, só que a partir 
de agora se mostrará alguns elementos a mais além de Vértices e Arestas dos grafos. 
 
Na sequência será visto o que representa o Digrafo. 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
15 
1.5.2 Digrafo 
 
Conforme Conceito... (2014, p. 14) um grafo tem a seguinte sistemática, 
 
Considere, agora, o grafo definido por: 
V = { p | p é uma pessoa da família Castro } 
A = { (v,w) | < v é pai/mãe de w > } 
Um exemplo de deste grafo (ver G2) é: 
V = { Emerson, Isadora, Renata, Antonio, Cecília, Alfredo } 
A = {(Isadora, Emerson), (Antonio, Renata), (Alfredo, Emerson), 
(Cecília, Antonio), (Alfredo, Antonio)}. 
 
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 de G. 
O grafo acima é dito ser um grafo orientado (ou digrafo), sendo que as 
conexões entre os vértices são chamadas de arcos. 
 
Na figura a seguir mostra um simples dígrafo denominado G2. 
 
 
 
 
Outro conceito vem de Feofiloff (2013, p. 15) que diz: 
 
 
 Um digrafo (= digraph = directed graph) é uma coisa que consiste em 
dois conjuntos: um conjunto de coisas conhecidas como vértices e um 
conjunto de coisas conhecidas como arcos. Cada arco é um par ordenado 
de vértices. O primeiro vértice do par é a ponta inicial do arco e o 
segundo é a ponta final. 
 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
16 
 A ponta final de todo arco é diferente de sua ponta inicial. [O livro de 
Sedgewick admite arcos cuja ponta final é igual à inicial. Arcos desse tipo 
são conhecidos como laços (= loops). Nossos digrafos não terão laços.] 
 Um arco com ponta inicial v e ponta final w será denotado por v-w . 
 
 (É preciso estar atento ao contexto para não confundir essa expressão com 
"v menos w".) Dizemos que o arco v-w sai de v e entra em w. A 
presença de um arco v-w é independente da presença do arco w-v: o 
digrafo pode ter os arcos v-w e w-v, pode ter apenas um deles, ou pode 
não ter nenhum deles. 
 
 Dizemos que um vértice w é vizinho de um vértice v se v-w é um arco 
do digrafo. Dizemos também, nessa circunstância, que w é adjacente 
a v. A relação de vizinhança não é simétrica: w pode ser vizinho 
de v sem que v seja vizinho de w. (Grifo Nosso). 
 
 
Assim desta forma pode-se definir dígrafo conforme figura a seguir: 
 
 
 
 
Um exemplo baseado no digrafo acima conforme Feofiloff (2013, p. 16) seria o 
seguinte: 
 
Uma boa maneira de especificar um digrafo é exibir o seu conjunto de 
arcos. Por exemplo, o conjunto de arcos 
0-5 0-6 2-0 2-3 3-6 3-10 4-1 5-2 5-10 6-2 7-8 8-1 8-4 10-3 11-8 
 
define um digrafo sobre o conjunto de vértices 0..11. 
O vértice 9 é isolado. (Grifo Nosso). 
 
 
Veja que nos digrafos 0-5 são arcos observando a direção, pois te uma seta ( ), 
que sai de 0 e vai até 5 e assim para todos os demais. Nos grafos chama-se de arestas. 
 
 
 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
17 
1.5.3 Características dos grafos em geral 
 
Algumas características e particularidades os grafos e digrafos possuem conforme 
Adaptação de Conceito ... (2014, p. 17), como segue: 
 
ORDEM 
A ordem de um grafo G é dada pela cardinalidade do conjunto de 
vértices, ou seja, pelo número de vértices de G. Nos exemplos 
acima: 
 
 - ordem(G1) = 4 
 - ordem(G2) = 6 
 
ADJACÊNCIA 
Em um grafo simples (a exemplo de G1) dois vértices v e w são 
adjacentes (ou vizinhos) se há uma aresta a=(v,w) em G. Está aresta 
é dita ser incidente a ambos, v e w. É o caso dos vértices 
Maria e Pedro em G1. No caso do grafo ser dirigido (a exemplo 
de G2), 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. Em G2, 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. Em G2, por exemplo, diz-se 
que Alfredo e Cecília são antecessores de Antonio. 
 
GRAU 
O grau de um vértice é dado pelo número de arestas que lhe são 
incidentes. Em G1, por exemplo: 
 
 - grau(Pedro) = 3 
 - grau(Maria) = 2 
No caso do grafo ser dirigido (a exemplo de G2), 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. Em G2, por exemplo: 
 - grauDeEmissão(Antonio) = 1 
- grauDeEmissao(Alfredo) = 2 
- grauDeEmissao(Renata) = 0 
 
 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
18 
Grau de recepção: o grau de recepção de um vértice v corresponde 
ao número de arcos que chegam a v. Em G2, por exemplo: 
 
 - grauDeRecepção(Antonio) = 2 
 - grauDeRecepção(Alfredo) = 0 
 - grauDeRecepção(Renata) = 1 
 
FONTE 
Um vértice v é uma fonte se grauDeRecepção(v) = 0. É o caso dos 
vértices Isadora, Alfredo e Cecília em G2. 
 
SUMIDOURO 
Um vértice v é um sumidouro se grauDeEmissão(v) = 0. É o caso 
dos vértices Renata e Emerson em G2. 
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. Em G3 há três ocorrências de 
laços para um grafo não orientado. 
 
 
 G3: 
 
 
Veja que estas características são fáceis de serem identificadas nos grafos e digrafos 
como segue: 
 
- No caso da ORDEM é correspondente ao número de ligações, vértices, veja na 
figura G1 acima; 
 
- No caso da ADJACÊNCIA esta baseada na vizinhança observando que há 
SUCESSORES no caso da figura G2 acima quando as setas ( ) chegam. Exemplo: 
Emerson e Antonio são sucessores de Alfredo. Há os ANTECESSORES,que são de onde 
partem as setas ( ) saem. Ex: Alfredo e Cecília são antecessores de Antonio. 
 
- No caso GRAU é número de ligações que cada vértice recebe. Ex: Na figura G1 
por exemplo Pedro recebe 03 ligações (arestas). Quando for GRAU em digrafos tem grau 
de emissão “que partem” e de recepção “que recebem”. 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
19 
- No caso de FONTE é quando o grau de recepção for ZERO. É o caso dos vértices 
Renata e Emerson em Figura G2. 
 
- No caso de SUMIDOURO é quando o grau de emissão for ZERO. É o caso dos 
vértices Renata e Emerson em G2. 
 
- No caso do LAÇO é quando um vértice (grafo) ou arco (digrafo) se relaciona com 
ele mesmo. 
 
1.5.4 Alguns tipos de grafos 
 
Conforme Conceito ...(2014, p.19) existem alguns tipos de grafos como segue: 
 
GRAFO REGULAR 
 
Um grafo é dito ser regular quando todos os seus vértices tem o mesmo 
grau. 
O grafo G4, por exemplo, é dito ser um grafo regular-3, pois todos os seus 
vértices tem grau 3. 
 
G4: 
 
 
 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. 
 
 
 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
20 
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. 
Para exemplificar, sejam os conjuntos H={h | h é um homem} e M={m | 
m é um mulher} e o grafo G(V,A) (ver o exemplo G5) onde: 
V = H U M 
A = {(v,w) | (v ∈ H e w ∈ M) ou (v ∈ M e w ∈ H) 
e <v foi namorado de w>} 
 
G5: 
 
 
O grafo G6 é uma K3,3, ou seja, um grafo bipartido completo que contém 
duas partições de 3 vértices cada. Ele é completo, pois todos os vértices de 
uma partição estão ligados a todos os vértices da outra partição. 
 
 
 
 
 
 
 
 GRAFO ROTULADO 
 
Um grafo G(V,A) é dito ser rotulado em vértices (ou arestas) quando a 
cada vértice (ou aresta) estiver associado um rótulo. G5 é um exemplo de 
grafo rotulado. 
 
 
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 (ver o grafo G7), seja G (V,A) onde: 
 
G6: 
K3,3 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
21 
 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 voo>} 
 
 
 
 
 
 
 
 
 
 MULTIGRAFO 
 
Um grafo G(V,A) é dito ser um multigrafo quando existem múltiplas 
arestas entre pares de vértices de G. No grafo G8, por exemplo, há duas 
arestas entre os vértices A e C e entre os vértices A e B, caracterizando-o 
como um multigrafo. 
 
 
 
 
 
 
 
 
SUBGRAFO 
 
Um grafo Gs(Vs, As) é dito ser subgrafo de um 
grafo G(V,A) quando Vs ⊆ V e As ⊆ A. O grafo G9, por exemplo, é 
subgrafo de G8. 
G9: 
 
 
HIPERGRAFO 
 
Um hipergrafo H(V,A) é definido pelo par de conjuntos V e A, onde: 
 
V - conjunto não vazio;A - uma família e partes não vazias de V. 
 
 
G7: 
 
G8: 
 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
22 
Seja, por exemplo, o grafo H(V,A) dado por: 
 
V = { x1, x2, x3, x4} 
A = { {x1, x2, x4}, {x2, x3, x4}, {x2, x3}} 
G10: 
 
 
Como visto acima são vários tipos de grafos existentes e todos tem a sua 
importância neste nosso estudo. 
 
1.5.5 Percurso de grafos 
 
Neste item conforme Conceito... (2014, p.22) têm-se os mais variados percursos de 
grafos que se tem como segue: 
 
CADEIA 
 
Uma cadeia é uma sequê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 em G11. 
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. 
 
 
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 em G11. 
 
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 em G11. 
 
CIRCUITO 
 
Um circuito é um caminho simples e fechado. A seqüência de vértices (x1, 
x2, x5, x4, x1) é um exemplo de circuito elementar em G11. 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
23 
FECHO TRANSITIVO 
 
O fecho transitivo direto (ftd) de um vértice v é o conjunto de todos os 
vértices que podem ser atingidos por algum caminho iniciando em v. O ftd 
do vértice x5 do grafo G17, por exemplo, é o conjunto: {x1, x2, x3, x4, x5, 
x6}. Note que o próprio vértice faz parte do ftd já que ele é alcançável 
partindo-se dele mesmo. 
 
O fecho transitivo inverso (fti) de um vértice v é o conjunto de todos os 
vértices a partir dos quais se pode atingir v por algum caminho. O fti do 
vértice x5 do grafo G17, por exemplo, é o conjunto: {x1, x2, x4, x5, x7}. Note 
que o próprio vértice faz parte do fti já que dele se pode alncançar ele 
mesmo. 
G11: 
Como visto acima se tem vários tipos de percursos do grafos disponíveis. 
 
 
1.5.6 Conexões de grafos 
 
Neste item serão estudadas as formas como os grafos se conectam entre si, 
conforme Conceito... (2014, p.23), como segue: 
 
GRAFO CONEXO 
 
Um grafo G(V,A) é dito ser conexo se há pelo menos uma cadeia ligando 
cada par de vértices deste grafo G. 
 
G12: 
 
 
 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
24 
G13: 
 
 
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. 
 
G14: 
 
 
COMPONENTE CONEXA 
 
Um grafo G(V,A) desconexo é formado por pelo menos dois subgrafos 
conexos, disjuntos em relação aos vértices e maximais em relação à 
inclusão. Cada um destes subgrafos conexos é disto ser uma componente 
conexa de G. 
 
 
 
 
 
 
 
 
GRAFO FORTEMENTE CONEXO 
 
No caso de grafos orientados, um grafo é dito ser fortemente conexo (f-
conexo) se todo par de vértices está ligado por pelo menos um caminho 
em cada sentido, ou seja, se cada par de vértices participa de um circuito. 
Isto significa que cada vértice pode ser alcançável partindo-se de qualquer 
outro vértice do grafo. 
 
 
 
 
 
 
G15: 
 
G16: 
 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
25 
COMPONENTE FORTEMENTE CONEXA 
 
Um grafo G(V,A) que náo é fortemente conexo é formado por pelo menos 
dois subgrafos fortemente conexos, disjuntos em relação aos vértices e 
maximais em relação à inclusão. Cada um destes subgrafos é disto ser 
uma componente fortemente conexa de G, a exemplo dos subgrafos 
identificados por S1, S2 e S3 em G17. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
VÉRTICE DE CORTE 
 
Um vértice é dito ser um vértice de corte se sua remoção (juntamente com 
as arestas a ele conectadas) provoca um redução na conexidade do grafo. 
Os vértices x2 em G13 e G14 são exemplos de vértices de corte. 
 
 
PONTE 
 
Uma aresta é dita ser uma ponte se sua remoção provoca uma redução na 
conexidade do grafo. As arestas (x1, x2) em G13 e G14 são exemplos de 
pontes. 
 
Na sequência serão estudadas as bases e raízes dos grafos, como segue: 
 
 
 
 
 
 
 
 
 
G17: 
 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
26 
1.5.7 Bases e raízes dos grafos 
 
Neste item serão estudados as bases e raízes dos grafos, como eles funcionam, 
conforme Conceito... (2014, p.25), como segue: 
 
BASE 
 
Uma base de um grafo G(V,A) é um subconjunto B ⊆ V, tal que: 
- dois vértices quaisquer de B não são ligados por nenhum caminho; 
- todo vértice não pertencente a B pode ser atingido por um caminho 
partindo de B. 
 
ANTI-BASE 
 
Uma anti-base de um grafo G(V,A) é um subconjunto A ⊆ V, tal que: 
- dois vértices quaisquer de A não são ligados por nenhum caminho; 
- de todo vértice não pertencente a A pode ser atingir A por um caminho. 
 
 
 
 
 
 
 
 
 
RAIZ 
 
Se a base de um grafo G(V,A) é um conjunto unitário, então esta base é a 
raiz de G. 
 
ANTI-RAIZ 
 
Se a anti-base de um grafo G(V,A) é um conjunto unitário, então esta anti-
base é a anti-raiz de G. 
 
 
 
 
 
 
 
 
 
 
G18: 
 
G19: 
 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da ComputaçãoEstrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
27 
1.5.8 Arvores em grafos 
 
Neste item serão estudados as arvores, mostrando que arvores são grafos, conforme 
Conceito... (2014, p.27), como segue: 
 
ÁRVORE 
 
Uma árvore é um grafo conexo sem ciclos. 
Seja G(V,A) um grafo com ordem n ≥ 2. As propriedades seguintes são 
equivalentes e suficientes para caracterizar G como uma árvore: 
 1. G é conexo e sem ciclos; 
 2. G é sem ciclos e tem n-1 arestas; 
 3. G é conexo e tem n-1 arestas; 
4. G é sem ciclos e por adição de uma aresta se cria um ciclo e somente 
um; 
5. G é conexo, mas deixa de sê-lo se uma aresta é suprimida (todas as 
arestas são pontes); 
6. todo par de vértices de G é unido por uma e somente uma cadeia 
simples. 
 
 
 
 
 
 
 
 
ARBORESCÊNCIA 
 
Uma arborescência é uma árvore que possui uma raiz. Aplica-se, portanto, 
somente a grafos orientados. 
 
 
 
 
 
 
 
 
 
 
 
 
G20: 
 
G21: 
 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
28 
FLORESTA 
 
Uma floresta é um grafo cujas componentes conexas são árvores. 
 
 
 
 
 
 
 
 
 
 
 
 
1.5.9 Grafos planares e não planares 
 
Neste item será estudado os grafos planares, aqueles que não cruzam por cima de 
arestas ou arcos do outros e não planares, conforme Conceito ... (2014, p.28), como segue: 
 
GRAFOS PLANARES E NÃO PLANARES 
 
Um grafo G(V,A) é dito ser planar quando existe alguma forma de se dispor 
seus vértices em um plano de tal modo que nenhum par de arestas se cruze. 
Ao lado (A seguir) aparecem três representações gráficas distintas para 
uma K4 (grafo completo de ordem 4). Apesar de haver um cruzamento de 
arestas na primeira das representações gráficas, a K4 é um grafo planar pois 
admite pelo menos uma representação num plano sem que haja cruzamento 
de arestas (duas possíveis representações aparecem nas figuras ao lado). 
(grifo nosso). 
 
 
K4: 
 
 
 
 
 
G22: 
 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
29 
 Já uma K5 e uma K3,3 são exemplos de grafos não planares. Estes dois 
grafos não admitem representações planares. 
 
 
 
 
 
 
 
 
1.5.10 Grafos com colorações 
 
Neste item será estudado os grafos e suas colorações, conforme Conceito ... (2014, 
p.29), como segue: 
 
COLORAÇÃO 
 
Seja G(V,A) um grafo e C um conjunto de cores. Uma coloração de G é 
uma atribuição de alguma cor de C para cada vértice de V, de tal modo 
que a dois vértices adjacentes sejam atribuídas cores diferentes. Assim 
sendo, uma coloração de G é uma função f: V → C tal que para cada par 
de vértices (v,w) ∈ A → f(v) ≠ f(w). 
Uma k-coloração de G é uma coloração que utiliza um total de k cores. O 
exemplo ao lado mostra um 4-coloração para o grafo. 
 
 
 
NÚMERO CROMÁTICO 
 
Denomina-se número cromático X(G) de um grafo G ao menor número de 
cores k, para o qual existe uma k-coloração de G. O exemplo ao lado 
mostra uma 3-coloração para o grafo, que é o número cromático deste 
grafo. 
 
 
K3,3: K5: 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
30 
1.5.11 Grafos isomorfos 
 
Neste item serão estudados os grafos isomorfos, conforme Conceito... (2014, p.29), 
como segue: 
 
 ISOMORFISMO 
 
 Sejam dois grafos G1(V1,A1) e G2(V2,A2). Um isomorfismo 
de G1 sobre G2 é um mapeamento bijetivo f: V1 ↔ V2 tal que (x,y) ∈ A1 se 
e somente se (f(x),f(y)) ∈ A2, para todo x,y ∈ V1. 
 
 Os grafos ao lado (a seguir) são isomorfos, pois há a função { (a,2), (b,1), 
(c,3), (d,4), (e,6), (f,5) } que satisfaz a condição descrita acima. (grifo 
nosso). 
 
 
 
 
 
 
 
Como visto neste item mostra os grafos isomorfos. 
 
Outro exemplo de isomorfismo poderia ser o seguinte conforme Wikipédia (2014, 
p.30), conforme figura a seguir: 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
31 
 
A identificação dos grafos isomórficos é algo muito complexo, conforme Gagnon 
(2014, p. 31) tem-se uma ideia, como segue: 
 
Um grafo completo com v vértices, escrito Kv, é um grafo simples onde 
todo par de vértices é ligado por uma aresta. Em outras palavras, um grafo 
completo é um grafo simples que contém o número máximo de arestas. 
 
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. Eis alguns exemplos de grafos 
isomorfos: 
 
Figura 1 
Para ver o isomorfismo dos grafos da figura 2, podemos utilizar a seguinte 
função: 
 
f(a) = 1, f(b) = 2, f(c) = 3, f(d) = 8, f(e) = 5, f(f) = 6, f(g) = 7, f(h) = 4. 
 
Imagine você pegando a imagem da direta (com números) da figura acima e 
girando ela para direita, tem-se a imagem semelhante a da esquerda (com letras) , seria 
esta uma forma de se identificar se são isomórficas. 
 
Separando as figuras se teria: 
 
 
 
 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
32 
Figura 07 – Divisão das imagens 
 
 
 
 
 
Fonte: Adaptado de Gagnon (2014, p. 32) 
 
 
Girando a imagem da direita (com números) teria-se aproximadamente esta 
imagem: 
 
Figura 08 – Nova imagem após o giro 
 
 
 
 
 
 
 
 
 
 
 
Fonte: O Autor 
 
Desta forma tem-se a seguinte sequência f(a) = 1, f(b) = 2, f(c) = 3, f(d) = 8, porque 
os demais ficaram encobertos, onde o 1 encobre o 6; o 2 encobre o 7; o 3 encobre o 4 e o 
8 encobre o 5,provando que eles são isomórficos. 
 
Posteriormente poderão ser tratado melhor sobre grafos isomórficos. 
 
1.5.12 Subconjunto de grafos 
 
 Neste item será estudado os subconjuntos (Internamente Estável) e os 
(Subconjunto Externamente Estável), conforme Conceito ... (2014, p.29), como segue: 
 
1 2 
3 8 
6 
5 
7 
4 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
33 
SCIE (Subconjunto Internamente Estável) (por vezes também conhecido 
como conjunto independente) 
 
Seja G(V,A) um grafo não orientado. Diz-se que S ⊂ V é um subconjunto 
internamente estável se dois vértices quaisquer de S nunca são adjacentes 
entre si. Para o grafo ao lado, são exemplos de SCIE os conjuntos: 
{2, 3}, {1, 4} e {2, 3, 4} 
Agora, se dado um SCIE S não existe um outro SCIE S' tal que S' ⊂ S, 
então S é dito ser um SCIE maximal. Para o grafo ao lado, são exemplos 
de SCIE maximais os conjuntos: {2, 3, 4}, {1, 6} e {4, 5} 
 
 SCEE (Subconjunto Externamente Estável) (por vezes também conhecido 
como conjunto absorvente) 
 Seja G(V,A) um grafo orientado. Diz-se que T ⊂ V é um subconjunto 
externamente estável se todo vértice não pertencente a T tiver pelo menos 
um vértice de T como sucessor. 
 Agora, se dado um SCEE S não existe um outro SCEE S' tal que S' ⊂ S, 
então S é dito ser um SCEE minimal. Para o grafo ao lado, são exemplos 
de SCEE minimais os conjuntos: {x2, x4, x6} e {x1, x5, x3} 
 Este conceito também pode ser aplicado a grafos não orientados, bastando 
que consideremos que todo vértice exterior a T deva ter como 
adjacente pelo menos um vértice de T. 
 
 
Sendo assim concluem-se as diversas características dos grafos, tendo-se assim uma 
visão mais clara do que representam os mesmos. 
 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
34 
1.6 Algoritmos importantes usando grafos 
 
Neste item será visto um algoritmo em detalhes que utiliza grafos que se destacam 
pela história, importância, mas obviamente existem muitos outros que poderão ser 
pesquisados. Neste caso aqui escolhido é o algoritmo do caminho mínimo, mas existem 
diversos outros. 
 
Sobre os problemas de caminho mínimo será mostrado o algoritmo a seguir, mas 
eles têm uma grande importância veja a figura: 
 
Figura 09 – Menor caminho 
 
 
 
Fonte: Wikipédia (2014, p. 34). 
 
Sendo neste caso acima o menor caminho o seguinte: 
 
O caminho mínimo entre D e E não é D-E, mas sim D-F-E, com uma distância 
de 14. D e F = 6 e F e E = 8, resultando 14. 
 
Conforme Wikipédia (2014, p. 34) “Na teoria de grafos, o problema do caminho 
mínimo consiste na minimização do custo de travessia de um grafo entre dois nós (ou 
vértices); custo este dado pela soma dos pesos de cada aresta percorrida”. 
 
Conforme Wikipédia (2014, p. 34) tem-se que, 
 
 Os algoritmos especializados em solucionar o problema do caminho 
mínimo são eventualmente chamados de algoritmos de busca de 
caminhos. Entre os algoritmos dessa classe, os mais conhecidos são: 
 
 Algoritmo de Dijkstra — Resolve o problema com um vértice-fonte em 
grafos cujas arestas tenham peso maior ou igual a zero. Sem reduzir o 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
35 
desempenho, este algoritmo é capaz de determinar o caminho mínimo, 
partindo de um vértice de início v para todos os outros vértices do grafo. 
 
 Algoritmo de Bellman-Ford — Resolve o problema para grafos com um 
vértice-fonte e arestas que podem ter pesos negativos. 
 
 Algoritmo A* — um algoritmo heurístico que calcula o caminho mínimo 
com um vértice-fonte. 
 
 Algoritmo de Floyd-Warshall — Determina a distância entre todos os 
pares de vértices de um grafo. 
 
 Algoritmo de Johnson — Determina a distância entre todos os pares de 
vértices de um grafo, pode ser mais veloz que o algoritmo de Floyd-
Warshall em grafos esparsos. 
 
 O problema de caminho mínimo é um dos problemas genéricos 
intensamente estudados e utilizados em diversas áreas como Engenharia 
de Transportes, Pesquisa Operacional, Ciência da Computação e 
Inteligência Artificial. Isso decorre do seu potencial de aplicação a 
inúmeros problemas práticos que ocorrem em transportes, logística, redes 
de computadores e de telecomunicações, etc. 
 
 Outras possibilidades de aplicação incluem quaisquer problemas 
envolvendo redes ou grafos em que se tenha grandezas (distâncias, tempo, 
perdas, ganhos, despesas) que se acumulem linearmente ao longo do 
percurso da rede. 
 
 Um problema relacionado é o Problema do Caixeiro-viajante, que consiste 
em determinar o caminho mais curto que passa exatamente uma vez por 
cada vértice e retorna ao vértice de partida. Este é um problema NP-
Completo, para os quais não há uma solução eficiente. (Grifo nosso) 
 
Neste estudo será visto o algoritmo de Algoritmo de Dijkstra, como segue: 
 
1.6.1 Algoritmo de Dijkstra 
 
Conforme se sabe Dijkstra foi um grande cientista da computação em meados dos 
anos 50, como segue: 
 
Conforme Wikipédia (2014, p. 34), tem-se: 
 
 O algoritmo de Dijkstra, concebido pelo cientista da computação holandês 
Edsger Dijkstra em 1956 e publicado em 1959, soluciona o problema do 
caminho mais curto num grafo dirigido ou não dirigido com arestas 
de peso não negativo, em tempo computacional O([m+n]log n) onde m é 
o número de arestas e n é o número de vértices. O algoritmo que serve 
para resolver o mesmo problema em um grafo com pesos negativos é o 
algoritmo de Bellman-Ford, que possui maior tempo de execução que o 
Dijkstra. 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
36 
 
 O algoritmo de Dijkstra assemelha-se ao BFS, mas é um algoritmo 
guloso, ou seja, toma a decisão que parece ótima no momento. Para a 
teoria dos grafos uma "estratégia gulosa" é conveniente já que sendo P 
um menor caminho entre 2 vértices U e V, todo sub-caminho de P é um 
menor caminho entre 2 vértices pertencentes ao caminho P, desta forma 
construímos os melhores caminhos dos vértices alcançáveis pelo vértice 
inicial determinando todos os melhores caminhos intermediários. Nota: 
diz-se 'um menor caminho' pois caso existam 2 'menores caminhos' 
apenas um será descoberto. 
 
 O algoritmo considera um conjunto S de menores caminhos, iniciado 
com um vérticeinicial I. A cada passo do algoritmo busca-se nas 
adjacências dos vértices pertencentes a S aquele vértice com menor 
distância relativa a I e adiciona-o a S e, então, repetindo os passos até 
que todos os vértices alcançáveis por I estejam em S. Arestas que ligam 
vértices já pertencentes a S são desconsideradas. 
 
Conforme Wikipédia (2014, p. 34), a aplicabilidade poderia ser a seguinte: 
 
 Um exemplo prático do problema que pode ser resolvido pelo algoritmo 
de Dijkstra é: alguém precisa se deslocar de uma cidade para outra. Para 
isso, ela dispõe de várias estradas, que passam por diversas cidades. Qual 
delas oferece uma trajetória de menor caminho? 
 
Sendo assim tem-se uma ideia boa para que serve o algoritmo de Dijkstra. 
 
O algoritmo seria o seguinte, conforme Wikipédia (2014, p. 35), seguindo os 
seguintes passos: 
 1º passo: iniciam-se os valores: 
 
 para todo v ∈ V[G] 
 d[v]← ∞ 
 π[v] ← -1 
 d[s] ← 0 
 
 V[G] é o conjunto de vértices(v) que formam o Grafo G. d[v] é o vetor de 
distâncias de s até cada v. Admitindo-se a pior estimativa possível, o 
caminho infinito. π[v] identifica o vértice de onde se origina uma conexão 
até v de maneira a formar um caminho mínimo. 
2º passo: temos que usar o conjunto Q, cujos vértices ainda não contém o 
custo do menor caminho d[v] determinado. 
 
 Q ← V[G] 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
37 
3º passo: realizamos uma série de relaxamentos das arestas, de acordo 
com o código: 
 
 enquanto Q ≠ ø 
 u ← extrair-mín(Q) //Q ← Q - {u} 
 para cada v adjacente a u 
 se d[v] > d[u] + w(u, v) //relaxe (u, v) 
 então d[v] ← d[u] + w(u, v) 
 π[v] ← u 
 Q ← Q ∪ {v} 
 
w(u, v) é o peso(weight) da aresta que vai de u a v. 
u e v são vértices quaisquer e s é o vértice inicial. ffd extrair-mín(Q), pode 
usar um heap de mínimo ou uma lista de vértices onde se extrai o 
elemento u com menor valor d[u]. 
No final do algoritmo teremos o menor caminho entre s e qualquer outro 
vértice de G. O algoritmo leva tempo O(m + n log n) caso seja usado 
um heap de Fibonacci, O(m log n) caso seja usado um heap binário e 
O(n²) caso seja usado um vetor para armazenar Q. 
 
Na sequência será mostrado um esquema do algoritmo e um link para poder ver em 
tempo real como ele funciona. 
 
Veja a figura a seguir: 
 
Figura 10 – Dinâmica do algoritmo de Dijkstra 
 
Fonte: Adaptado de Wikipédia (2014, p. 36) 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
38 
A figura acima tem o resultado final, mas veja a animação no link abaixo. 
http://pt.wikipedia.org/wiki/Algoritmo_de_Dijkstra 
 
O funcionamento é o seguinte: 
 
Observando o grafo acima se tem um conjunto de vértices variando de 1 a 6 e 
diversas arestas valoradas como valores nas distâncias. 
 
Partindo-se do vértice 1 observa-se que se tem ligação com o 2, 3 e o 6. O menor 
caminho é o de valor 7 então ele vai até ali, que é o vértice 2. 
 
Figura 11 – Dinâmica do algoritmo de Dijkstra 
 
Fonte: Adaptado de Wikipédia (2014, p. 36) 
 
No vértice 2 observa-se que se tem ligação com o 3 e o 4. O menor caminho é o de 
valor 10 então ele vai até o vértice 3. 
 
Figura 12 – Dinâmica do algoritmo de Dijkstra 
 
Fonte: Adaptado de Wikipédia (2014, p. 37) 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
39 
Estando-se no vértice 3 observa-se que se tem ligação com o 4 e o 6. O menor 
caminho é o de valor 2 então ele vai até o vértice 6. 
 
Figura 13 – Dinâmica do algoritmo de Dijkstra 
 
Fonte: Adaptado de Wikipédia (2014, p. 37) 
 
Estando no vértice 6 observa-se que é o final e ai termina o caminho, pois os 
vértices vão de 1 até 6, não tendo sentido ele retroceder indo ao 4 ou 5. 
 
Figura 14 – Dinâmica do algoritmo de Dijkstra 
 
Fonte: Adaptado de Wikipédia (2014, p. 38) 
 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
40 
Como visto este algoritmo pode ser resolvido desta forma, observando o menor 
caminho, analisando se os mesmos são positivos é claro, como já foi explicado no início. 
 
1.7 Usabilidade com Bancos de dados orientados a grafos. 
 
Um dos motivos de se estudar grafos é a aplicabilidade em bases de dados tanto 
relacionais, orientadas a objetos e até mesmo em outras formas como arquivos de dados 
que não possuem um gerenciador para auxiliar e são pouco usados. 
 
Mas existem bancos de dados orientados a grafos e isto é uma realidade. Na internet 
fazem uma comparação da seguinte forma: 
 
Bancos de dados relacionais foram criados em 1970 aproximadamente e 
 
Bancos de dados orientados a grafos vêm de 1736 aproximadamente com o 
matemático Euler. 
 
Matemático que já foi citado anteriormente, como sendo o pioneiro na teoria dos 
grafos. 
 
Mas é claro que é só uma brincadeira!!!. 
 
Conforme Sato (2014, p. 40) cita que, 
 
É normal, quando falamos de banco de dados, lembrarmos 
primeiramente de bases relacionais, do tipo SQL. Uma base relacional 
possui a tabelas, colunas, tuplas (linhas), chaves e relacionamentos. 
Quando temos um relacionamento entre uma tabela e outra, uma das 
tabelas possui a indicação de foreign key, chave estrangeira. Quando 
possuímos então o chamado Many to Many (muito para muito) colocamos 
uma terceira tabela ligando às outras duas e seus relacionamentos. 
 
Em um banco de dados de grafos, relacionamentos são mais naturais. 
Temos as entidades chamadas de vértices (ou node) que são ligadas entre 
elas pelas arestas (ou relationships) cada um podendo guardar dados entre 
os relacionamentos e cada relacionamento pode ter uma direção. (Grifo 
nosso). 
 
Como visto com grafos os relacionamentossão mais naturais até pela sua forma de 
existir, pois veja se eu tenho um amigo chamado João e ele tem um amigo chamado 
Pedro, que tem uma amiga chamada Ana, que tem .... e assim vai o número de 
relacionamentos observando que eu também posso ser amigo de todos eles ou de alguns 
deles, formando uma grande rede, que hoje são as redes sociais. 
 
Prestando bem atenção quando se entra numa rede social muitas vezes vêm imagens 
de pessoas que a princípio não as conhecemos, mas nossos amigos as conhecem e elas 
direta ou indiretamente estão interligadas a nós e isto são bases de dados orientadas a 
grafos. 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
41 
Conforme Sato (2014, p. 40) a sua representação poderia ser a seguinte: 
 
Figura 15 – Ideia de relacionamentos de banco de dados em grafos 
 
Fonte: Sato (2014, p.41) 
 
Como visto os relacionamentos são muitos entre as bolas vermelhas, podendo umas 
se relacionar com quase todas de forma direta ou indiretamente. 
 
Conforme Sato (2014, p. 41) a ideia é a seguinte, 
 
 A imagem mostra um exemplo da ideia de grafos. As esferas vermelhas 
são os vértices e as arestas seus relacionamentos. Apesar de todos aqui 
possuírem a indicação “relaciona”, cada relacionamento pode guardar 
dados diferentes sobre o relacionamento. Por exemplo: no twitter 
podemos ligar uma pessoa a outra pelo relacionamento de seguir. 
Podemos guardar junto a data de início da relação e a pessoa pode seguir 
de volta. Podemos também ter vértices de outros tipos, como tweets. Uma 
pessoa se relaciona a um tweet escrevendo ele ou dando RT. 
 Baseado na teoria de grafos, essas bases são um tipo dentro do mundo das 
bases noSQL. Ao pensar em noSQL já lembramos que esses são bancos 
mais rápidos (potencialmente menos seguros) e fáceis de escalar. A 
velocidade de se comparar um banco de dados relacional com um banco 
de dados de grafos vem na hora de se comparar uma busca cheia de joins 
index em um banco SQL e a simplicidade de se buscar relacionamentos 
em grafos. 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
42 
Na verdade as possibilidades são muitas em relação a bancos de dados orientados a 
grafos e por isso é uma vasta área a ser explorada atualmente. 
 
Nos bancos de dados orientados a grafos os elementos são basicamente os vértices e 
as arestas, como cita Sato (2014, p. 42), 
 
Itens de um banco de dados de Grafos 
 
Vértice: 
 
Também pode ser chamado de nó é a nossa unidade de dados, um 
conjunto de propriedades do tipo chave valor que representam uma 
entidade. Um exemplo seria um usuário o Twitter: 
 
nome: “Priscila Sato” 
arroba: “MayogaX” 
 
Aresta: 
 
São os nossos relacionamentos. Eles ligam os vértices por meio de uma 
rede semântica. Uma aresta pode possuir um sentido, uma orientação e, se 
necessário, dados sobre esse relacionamento. Exemplo baseado no 
Twitter: vértice “Priscila” segue o vértice “Lucas” desde 2012. “Priscila” 
e “Lucas” são vértices ligados pelo relacionamento “segue” que possui 
um sentido: do primeiro ao segundo, e possui também dados: a data de 
início do relacionamento. (Grifo Nosso). 
 
São elementos simples que os bancos de dados orientados a grafos possuem como: 
vértices e arestas. 
 
A autora Sato (2014, p. 42) cita, 
 Como manipulo acesso a dados em bases de dados de grafos? 
 
A maioria das bases de dados de grafos disponibilizam uma API REST 
para você poder manipular os dados. Algumas feitas em java 
disponibilizam um meio amigável para acessar suas classes e fazer buscas 
em suas bibliotecas. No caso de Neo4J, você pode usar uma linguagem de 
query específica chamada cypher. 
 
Existe também o BrightstarDB que possui uma lib que eles chamam de 
Entity Framework para noSQL. (Grifo Nosso). 
 
Como visto é amplo à forma de manipulação de dados com os bancos de dados 
orientados a grafos. 
 
Conforme Sato (2014, p. 43) os principais bancos de dados orientados a grafos são 
os seguintes: 
 
 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
43 
Exemplos de banco de dados de grafos existentes: 
 
AllegroGraph 
ArangoDb 
Bitsy (java) 
BrightstarDB (feito para .Net) 
DEX (possui api .Net e roda em windows) 
Filament 
InfiniteGraph 
InfoGrid 
HyperGraphDb 
Oracle Spatial 
Titan 
Neo4J (provavelmente o mais famoso de todos). (Grifo Nosso). 
 
Pois bem, ai fica uma pergunta: Porque os Bancos de dados orientados a grafos não 
são tão difundidos quanto os relacionais, por exemplo? 
 
Não se pode afirmar, mas o lado comercial ainda fala mais alto hoje em dia mesmo 
sendo na área de computação e mesmo vendo que eles são muito uteis para situações tão 
atuais como redes sociais, sistemas de recomendação e etc. 
 
1.7.1 Aplicabilidade dos Bancos de dados que usam grafos 
 
Muitas são as aplicabilidades dos bancos de dados orientados a grafos destacando-se 
atualmente as redes sociais, bancos de dados geográficos (Ex: Google Maps), dentre outras, 
como sistemas de recomendações em e-commerce em geral. 
 
Mas conforme Sato (2014, p. 43) vem a pergunta: 
 
 Como fazer um sistema de recomendações simples sem usar tanta 
complexidade? 
 
 A resposta é usar uma base de dados de grafos. Podemos usar o número 
de relações para classificar um item para ser indicado. Por exemplo, três 
itens, um A, um B, e um C possuem ligações com usuários do tipo 
“curtiu”. Se muita gente curtiu produto A e C ao mesmo tempo, ao pegar 
um único usuário que curtiu item A e formos sugerir um novo item, 
vamos sugerir o item B ou o item C? O C, né? Porque quem gosta de A 
tem um gosto parecido com quem gostou de C. 
 
 Para isso facilita usar banco de dados de grafos. Claro que você pode usar 
algoritmos mais complexos para misturar uma base de grafos com uma 
classificação de conteúdo, por exemplo. 
 
A aplicabilidade é a seguinte conforme Sato (2014, p. 43), 
 
Você conhece sistemas de recomendações, são itens básicos em e-commerces. A 
Amazon virou referencia em e-commerce e um dos motivos foi a recomendação 
Prof. Romário Lopes Alcântara - Unijuí - Universidade de Ijuí - Curso de Ciência da Computação 
Estrutura de Dados II - Capitulo 1 - Introdução a Grafos 
(EDII_C1_Introdução_Grafos) 
44 
de produtos. O Google também é ótimo nisso, com base nas suas pesquisas 
anteriores e gostos pessoais ele altera a ordem dos resultados