Teoria dos Grafos - Parte 1

Prévia do material em texto

TEORIA DOS GRAFOS 
AULA 1 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Prof. Guilherme Augusto Pianezzer 
 
 
2 
CONVERSA INICIAL 
A teoria dos grafos é uma área da matemática que se expandiu com base 
em um problema clássico conhecido como as sete pontes de Konigsberg. A 
solução do problema, proposta pelo matemático suíço Leonard Euler, levou ao 
desenvolvimento dessa grande área, conhecida como teoria dos grafos. Hoje, 
as aplicações dessa área são desde a determinação das melhores rotas de 
entrega de produtos até modelos de reconhecimento de padrões de grandes 
volumes de informação. 
TEMA 1 – O PROBLEMA DAS SETE PONTES DE KONISGBERG 
A teoria dos grafos se desenvolveu com base em um problema muito 
interessante e atual que foi estudado no século XVIII. Vejamos a característica 
desse problema. 
1.1 O problema das sete pontes de Konigsberg 
Konigsberg era uma cidade que, no século XVIII, possuía um conjunto de 
sete pontes que cruzavam o famoso rio Pregel. As pontes eram essenciais, dado 
que conectavam duas ilhas entre si e as ilhas com as margens, conforme Figura 1. 
Figura 1 – Pontes de Konigsberg 
 
Créditos: MERIAN-ERBEN – DP. 
O problema, hoje central para estudar as melhores rotas de entrega para 
empresas de logística, era saber se poderíamos cruzar as sete pontes sem 
passar duas vezes por qualquer uma delas. 
Bom, vamos pensar na solução. Antes, algo muito interessante: na 
matemática, sempre buscamos eliminar as informações em excesso que 
atrapalham a análise do problema. Observando o mapa da Figura 1, percebemos 
 
 
3 
que não precisamos representar os prédios, as casas e as avenidas, visto que o 
interessante do problema são as pontes e as ilhas. Logo, a Figura 2 simplifica a 
representação do problema. 
Figura 2 – Simplificação do mapa da cidade 
 
Créditos: MERIAN-ERBEN – DP; DP. 
Entretanto, embora a Figura 2 já seja uma forma simplificada do mapa da 
cidade, ainda possui muitas informações desnecessárias para a resolução do 
problema. Na verdade, se separarmos cada região por vértices e as pontes 
conectarem cada região por arestas, chegaremos à Figura 3, que é, finalmente, 
um grafo. 
Figura 3 – Construção do grafo 
 
Créditos: DP; Mark Foskey/Booyabazooka/DP. 
A representação formal utiliza a teoria dos conjuntos para escrever esses 
dois conjuntos. O conjunto 𝑽 formado pelas regiões (ilha ou margem) e o 
conjunto 𝑨 formado por triplas ordenadas, indicando a ponte que liga uma região 
à outra. Então, considerando 
https://en.wikipedia.org/wiki/User:Mark_Foskey
https://en.wikipedia.org/wiki/User:Booyabazooka
 
 
4 
𝑽 = {𝑨, 𝑩, 𝑪, 𝑫} 
Percebemos que existem 4 regiões distintas, sendo 2 ilhas e 2 margens. 
O conjunto 𝑬 (arestas) é dado por: 
𝑬 = {(𝑨, 𝑪, 𝒄), (𝑨, 𝑪, 𝒅), (𝑨,𝑩, 𝒂), (𝑨, 𝑩, 𝒃), (𝑨,𝑫, 𝒆), (𝑩, 𝑫, 𝒇), (𝑪,𝑫,𝒈)} 
Note que, por exemplo, a tripla ordenada (𝑨, 𝑪, 𝒄) indica que existe uma 
ponte 𝒄 que conecta 𝑨 com 𝑪, enquanto a tripla ordenada (𝑨,𝑩, 𝒂) indica que 
existe uma ponte 𝒂 que conecta 𝑨 com 𝑩. 
Com essa terminologia, encontrar a solução do problema significa 
atravessar todas as arestas uma única vez e retornar, então, ao vértice de 
origem. Note que estamos buscando um caminho fechado, em teoria dos grafos 
conhecido como caminho de Euler. Nesse caso, Euler chamou os grafos que 
possuem essa característica de grafo de Euler. 
Assim, a solução do problema consiste em verificar o grau dos vértices 
para garantir que se trata de um grafo de Euler. O teorema que o matemático 
mostrou e que vamos estudar mostra que somente conjuntos de vértices de grau 
par geram grados de Euler. Isso porque se o número de arestas for ímpar, em 
pelo menos um dos vértices, quando entrarmos em uma aresta, não 
encontraremos outra aresta para sair, isto é, precisaremos cruzar o mesmo 
vértice para sair ao menos mais uma vez. Mesmo que Euler tenha concluído que 
o problema das sete pontes não tem solução, esse estudo deu o pontapé inicial 
para o desenvolvimento da teoria. 
TEMA 2 – ESQUEMATIZANDO E ROTULANDO UM GRAFO 
Do século XVIII até os tempos atuais, vários estudos na área 
impulsionaram a teoria dos grafos. A grande diferença entre os estudos daquela 
época para os de hoje é que utilizamos o computador para resolver a maior parte 
dos problemas. É por isso que dedicaremos um tempo para compreender como 
modelar computacionalmente esse tipo de situação. 
2.1 Lista de adjacência 
No problema das sete pontes de Konigsberg, verificamos que um grafo é 
composto por arestas conectadas por vértices. Quando um vértice está 
 
 
5 
conectado por uma aresta a um outro vértice, dizemos que são vértices 
adjacentes. Existem situações em que a aresta não é direcionada: tanto faz sair 
do vértice 𝑨 ao vértice 𝑩 e vice-versa, mas existem outros casos em que isso 
não será verdadeiro. Nesse caso, definiremos um grafo orientado. 
Veja, por exemplo, o grafo da Figura 4, seguido do Quadro 1, que contém 
a lista de vértices adjacentes. 
Figura 4 – Grafo composto por sete vértices numerados 
 
Quadro 1 – Lista de adjacência 
Vértice Vértice adjacente 
1 2,4 
2 1,3,4 
3 2,4 
4 1,2,3,5 
5 4,6 
6 5,7 
7 6 
Nesse caso, é fácil perceber que o Quadro 1 apresenta uma lista contendo 
o vértice adjacente, conhecida como lista de adjacência do grafo. Pouca coisa 
muda quando tratamos de um grafo orientado. 
 
 
 
6 
Figura 5 – Grafo orientado composto por seis vértices numerados 
 
Quadro 2 – Lista de adjacência 
Vértice Vértice adjacente 
1 2,4 
2 1,3,4 
3 2,4 
4 1,2,3,5 
5 4,6 
6 5,7 
2.2 Matriz de adjacência 
Essa representação com base na lista de adjacência é uma das mais 
simples que existem. Entretanto, há casos em que as arestas também possuem 
valor. Pense na situação representada pela Figura 4 ou pela Figura 5. Ambas 
podem representar as rotas possíveis entre várias cidades ou o direcionamento 
de um processo industrial qualquer. Em qualquer um desses casos, a rota ou o 
processo pode ter custos que diferem o valor da aresta dada entre dois vértices 
quaisquer. 
Se precisamos valorar uma aresta, podemos utilizar uma matriz quadrada 
cuja ordem é a quantidade de vértices para fazer essa representação. Veja o 
que ocorre na representação do grafo da Figura 6. 
 
 
 
7 
Figura 6 – Grafo composto por cinco vértices e arestas valoradas 
 
Esse grafo pode representar o custo (tempo, distância ou dinheiro) para 
se movimentar entre duas cidades adjacentes. Como o grafo não é orientado, 
supomos que o valor é o mesmo para quem está indo e para quem está vindo. 
Sua representação computacional se dá pela matriz de adjacência. Nesse 
caso, temos: 
𝑨 = [𝒂𝒊𝒋]𝒏
 
𝑨 =
[
 
 
 
 
𝟎 𝟏 𝟑 𝟎 𝟑
𝟏 𝟎 𝟐 𝟎 𝟐
𝟑 𝟐 𝟎 𝟑 𝟎
𝟎 𝟎 𝟑 𝟎 𝟎
𝟑 𝟏 𝟎 𝟎 𝟎]
 
 
 
 
 
Note, por exemplo, que 
𝒂𝟏𝟐 = 𝒂𝟐𝟏 = 𝟏 
Indica-se o custo 𝟏 entre os vértices 𝟏 e 𝟐. Como o grafo é não orientado, 
essa característica faz da matriz 𝑨 simétrica. Inclusive, ao programar esse tipo 
de matriz, é interessante utilizar esse tipo de característica para economizar na 
escrita de dados, especialmente na construção de base de dados enormes. 
Perceba também que: 
𝒂𝟏𝟏 = 𝒂𝟐𝟐 = ⋯ = 𝒂𝟓𝟓 = 𝟎 
Indicando que um vértice não pode ser levado nele mesmo. Em alguns 
casos isso será possível: esses são os conhecidos laços. 
Analisando a matriz de adjacência e a lista de adjacência, talvez você 
imagine que a primeira seja capaz de descrever todo o modelo. Entretanto, 
 
 
8 
existem casos dinâmicos que possuem ligações, mas com peso 0, como é o 
caso de 𝒂𝟒𝟏 = 𝒂𝟏𝟒 nesse problema. Precisamos definir, computacionalmente, 
ambas as estruturas em todos os problemas. 
No caso da Figura 7, observamos um grafo orientado. 
Figura 7 – Grafo não completo, orientado, formado por quatro arestas 
 
Como a matriz não será simétrica nesse caso, precisamos nos atentar, 
lançando todas as informações. Nesse caso,a matriz de adjacência será de 
quarta ordem, dada por: 
𝑨 = [
𝟎 𝟑 𝟑 𝟕
𝟓 𝟎 𝟏 𝟎
𝟏 𝟕 𝟎 𝟏
𝟎 𝟎 𝟓 𝟎
] 
2.3 Matriz de incidência 
A matriz de adjacência que criamos tem em suas linhas e colunas vértices. 
Por isso é considerada uma matriz vértice-vértice. A matriz de incidência tem em 
suas linhas vértices, mas em suas colunas, arestas, sendo, portanto, uma matriz 
vértice-aresta (ou vértice-ligação). 
Os elementos da matriz de incidência podem assumir 3 valores: 0, no caso 
em que o vértice não indica na aresta; 1, se o vértice índice na aresta; e 2, se for 
um laço. Existem outras formas de programar e definir a matriz de incidência, de 
forma que você deve ter cuidado com o que foi proposto por cada 
autor/programador. 
 
 
 
9 
Figura 8 – Grafo composto por quatro arestas, com arestas direcionadas, não 
direcionadas e laços 
 
Nesse caso, nossa matriz de incidência será 𝑩 = [𝒃𝒊𝒋]𝒎×𝒏 em que 𝒎 é a 
quantidade de vértices, enquanto 𝒏 é a quantidade de arestas. Assim, 
chegaremos à matriz: 
𝑩 = [
𝟎 𝟎 𝟎 𝟏 𝟏
𝟏 𝟎 𝟎 𝟎 𝟏
𝟏 𝟐 𝟏 𝟎 𝟎
𝟎 𝟎 𝟏 𝟏 𝟎
] 
Leia com cuidado para reconhecer cada um dos valores. 
TEMA 3 – ÁLGEBRA DE GRAFOS 
Para tratarmos de forma adequada de grafos, precisamos determinar 
alguns termos que vão surgir ao longo da nossa discussão. Separamos os 
principais aqui, embora outros ainda serão definidos. 
3.1 Ordem e tamanho 
Você percebeu que o uso de matrizes é constante para representar os 
grafos computacionalmente. É por isso que a ordem de um grafo relembra a 
ordem da matriz de adjacência: representa a quantidade de vértices que um 
grafo possui. O tamanho do grafo, por sua vez, representa a quantidade de 
arestas ligações que possui. 
3.2 Grafo complementar e subgrafo 
 
 
10 
Você também deve ter percebido que usamos a teoria dos conjuntos para 
fazer a representação algébrica dos grafos. Então, o termo grafo complementar 
vem de teoria dos conjuntos quando imaginamos o complementar de um 
conjunto: são aqueles elementos que faltam no conjunto dado. 
Ao considerar o conjunto de arestas 𝑬 de um grafo 𝑮 dado, o grafo 
complementar, �̅�, é aquele que possui os mesmos vértices, mas todas aquelas 
arestas que não estão em 𝑮. Note que não utilizamos os arcos no conjunto 
universo, dado alguns casos que serão pontuados, como o uso das cadeias de 
Markov, além de que o conjunto universo são as arestas possíveis para os 
vértices contidos no problema. 
Figura 9 – Grafo 𝑮 à esquerda e seu grafo complementar à direita 
 
Também é da teoria do conjunto que extraímos o conceito de subgrafo. 
Um grafo 𝑮 = (𝑽, 𝑬), portanto, composto dos vértices 𝑽 e das arestas 𝑬 terá um 
subgrafo 𝑯 = (𝑽𝟏, 𝑬𝟏) sempre que 𝑽𝟏 ⊂ 𝑽 e 𝑬𝟏 ⊂ 𝑬. Note que um subgrafo não 
precisa ter todas as arestas nem todos os vértices do grafo dado. Entretanto, 
quando o grafo possui todos os vértices, mas não necessariamente todas as 
arestas, é definido como um subgrafo abrangente. 
Figura 10 – Grafo 𝐺 à esquerda e um de seus subgrafos à direita 
 
 
 
11 
TEMA 4 – VIZINHANÇA, PERCURSOS, FECHO E ISOMORFISMO 
Neste tópico, vamos continuar com algumas definições que vão nos 
auxiliar a compreender melhor características que diferenciam um grafo de outro 
ou os tornam semelhantes: trataremos de vizinhança, percurso, fecho e 
isomorfismo. 
4.1 Vizinhança 
O conceito de vizinhança nos remete à proximidade entre um vértice e 
outro. É por isso que em um vértice não orientado, dado por 𝑮 = (𝑽,𝑬), temos 
que 𝑨 será vizinho de 𝑿 sempre que existir no grafo 𝑮 uma aresta (𝑨, 𝑿, 𝒆) 
(lembra das triplas ordenadas?). Então, a vizinhança aberta de 𝑿, 𝑵(𝒙), 
representa o conjunto de vértices que são vizinhos de 𝑿 e pertencem a 𝑮: 
𝑵(𝒙) = {𝒀; (𝒙, 𝒀, 𝒆) ∈ 𝑬 𝐩𝐚𝐫𝐚 𝐚𝐥𝐠𝐮𝐦 𝒆} 
Nada nos impede também de definir a vizinhança de um conjunto de 
vértices, 𝑪, denotada por 𝑵(𝑪). Todos os elementos que pertencem a 𝑵(𝑪) 
serão, por definição, externos a 𝑪, ou seja, conterão apenas os vértices que são 
vizinhos a pelo menos um vértice de 𝑪 e que não pertencem a 𝑪. 
Figura 11 – Grafo composto por seis vértices 
 
Veja, por exemplo, qual é o conjunto 𝑵(𝟏), isto é, a vizinhança aberta do 
vértice 𝟏: 𝑵(𝟏) = {𝟐, 𝟑, 𝟒}, enquanto, por exemplo, 𝑵(𝟐, 𝟒) = {𝟏, 𝟑, 𝟓, 𝟔}. Embora 
2 e 4 sejam vizinhos, não pertencem à sua própria vizinhança aberta. Quando 
necessários, discutiremos a vizinhança fechada. Nesse caso, seria dada por 
 
 
12 
𝑵[𝟐, 𝟒] = {𝟏, 𝟐, 𝟑, 𝟒, 𝟓, 𝟔}. Note também, revendo a lista de adjacência, que ela 
contém a vizinhança de cada um dos vértices do grafo dado. 
4.2 Grau e semigraus 
A definição do grau de um vértice (não confundir com grau do grafo) difere, 
ligeiramente, ao tratar de grafos não orientados e grafos orientados. No caso de 
grafos orientados, a quantidade de vizinhos de um vértice é o grau do vértice. 
Ao observar a Figura 11, notamos que 𝒅(𝟏) = 𝟑, enquanto 𝒅(𝟔) = 𝟐. 
A ligeira diferença em grafos orientados é que diferenciamos o semigrau 
exterior 𝒅∗(𝒗) dado pelo número de sucessores do vértice 𝒗 dado, isto é, a 
quantidade de arestas que saem do vértice 𝒗 dado, enquanto definimos o 
semigrau interior 𝒅′(𝒗) dado pelo número de antecessores do vértice 𝒗 dado, 
isto é, a quantidade de arestas que entram no vértice 𝒗 dado. 
Figura 12 – Grafo composto por seis vértices 
 
Na Figura 12, observamos que o vértice 2 possui 3 antecessores e 
nenhum sucessor. Dessa forma, 𝒅∗(𝟐) = 𝟎, enquanto 𝒅′(𝟐) = 𝟑. O grau do 
vértice 𝟐 continua sendo dado como 𝒅(𝟐) = 𝟑. No caso do vértice 𝟑, temos que 
𝒅∗(𝟑) = 𝟐,𝒅′(𝟑) = 𝟐,𝒅′(𝟑) = 𝟐. 
Em alguns casos, é interessante definir também o grau máximo de um 
grafo 𝑮, denotado por ∆(𝑮), e o seu grau mínimo 𝜹(𝑮). Tendo todos os 
vértices o mesmo grau, o grafo será chamado de grafo 𝒌 −regular. 
4.3 Percursos 
Além de o vértice ser adjacente, podemos definir que as ligações são 
adjacentes quando partilham o mesmo vértice. Existem vários tipos de percursos 
 
 
13 
(ou cadeias) disponíveis, todos são identificados como uma coleção de vértices 
sequencialmente adjacentes. Aqui existem várias classificações de percursos 
que vão aparecer ao longo da teoria. Por exemplo, um caminho é entendido 
como um percurso em que os arcos possuem um início e um fim. Um percurso 
será simples sempre que não repetir ligações ou elementar sempre que não 
repetir vértices. Ao definir um percurso elementar fechado, estamos definindo 
um ciclo, e um caminho elementar fechado será considerado um circuito. 
4.4 Fecho transitivo 
O conceito de fecho transitivo advém do conceito de transitividade em 
matemática. Afinal, se você deseja ir até Salvador, saindo de Curitiba, existe um 
ônibus que vai até São Paulo e de lá até Salvador. Logo, você pode ir de Curitiba 
até Salvador mesmo que não haja um ônibus que vá direto nessa direção. Isso 
porque essa é uma propriedade transitiva. Nesse caso, se considerarmos essas 
cidades como vértices de um grafo maior (o mapa do Brasil contendo suas 
capitais), vamos concluir que Salvador é atingível ao se partir de Curitiba. 
Ao levantarmos todos os vértices atingíveis de 𝒗 ∈ 𝑽, definimos o conjunto 
chamado de fecho transitivo de 𝒗 em 𝑮 e denotado por 𝑹(𝒗). Aqui, existem 
duas subclassificações quando tratamos de um grafo orientado: o fecho 
transitivo direto 𝑹∗(𝒗) contém todos os vértices sucessores atingíveis do vértice 
dado, enquanto o fecho transitivo inverso 𝑹′(𝒗) possui todos os vértices 
antecessores atingíveis do vértice dado. Perceba que o conceito de fecho amplia 
o conceito de vizinhança ao considerar os diversos percursos em um grafo. 
Figura 13 – Grafo composto por oito vértices 
 
Veja o grafo da Figura 13. Note, inicialmente, o vértice 1. Partindo dele, é 
possível atingir o vértice 𝟐 e 𝟒, suas vizinhanças, ou ainda atingir os vértices 
 
 
14 
𝟑, 𝟓, 𝟔. Entretanto,não há um percurso saindo de 1 e chegando a 7 ou a 8. O 
fecho transitivo (direto) de 𝟏 é dado por 𝑹(𝟏) = {𝟐, 𝟑, 𝟒, 𝟓, 𝟔}. 
Aqui também podemos definir o fecho transitivo direto e o inverso. Por 
exemplo, veja o caso do vértice 𝟓. 𝑹∗(𝟓) = 𝟔, enquanto 𝑹′(𝟓) = {𝟏, 𝟐, 𝟑, 𝟒, 𝟕, 𝟖}, 
indicando que é possível chegar ao vértice 𝟓 partindo de qualquer vértice que 
não seja o vértice 6 ou ele mesmo. 
4.5 Isomorfismo de grafos 
Em matemática, isomorfismos surgem quando estruturas algébricas 
compartilham a mesma forma. 
Figura 14 – Dois grafos isomorfos compostos de cinco vértices 
 
Na Figura 14, tente diferenciar os dois grafos. Observando a forma, 
parece se tratar de estruturas diferentes. Entretanto, ambos possuem os 
mesmos cinco vértices, e existem as mesmas arestas entre cada vértice. Por 
isso são considerados grafos isomorfos. Ao tratar de alguma modelagem, o 
mesmo problema poderia gerar qualquer um desses dois grafos. 
Matematicamente, o teste para verificar isomorfismo depende da 
construção de uma função bijetora. Se você conseguir escrever uma função 
entre os vértices de cada um dos grafos que preserve as relações de adjacência, 
estará tratando do mesmo grafo, mesmo sendo, aparentemente, diferentes! 
TEMA 5 – CLASSIFICAÇÃO DE GRAFOS 
Para finalizar esta etapa, vejamos algumas classificações de grafos que 
vão aparecer nos algoritmos que estudaremos futuramente. 
5.1 Grafo simétrico 
 
 
15 
Definimos grafo orientado. Dados dois vértices, digamos 𝒗𝟏 e 𝒗𝟐 ∈ 𝑽 se 
existir (𝒗𝟏, 𝒗𝟐, 𝒆) ∈ 𝑬 e (𝒗𝟐, 𝒗𝟏, 𝒆) ∈ 𝑬 para todos os arcos existentes, então 
concluiremos que se trata de um grafo simétrico. Note, portanto, que um grafo 
simétrico é um grafo não orientado. 
5.2 Grafo completo 
Um grafo completo é entendido como um grafo em que cada um de 
seus vértices possui ligação com todos os outros vértices existentes. 
Figura 15 – Grafo completo de cinco vértices 
 
Na Figura 15, observamos um grafo completo. Note que não é necessário 
vincular as ligações dele com ele mesmo (os laços), e esse será o grafo universo 
para construirmos o grafo complementar já discutido. 
NA PRÁTICA 
Vamos usar a linguagem de programação Python para modelar nossos 
problemas. Nesta atividade prática, seremos convidados a lançar a lista de 
adjacência, a matriz de adjacência e a matriz de incidência de um grafo qualquer. 
Para isso, seguiremos o tutorial lançado pela página Algoritmos em Python nas 
referências bibliográficas para realizar essa tarefa. 
1. Realizar a representação explícita proposta pelo autor. 
2. Criar uma classe para representação dos grafos, conforme proposto pelo 
autor. 
3. Realizar a representação implícita proposta pelo autor. 
 
 
16 
É essencial que você aproveite essa oportunidade para aprender a 
instalar o Python (sugere-se o compliador Spyder, embora exista uma infinidade 
disponível na internet) e também a utilizar seus principais comandos. 
FINALIZANDO 
Conseguimos iniciar as principais modelagens de grafos. Em outro 
momento, começaremos a investigar as conexões entre grafos e suas 
peculiaridades com vistas a resolver problemas de minimização e otimização de 
caminhos. Tudo isso será feito computacionalmente. É por isso que você precisa 
aproveitar o início do estudo para conhecer a implementação básica de grafos 
em Python. 
 
 
17 
REFERÊNCIAS 
ALGORITMOS EM PYTHON. Representação de grafos. Disponível em: 
<https://algoritmosempython.com.br/cursos/algoritmos-python/algoritmos-
grafos/representacao-
grafos/#:~:text=A%20primeira%20%C3%A9%20chamada%20matriz,n%C3%B
Amero%20de%20v%C3%A9rtices%20do%20grafo>. Acesso em: 17 jan. 2023. 
BOAVENTURA NETTO, P. O.; JURKIEWICZ, S. Grafos: introdução e prática. 
2. ed. São Paulo: Blucher, 2017. Disponível em: 
<https://integrada.minhabiblioteca.com.br/books/9788521211327>. Acesso em: 
17 jan. 2023. 
GOLDBARG, M.; GOLDBARG, E. Grafos: conceitos, algoritmos e aplicações. 
Rio de Janeiro: GEN LTC, 2012. Disponível em: 
<https://integrada.minhabiblioteca.com.br/books/9788595155756>. Acesso em: 
17 jan. 2023. 
SPYDER. The Scientific Python Development Environmet. Disponível em: 
<https://www.spyder-ide.org/>. Acesso em: 17 jan. 2023.