Fundamentos da Matemática Discreta
Fundamentos da Matemática Discreta
net/publication/352648056
CITATIONS READS
0 7,144
1 author:
Alexandre L M Levada
Federal University of São Carlos
156 PUBLICATIONS 492 CITATIONS
SEE PROFILE
All content following this page was uploaded by Alexandre L M Levada on 29 September 2025.
28 de setembro de 2025
Prefácio
1
4. Relações: aborda relações binárias e suas propriedades (reflexividade, simetria, transitividade,
antissimetria), fundamentais para modelar estruturas em bancos de dados, linguagens formais,
autômatos e redes.
6. Relações de Ordem Parcial: explora ordens parciais e totais, Hasse diagrams e máximos/mí-
nimos. Essencial para organizar elementos em estruturas hierárquicas, como em sistemas de
arquivos e ordenações de tarefas.
10. Grafos e Fundamentos Básicos: apresenta grafos, multigrafos, laços, graus dos vértices, ca-
minhos e ciclos. Elementares para representação de redes e estruturas em algoritmos.
11. Árvores: estuda árvores, árvores binárias, folhas e propriedades estruturais. Essenciais para
algoritmos de busca, estruturas de dados e hierarquias.
13. Grafos Planares: discute planificação de grafos e o Teorema de Euler, úteis em redes elétricas,
circuitos e computação gráfica.
Espero que esta obra contribua para tornar o estudo da Matemática Discreta mais acessível, inte-
ressante e prazeroso, despertando no leitor o desejo de ir além e explorar as inúmeras possibilidades
que esta área oferece.
Bons estudos!
2
Sumário
1 Métodos de prova 5
1.1 Prova Direta . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
1.2 Prova por Contrapositiva . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Prova por Redução ao Absurdo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.4 Demonstrações do tipo se e somente se . . . . . . . . . . . . . . . . . . . . . . . . . 12
1.5 Demonstração por vacuidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.6 A conjectura de Goldbach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1.7 Considerações finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4 Relações 44
4.1 Considerações finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
5 Relações de equivalência 58
5.1 Considerações finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
7 Funções 83
7.1 Contando o número de funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
7.2 Propriedades de funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
7.2.1 Contagem de funções injetoras . . . . . . . . . . . . . . . . . . . . . . . . . 90
7.2.2 Contagem de funções sobrejetoras . . . . . . . . . . . . . . . . . . . . . . . 91
7.3 Composição de funções . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92
7.4 Considerações finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98
3
8 Somatórios 99
8.1 Representando somatórios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
8.2 Propriedades de somatórios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101
8.3 Considerações Finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
4
1 Métodos de prova
Os métodos de prova constituem a base do raciocínio matemático rigoroso e desempenham um
papel essencial tanto na Matemática quanto na Computação. Provar uma afirmação significa de-
monstrar, de maneira lógica e fundamentada, que ela é verdadeira em todos os casos possíveis. Esse
processo não apenas garante a validade de teoremas, mas também desenvolve a capacidade de argu-
mentação formal e a precisão no uso da linguagem, habilidades indispensáveis para qualquer cientista,
engenheiro ou programador. Em Computação, métodos de prova são aplicados, por exemplo, na ve-
rificação de algoritmos, na análise de corretude de programas, na definição de linguagens formais e
na fundamentação de estruturas abstratas como autômatos e sistemas lógicos.
Diferentes estratégias podem ser adotadas para conduzir uma prova, como os métodos direto,
por contrapositiva, por contradição, por indução e por vacuidade. A escolha do método adequado
depende da estrutura lógica da proposição e do conhecimento disponível. Dominar essas técnicas
é um passo fundamental para a construção do pensamento dedutivo e para o desenvolvimento da
autonomia intelectual necessária para resolver problemas complexos. Assim, o estudo dos métodos
de prova vai muito além de uma formalidade acadêmica: ele capacita o aluno a pensar com clareza,
justificar suas ideias com solidez e construir soluções robustas em ambientes computacionais.
Na matemática, conceitos como conjectura, teorema, lema e corolário representam diferentes
tipos de afirmações dentro de um sistema lógico, cada uma com um papel específico na construção
do conhecimento matemático:
• Conjectura: é uma proposição que se acredita ser verdadeira com base em observações, expe-
rimentos ou padrões identificados, mas que ainda não foi provada rigorosamente. Conjecturas
são frequentemente pontos de partida para investigações matemáticas. Um exemplo clássico
é a Conjectura de Goldbach, que afirma que todo número par maior que 2 é a soma de dois
números primos, ainda sem demonstração formal.
• Teorema: é uma proposição matemática que foi demonstrada com base em axiomas, definições
e teoremas anteriores. Uma vez provado, o teorema torna-se uma verdade incontestável dentro
do sistema lógico adotado. Teoremas são os principais resultados buscados na matemática.
• Lema: é um resultado auxiliar, geralmente mais simples, cuja função principal é ajudar na
prova de um teorema mais importante. Embora possa parecer menos relevante isoladamente, o
lema é muitas vezes indispensável para o encadeamento lógico de uma demonstração.
5
Do ponto de vista matemático, uma definição é uma sentença que estabelece com precisão o
significado de um termo ou conceito dentro de um determinado contexto teórico. Seu objetivo é
eliminar ambiguidades, especificando de forma clara e inequívoca os critérios que determinam se um
objeto ou estrutura possui determinada propriedade.
Ao contrário de um teorema, que precisa ser provado, uma definição é uma convenção adotada
como ponto de partida. Ela não é verdadeira nem falsa, é uma forma de dar nome e estrutura a ideias
matemáticas que queremos estudar. Por exemplo, ao definir que um número natural 𝑛 é par se existe
um número natural 𝑘 tal que 𝑛 = 2𝑘, estamos apenas escolhendo uma forma precisa de identificar os
números pares com base em uma propriedade específica.
Definições são fundamentais na matemática porque servem como blocos de construção conceitual:
a partir delas, é possível formular conjecturas, enunciar teoremas e construir provas com base em
regras bem estabelecidas.
A seguir, veremos diversas definições básicas sobre a teoria dos números.
Definição 5. Para todo 𝑛 ∈ N, 𝑛 é primo se e somente se 𝑛 > 1 e 𝑛 não tem divisor maior que 1,
exceto o próprio 𝑛.
Em alguns casos, é necessário mostrar que uma afirmação é falsa, o que, em geral, é bem mais
simples do que provar sua veracidade, pois basta encontrarmos um contra-exemplo. Considere a
seguinte proposição. Ela é verdadeira ou falsa?
∀𝑎, 𝑏 ∈ Z 𝑎2 = 𝑏2 → 𝑎 = 𝑏
(︀ )︀
(1)
É trivial provar que essa afirmação é falsa, bastando para isso considerar um caso em que 𝑎2 = 𝑏2
seja verdadeiro, mas 𝑎 = 𝑏 seja falso. Seja 𝑎 = 1 e 𝑏 = −1. Com isso, teremos um caso particular
para o qual a afirmação não é verdade. Isso é o suficiente para demonstrar que ela é falsa. Porém, para
provar que uma afirmação do tipo ∀𝑥 ∈ 𝑁 (𝑃 (𝑥) → 𝑄(𝑥)) é verdadeira, não basta selecionarmos um
ou mais casos e verificar que ela é verdadeira. Isso não é suficiente! Precisamos mostrar que ela é
verdadeira para todos os possíveis elementos do conjunto 𝑁 .
6
1.1 Prova Direta
A prova direta é uma das formas mais elementares e fundamentais de demonstrar a veracidade
de uma proposição matemática. Nesse método, parte-se da hipótese assumida como verdadeira e,
por meio de uma sequência de deduções lógicas válidas, chega-se à conclusão desejada. Trata-se de
um raciocínio do tipo “se p, então q”, em que cada passo é justificado com base em definições, pro-
priedades conhecidas, axiomas ou resultados previamente demonstrados. A simplicidade conceitual
da prova direta a torna uma ferramenta indispensável no aprendizado matemático, pois desenvolve a
clareza no raciocínio e o domínio sobre a estrutura lógica dos argumentos. É amplamente utilizada na
demonstração de propriedades numéricas, identidades algébricas, propriedades de conjuntos, funções
e estruturas discretas.
Outra definição importante é a que define o que são números racionais. Dizemos que um número
é racional se ele pode ser expresso pela divisão de 2 inteiros. De modo mais formal, temos a seguinte
definição.
Em alguns casos, para provar uma afirmação do tipo 𝑝 → 𝑞, não temos acesso direto a p. Nessas
situações, podemos utilizar uma lógica reversa (backtracking). O exemplo a seguir ilustra essa ideia.
Por exemplo, suponha que deseja-se provar que a média aritmética de dois números distintos é sempre
7
maior ou igual a média geométrica dos mesmos números. Note que sabemos onde queremos chegar,
mas não está claro de onde devemos partir. Neste caso, 𝑝 não é fornecido de maneira explícita.
Iniciamos definindo as médias aritméticas e geométricas como:
𝑥+𝑦
𝑚𝐴 = (2)
2
√
𝑚𝐺 = 𝑥𝑦 (3)
Podemos escolher alguns valores de 𝑥 e 𝑦 para verificar que aparentemente a média aritmética é
sempre maior ou igual que a geométrica.
√
• 𝑥 = 1 e 𝑦 = 3: 𝑚𝐴 = 2 > 𝑚𝐺 = 3
√
• 𝑥 = 2 e 𝑦 = 4: 𝑚𝐴 = 3 > 𝑚𝐺 = 8
√
• 𝑥 = 3 e 𝑦 = 5: 𝑚𝐴 = 4 > 𝑚𝐺 = 15
Como podemos provar que 𝑚𝐴 > 𝑚𝐺 para 𝑥 ̸= 𝑦? Vamos tentar partir da conclusão e ver onde
podemos chegar.
𝑥+𝑦 √
1. Iremos partir da eventual conclusão, ou seja, 2
> 𝑥𝑦.
(𝑥+𝑦)2
2. Elevando ambos os lados ao quadrado, temos 4
> 𝑥𝑦.
Note que (𝑥2 − 𝑦 2 ) > 0 é sempre verdadeiro para 𝑥 ̸= 𝑦, então, se invertermos os passos da prova
direta, ou seja, se partirmos de 6 e chegarmos em 1, fazendo os devidos ajustes (como somar 4𝑥𝑦
ao invés de subtrair), temos uma sequência de consequências lógicas válidas e portanto uma prova
direta.
Teorema 3 (Lema de Euclides). Seja 𝑝 ∈ N um número primo, tal que 𝑝 é um fator de 𝑎𝑏. Então, 𝑝 é
um fator de 𝑎 ou de 𝑏. Para 𝑎 = 𝑏, temos que, se 𝑝 divide 𝑎2 , então 𝑝 divide 𝑎.
1. Pelo Teorema Fundamental da Aritmética, sabemos que: "Todos os inteiros positivos maiores
que 1 possuem uma decomposição única em fatores primos".
8
1.2 Prova por Contrapositiva
A prova por contrapositiva é uma técnica fundamental em Matemática Discreta, frequentemente
utilizada para demonstrar implicações lógicas de forma indireta. Em vez de provar diretamente que
𝑝 → 𝑞, essa estratégia consiste em demonstrar a contrapositiva ¬𝑞 → ¬𝑝, que é logicamente equi-
valente à proposição original. Esse método é especialmente útil quando a negação das hipóteses ou
conclusões simplifica a argumentação, revelando estruturas mais acessíveis para a demonstração. Ao
dominar a contrapositiva, ampliamos nosso arsenal de ferramentas para abordar teoremas e problemas
discretos com maior versatilidade e clareza.
1. Iremos utilizar a prova por contrapositiva. Note que as proposições 𝑟 e 𝑠 são dadas por: 𝑟 : 𝑝 ∈
N é ímpar e 𝑠 : 𝑥2 + 𝑥 − 𝑝 = 0 não admite solução inteira.
é inteiro.
√ √ √
4. Então, 1 − 4𝑝 − 1 e − 1 − 4𝑝 − 1 devem ser pares, o que ocorre apenas se 1 − 4𝑝 é ímpar.
9
√
5. Isso implica que 1 − 4𝑝 = 2𝑘 + 1, para algum 𝑘 ∈ N.
6. Como o produto de um inteiro ímpar e um inteiro par é sempre par, temos que 𝑝 é sempre par
concluindo a prova.
10
1. Suponha que exista um 𝑛 ∈ N que seja o máximo elemento do conjunto.
2. Então, ∀𝑥 ∈ N, temos 𝑛 ≥ 𝑥.
5. Logo, 𝑚 é maior que o máximo elemento do conjunto N, o que gera uma contradição à hipótese
inicial, concluindo a prova.
√
Teorema 6. 2 é um número irracional.
√
1. Iremos supor que 2 pertence ao conjunto dos racionais Q.
√
2. Então, 2 = 𝑎𝑏 , com 𝑏 ̸= 0, sendo que 𝑎 e 𝑏 não possuem fatores primos.
𝑎2
3. Assim, 2 = 𝑏2
, o que implica em 𝑎2 = 2𝑏2 . Ou seja, temos que 𝑎2 é par.
7. Note que 2 divide tanto 𝑎 quanto 𝑏, contradizendo a hipótese de que eles não possuem fatores
primos (contradição), o que conclui a demonstração.
√
Exercício: Prove que 3 é um número irracional.
1. Suponha que o conjunto 𝑃 dos números primos seja finito, ou seja, 𝑃 = {2, 3, 5, 7, ..., 𝑝}, em
que 𝑝 denota o maior deles.
2. Seja 𝑛 o inteiro definido pela multiplicação de todos os números primos, adicionado de uma
unidade, ou seja, 𝑛 = (2 × 3 × 5 × 7 × ... × 𝑝) + 1.
4. Entretanto, note que 𝑛 não é divisível por nenhum número primo do conjunto 𝑃 , uma vez que
terá resto 1.
5. Pelo Teorema Fundamental da Aritmética, sabe-se que: Todos inteiros positivos maiores que 1
possuem uma decomposição única em fatores primos.
11
6. Seja 𝑟 um dos fatores primos de 𝑛. Então, 𝑟 não pode ser nenhum dos elementos de 𝑃 , o que
contradiz a hipótese de que 𝑃 contém todos os números primos.
• Parte 1: 𝑝 → 𝑞
𝑥 = 2𝑟 + 1 (7)
𝑦 = 2𝑠 + 1 (8)
3. Como o conjunto os inteiros é fechado para adição e multiplicação, temos que 𝑘 = 2𝑟𝑠 +
𝑟 + 𝑠 ∈ N.
4. Portanto, como 𝑥𝑦 = 2𝑘 + 1, o produto é um número ímpar.
• Parte 2: 𝑞 → 𝑝
12
Proposição: Seja 𝑛 um inteiro. Então 𝑛 é par se e somente se 𝑛2 é par.
Demonstração: Devemos provar as duas direções:
𝑛2 = (2𝑘)2 = 4𝑘 2 = 2(2𝑘 2 )
Exemplo: "Todos os unicórnios voam" é verdadeiro por vacuidade, pois não existem unicórnios
para contradizer a afirmação.
Exemplo: Todos os inteiros pares e primos maiores que 2 são quadrados perfeitos.
Supondo que N represente o conjunto dos inteiros, podemos escrever:
13
onde os predicados denotam:
Como 𝑃 (𝑥) ∧ 𝑀 (𝑥) sempre é falso, a expressão sempre será verdadeira por vacuidade.
“Todo número inteiro par maior que 2 pode ser expresso como a soma de dois números
primos.”
Por exemplo:
4=2+2
6=3+3
8=3+5
10 = 3 + 7 = 5 + 5
12 = 5 + 7
Até hoje, a Conjectura de Goldbach não foi demonstrada nem refutada. No entanto, avanços
significativos foram feitos:
• Resultados Parciais:
– Em 1937, Vinogradov provou que todo número ímpar suficientemente grande pode ser
escrito como a soma de três primos (uma versão fraca da conjectura).
– Em 1966, Chen Jing-run mostrou que todo número par grande pode ser escrito como 𝑝+𝑞,
onde 𝑝 é primo e 𝑞 é um quase-primo (número com no máximo dois fatores primos).
– Verificações computacionais confirmaram a conjectura para todos os números pares até
4 × 1018 (até 2023).
• Abordagens Modernas:
14
– Alguns matemáticos acreditam que uma prova pode exigir novas técnicas, talvez relacio-
nadas à Hipótese de Riemann.
• A conjectura exige uma garantia absoluta para todo número par, não apenas para casos particu-
lares.
• Não há uma fórmula simples que descreva todos os pares (𝑝, 𝑞) de primos tais que 𝑝 + 𝑞 = 2𝑛.
A conjectura de Goldbach continua sendo um dos grandes desafios da matemática. Se um dia for
resolvida, provavelmente revolucionará nossa compreensão dos números primos.
15
2 O princípio da indução matemática
O Princípio da Indução Matemática é uma das ferramentas mais poderosas da Matemática Dis-
creta, utilizado para demonstrar proposições indexadas nos números naturais. Baseado na estrutura
bem ordenada de N, o método estabelece que uma afirmação 𝑃 (𝑛) vale para todos os inteiros 𝑛 ≥ 0
mediante:
Sua relevância estende-se desde fundamentos teóricos (como definições recursivas e propriedades
de sequências) até aplicações práticas em:
A seguir iremos utiilzar uma analogia para explicar a intuição por trás da prova por indução:
suponha uma escada com infinitos degraus. Queremos saber se podemos alcançar todo degrau dessa
escada inifinita. Para isso, devemos garantir duas condições:
Se garantirmos essas duas condições, então é verdade que podemos acessar qualquer um dos
infinitos degraus da escada. Essa é a intuição que guia o princípio da indução matemática. Em termos
matemáticos, podemos escrever a seguinte proposição lógica:
Mas, a pergunta que surge é: porque a indução matemática á válida? Primeiramente, veremos um
princípio fundamental para entendermos a resposta desta pergunta.
Definição 8 (Princípio da boa ordenação (PBO)). Todo subconjunto não vazio de N possui um menor
elemento.
Iremos demonstrar que a indução matemática é válida a partir de uma prova por contradição.
1. Vamos supor que 𝑃 (1) é verdadeira e que para todo 𝑘, 𝑃 (𝑘) → 𝑃 (𝑘 + 1).
16
3. Assuma que exista pelo menos um inteiro positivo para o qual 𝑃 (𝑛) é falso.
4. Então, o conjunto 𝑆 dos inteiros positivos para os quais 𝑃 (𝑛) é falso não é vazio.
9. Mas pela suposição inicial, para todo 𝑘, 𝑃 (𝑘) → 𝑃 (𝑘+1), o que implica em: 𝑃 (𝑚˘1) → 𝑃 (𝑚)
ser verdade.
10. Isso faz com que P(m) tenha que ser verdadeira, o que gera uma contradição.
𝑘
∑︁ 𝑘(𝑘 + 1)
𝑃 (𝑘) : 𝑖 = 1 + 2 + ... + 𝑘 = (13)
𝑖=1
2
𝑘+1
∑︁ (𝑘 + 1)(𝑘 + 2)
𝑃 (𝑘 + 1) : 𝑖 = 1 + 2 + ... + 𝑘 + (𝑘 + 1) = (14)
𝑖=1
2
Sob a hipótese de que 𝑃 (𝑘) é verdadeira, devemos mostrar que 𝑃 (𝑘 + 1) é verdadeira. Note que:
𝑘+1 𝑘
∑︁ ∑︁ 𝑘(𝑘 + 1) 𝑘(𝑘 + 1) + 2(𝑘 + 1) (𝑘 + 1)(𝑘 + 2)
𝑖= 𝑖 + (𝑘 + 1) = + (𝑘 + 1) = = (15)
𝑖=1 𝑖=1
2 2 2
Exercício: Elabore uma fórmula para computar a soma dos 𝑛 primeiros inteiros ímpares positivos.
Prove por indução que sua fórmula vale para qualquer valor inteiro de 𝑛.
17
Vamos iniciar observando o padrão a seguir:
n números soma
1 1 1
2 1+3 4
3 1+3+5 9
4 1+3+5+7 16
5 1+3+5+7+9 25
... ... ...
Desejamos provar que essa expressão é válida para todo 𝑛 inteiro maior que zero. Iniciamos pelo
caso base.
e mostrar que:
18
𝑃 (𝑘) : 20 + 21 + 22 + 23 + ... + 2𝑘 = 2𝑘+1 − 1 (21)
que é justamente o valor desejado para 𝑃 (𝑘 + 1), o que conclui a prova por indução.
Exercício: Uma sequência do tipo 1, 1/2, 1/4, 1/8, ... é uma progressão geométrica (PG) em que
o primeiro termo 𝑎0 = 1 e a razão 𝑟 = 1/2. Sabe-se que o 𝑘-ésimo termo de uma PG é computado
como:
𝑎𝑘 = 𝑎0 𝑟 𝑘 (23)
Use a indução matemática para provar que a soma dos termos de uma PG finita com 𝑎0 = 𝑎 e
razão r é dada por:
𝑎𝑟𝑘+1 − 𝑎
𝑃 (𝑘) : 𝑎 + 𝑎𝑟 + 𝑎𝑟2 + 𝑎𝑟3 + ... + 𝑎𝑟𝑘 = (24)
𝑟−1
com 𝑟 ̸= 1, onde 𝑘 é um inteiro não negativo.
𝑎𝑟−𝑎 𝑎(𝑟−1)
• BASE: 𝑃 (0) : 𝑎 = 𝑟−1
= 𝑟−1
= 𝑎, o que valida o argumento.
𝑎𝑟𝑘+2 − 𝑎
𝑃 (𝑘 + 1) : 𝑎 + 𝑎𝑟 + 𝑎𝑟2 + 𝑎𝑟3 + ... + 𝑎𝑟𝑘 + 𝑎𝑟𝑘+1 = (25)
𝑟−1
𝑎𝑟𝑘+1 − 𝑎
(𝑎 + 𝑎𝑟 + 𝑎𝑟2 + 𝑎𝑟3 + ... + 𝑎𝑟𝑘 ) + 𝑎𝑟𝑘+1 = + 𝑎𝑟𝑘+1 (26)
𝑟−1
Exercício: Use a indução matemática para demonstrar a desigualdade 𝑃 (𝑛) : 𝑛 < 2𝑛 para todo
inteiro positivo 𝑛.
19
• BASE: 𝑃 (1) = 1 < 2, o que valida o argumento.
𝑘 < 2𝑘 (28)
Como 1 ≤ 2𝑘 , ∀𝑘 ∈ N:
1 1 1
𝐻𝑗 = 1 + + + ... + (31)
2 3 𝑗
para 𝑗 = 1, 2, ..., 𝑛. Por exemplo, temos que 𝐻4 é dado por:
1 1 1 25
𝐻4 = 1 + + + = (32)
2 3 4 12
Use a indução matemática para provar que:
𝑛
𝐻2𝑛 ≥ 1 + (33)
2
ou seja, que essa soma é divergente.
1 3 1
• BASE: 𝐻21 = 1 + 2
= 2
≥1+ 2
= 23 , o que valida o argumento.
𝑘
𝐻2𝑘 ≥ 1 + (34)
2
então
𝑘+1
𝐻2𝑘+1 ≥ 1 + (35)
2
Primeiramente, note que:
(︂ )︂
1 1 1 1 1 1
𝐻2𝑘+1 = 1 + + + ... + 𝑘 + 𝑘 + 𝑘 + ... + 𝑘+1 (36)
2 3 2 2 +1 2 +2 2
20
onde o somatório entre parêntesis é justamente 𝐻2𝑘 , ou seja:
1 1 1
𝐻2𝑘+1 = 𝐻2𝑘 + + 𝑘 + ... + 𝑘+1 (37)
2𝑘 +1 2 +2 2
Utilizando a hipótese de indução, temos:
(︂ )︂ [︂ ]︂
𝑘 1 1 1
𝐻2𝑘+1 ≥ 1+ + 𝑘 + 𝑘 + ... + 𝑘 (38)
2 2 +1 2 +2 2 + 2𝑘
Note que cada um dos 2𝑘 termos no somatório entre colchetes é maior ou igual que 1/2𝑘+1 ,o que
nos permite escrever:
(︂ )︂
𝑘 1
𝐻2𝑘+1 ≥ 1+ + 2𝑘 𝑘+1 (39)
2 2
o que nos leva a:
(︂ )︂
𝑘 1 𝑘+1
𝐻2𝑘+1 ≥ 1+ + =1+ (40)
2 2 2
concluindo a prova por indução.
Exercício: Use a indução matemática para provar que 7𝑛+1 82𝑛+1 é divisível por 57.
o que equivale a:
Assim, o objetivo consiste em mostrar que 7𝑘+3 82𝑘+3 é divisível por 57. Podemos escrever:
21
Colocando o fator 7 em evidência, temos:
Mas, pela hipótese de indução, sabemos que 7𝑘+2 + 82𝑘+1 é divisível por 57. A segunda parcela é
trivialmente divisível por 57. Uma observação importante é que, na aritmética modular, ∀𝑎, 𝑏, 𝑥 ∈ N,
se 𝑎 mod 𝑥 = 0 e 𝑏 mod 𝑥 = 0, então (𝑎 + 𝑏) mod 𝑥 = 0. Sendo assim, a prova por indução está
concluída.
Exercício: Um pesquisador desenvolveu uma fórmula para calcular o somatório do quadrado dos
𝑛 primeiros inteiros positivos. Mostre por indução que essa fórmula vale para todo 𝑛 ∈ N.
𝑘(𝑘 + 1)(2𝑘 + 1)
𝑃 (𝑘) : 12 + 22 + 32 + ... + 𝑘 2 = (46)
6
• BASE: 𝑃 (1) : 1 = 6/6 = 1, o que valida o argumento.
(𝑘 + 1)(𝑘 + 2)(2𝑘 + 3)
𝑃 (𝑘 + 1) : 12 + 22 + 32 + ... + 𝑘 2 + (𝑘 + 1)2 = (47)
6
Utilizando a hipótese de indução, o somatório dos 𝑘 + 1 primeiros inteiros ao quadrado pode ser
expressa como:
𝑘(𝑘 + 1)(2𝑘 + 1)
(12 + 22 + 32 + ... + 𝑘 2 ) + (𝑘 + 1)2 = + (𝑘 + 1)2 (48)
6
o que pode ser escrito como:
(𝑘 + 1)(2𝑘 2 + 𝑘 + 6𝑘 + 6) (𝑘 + 1)(2𝑘 2 + 3𝑘 + 4𝑘 + 6)
= (51)
6 6
o que nos leva a:
22
Finalmente, chegamos em:
1 × 1! 2! − 1 = 1
1 × 1! + 2 × 2! 3! − 1 = 5
1 × 1! + 2 × 2! + 3 × 3! 4! − 1 = 23
1 × 1! + 2 × 2! + 3 × 3! + 4 × 4! 5! − 1 = 119
... ...
1 × 1! + 2 × 2! + 3 × 3! + 4 × 4! + ... + 𝑛 × 𝑛! (𝑛 + 1)! − 1
Ele se pergunta se esse padrão é válido para todo 𝑛 > 0. Ajude-o a provar que sim.
Seja a proposição:
23
2 × (𝑘 + 1)! + 𝑘 × (𝑘 + 1)! − 1 = (𝑘 + 2)(𝑘 + 1)! − 1 = (𝑘 + 2)! − 1 (59)
(1 + ℎ)𝑛 ≥ 1 + 𝑛ℎ (60)
para ∀𝑛 ∈ N e ℎ > 0 (juros). A ideia dessa desigualdade consiste em comparar o avanço de um capital
a juros compostos com o avanço de um capital a juros simples, mostrando que juros compostos sempre
rendem pelo menos igual aos juros simples. Podemos expressar a proposição 𝑃 (𝑘) como:
Iniciando por:
(1 + ℎ)𝑘 ≥ 1 + 𝑘ℎ (63)
Aplique a distributiva:
Como 𝑘ℎ2 é estritamente positivo, temos que se a equação (65) é satisfeita, então 𝑃 (𝑘 + 1) é
satisfeita com uma margem ainda maior (pois o lado direito é menor ainda, devido a ausência do
termo quadrático). Portanto, a prova por indução está completa.
𝑛(2𝑛 − 1)(2𝑛 + 1)
12 + 32 + 52 + ... + (2𝑛 − 1)2 = (66)
3
para todo 𝑛 inteiro maior que zero.
24
Exercício: Prove por indução matemática que:
[︂ ]︂2
3 3 3 𝑛(𝑛 + 1)
3
1 + 2 + 3 + ... + 𝑛 = (67)
2
para todo inteiro 𝑛 positivo.
1 1 1 1
+ + + ... + 𝑛 (68)
2 4 8 2
Prove que sua fórmula vale para todo inteiro 𝑛 > 0.
1 1 1 1 𝑛−1
+ + + ... + = (69)
1×2 2×3 3×4 (𝑛 − 1)𝑛 𝑛
para todo inteiro 𝑛 > 1.
25
3 Introdução à teoria dos conjuntos
A teoria dos conjuntos é considerada a linguagem fundamental da matemática moderna. Quase
todos os conceitos matemáticos — números, funções, relações, estruturas algébricas e até mesmo al-
goritmos — podem ser descritos e compreendidos a partir da noção de conjuntos. Para o estudante de
Computação, isso significa adquirir uma base conceitual sólida que permitirá transitar com segurança
entre diferentes áreas da ciência, desde a análise de algoritmos até a modelagem de bancos de dados
e o estudo de linguagens formais.
Na prática computacional, conjuntos aparecem de forma recorrente: na representação de coleções
de dados em estruturas como listas, filas e árvores; na manipulação de bancos de dados relacionais; na
definição de domínios e intervalos de funções; ou ainda em algoritmos que lidam com agrupamentos,
interseções e buscas. Compreender operações como união, interseção, diferença e produto cartesiano
não é apenas um exercício de formalismo matemático, mas uma ferramenta para estruturar problemas
computacionais de forma mais clara e eficiente.
Além disso, a teoria dos conjuntos fornece o terreno para tópicos mais avançados que serão ex-
plorados ao longo da disciplina, como relações, funções e grafos. Esses conceitos, fundamentais na
Computação, só podem ser plenamente compreendidos quando se domina a noção de conjuntos. Es-
tudar esse tema, portanto, não é apenas um passo inicial, mas um investimento estratégico: é aprender
a “gramática” da matemática que sustenta o raciocínio lógico e a abstração necessários ao cientista
da computação.
3.1 Conjuntos
Uma forma simples e informal de definir conjuntos é dizer que um conjunto é uma coleção de
objetos bem definidos, considerados como uma unidade. Esses objetos são chamados de elementos do
conjunto, e podem ser números, letras, pessoas, símbolos ou até outros conjuntos. O ponto essencial
é que deve ficar claro quais elementos pertencem e quais não pertencem ao conjunto.
Por exemplo, o conjunto dos números pares menores que 10 pode ser escrito como {2, 4, 6, 8}.
Já o conjunto das vogais do alfabeto português é {𝑎, 𝑒, 𝑖, 𝑜, 𝑢}. O importante é que cada elemento é
distinto dentro do conjunto e a ordem em que os elementos são listados não altera o conjunto, ou seja,
{𝑎, 𝑒, 𝑖, 𝑜, 𝑢} representa exatamente o mesmo conjunto que {𝑢, 𝑖, 𝑒, 𝑜, 𝑎}.
Assim, de maneira informal, podemos pensar em um conjunto como uma caixa bem definida de
elementos, onde sabemos exatamente o que está dentro e o que está fora. Essa ideia, embora simples,
serve como base para toda a teoria dos conjuntos e, por consequência, para boa parte da matemática
e da computação.
26
números primos menores que 10 pode ser escrito como:
𝑃 = {2, 3, 5, 7}
Outra forma, especialmente útil para conjuntos infinitos ou de difícil enumeração, é defini-los
a partir de uma propriedade característica que determina a pertinência de seus elementos. Por
exemplo, podemos representar novamente o conjunto dos primos menores que 10 como:
𝐴 = {𝑥 : 𝑥 ∈ 𝑃 ∧ 𝑥 < 10}
onde 𝑃 é o conjunto de todos os números primos. De modo semelhante, o conjunto dos números
naturais pode ser descrito como:
N = {𝑥 : 𝑥 ∈ Z ∧ 𝑥 ≥ 0}
Também é importante destacar o conceito de conjunto vazio, que representa um conjunto sem
elementos. Ele é denotado por ∅ ou simplesmente {}. Um exemplo é:
𝐴 = {𝑥 : 𝑥 ∈ N ∧ 0 < 𝑥 < 1}
Neste caso, não há nenhum número natural que satisfaça a condição 0 < 𝑥 < 1, logo 𝐴 = ∅.
𝐴⊈𝐵 ⇐⇒ (∃𝑥 (𝑥 ∈ 𝐴 ∧ 𝑥 ∈
/ 𝐵)).
𝐴 ⊂ 𝐵 ⇔ (𝐴 ⊆ 𝐵 ∧ ∃𝑥 ∈ 𝐵 (𝑥 ∈
/ 𝐴)).
27
3.3 Operações entre conjuntos
As operações entre conjuntos permitem combinar ou relacionar diferentes coleções de elementos
de forma sistemática, possibilitando a construção de novos conjuntos a partir de outros já conhecidos.
Entre as operações mais importantes estão a união, que reúne todos os elementos presentes em ao
menos um dos conjuntos; a interseção, que seleciona apenas os elementos comuns; e a diferença, que
mantém apenas os elementos de um conjunto que não pertencem ao outro. Também são fundamentais
o conjunto complementar, que considera os elementos que não pertencem a um conjunto em relação
a um universo previamente definido, e a diferença simétrica, que reúne os elementos que estão em
apenas um dos conjuntos, mas não em ambos. Essas operações formam a base de muitos raciocínios
matemáticos e encontram aplicações diretas na Computação, como em consultas a bancos de dados,
manipulação de estruturas de dados e análise de informações.
Para facilitar a compreensão dessas operações, utilizamos frequentemente os diagramas de Venn,
que oferecem uma representação gráfica simples e intuitiva. Neles, conjuntos são representados por
regiões delimitadas, geralmente círculos, dentro de um retângulo que representa o universo. As sobre-
posições e áreas distintas ilustram visualmente relações como união, interseção e complementaridade,
ajudando a desenvolver a intuição dos estudantes. Além de serem ferramentas didáticas poderosas,
os diagramas de Venn são úteis em problemas práticos de contagem, probabilidade e lógica, servindo
como uma ponte entre o raciocínio formal e a visualização intuitiva.
O conjunto universo é o conjunto que contém todos os elementos de interesse em um determinado
contexto. Ele funciona como um "referencial"para a análise de subconjuntos e operações, pois qual-
quer conjunto considerado deve estar contido no universo adotado. A escolha do conjunto universo
depende do problema em estudo: por exemplo, em um exercício sobre números pares e ímpares, o
universo pode ser o conjunto dos números inteiros; já em uma aplicação envolvendo alunos de uma
turma, o universo pode ser o conjunto de todos os estudantes matriculados.
Em notação, o conjunto universo costuma ser representado por 𝑈 , e sua definição é essencial para
operações como o complemento de um conjunto 𝐴, denotado por 𝐴𝑐 = 𝑈 − 𝐴, que reúne todos os
elementos do universo que não pertencem a 𝐴. A seguir listamos algumas das operações básicas entre
dois conjuntos.
1. Complemento de 𝐴: 𝐴𝑐 = {𝑥 : 𝑥 ∈
/ 𝐴}
2. União de 𝐴 com 𝐵: 𝐴 ∪ 𝐵 = {𝑥 : 𝑥 ∈ 𝐴 ∨ 𝑥 ∈ 𝐵}
28
3. Intersecção de 𝐴 com 𝐵: 𝐴 ∩ 𝐵 = {𝑥 : 𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐵}
/ 𝐴} = 𝐵 ∩ 𝐴𝑐
4. Diferença de 𝐵 e 𝐴: 𝐵 − 𝐴 = {𝑥 : 𝑥 ∈ 𝐵 ∧ 𝑥 ∈
• (𝐴 ∪ 𝐵) − 𝐵 = 𝐴
• (𝐴 ∪ 𝐵) − 𝐵 ̸= 𝐴
𝑈 = {𝑥 ∈ N | 0 ≤ 𝑥 ≤ 9}
𝐴 = {1, 2, 3, 4}
𝐵 = {𝑥 ∈ N | (𝑥 − 1)(𝑥 − 3)2 = 0}
29
𝐶 = {𝑥 ∈ N | 𝑥 mod 2 = 0}
Calcule:
1. 𝐴 ∪ 𝐵
2. 𝐴 ∩ (𝐵 ∪ 𝐶)
3. 𝐶 − 𝐴
5. 𝐴 ∪ 𝐶
Se 𝐴 = 𝐵, então:
𝐴 ⊖ 𝐵 = ∅.
Se 𝐴 ∩ 𝐵 = ∅, então:
𝐴 ⊖ 𝐵 = 𝐴 ∪ 𝐵.
Até o presente momento vimos como definir as operações de união e interseção entre dois con-
juntos. Mas essas operações podem ser generalizadas para coleções de conjuntos.
a) Encontre 𝑛𝑖=1 𝐴𝑖 = 𝐴1 ∪ 𝐴2 ∪ 𝐴3 .
⋃︀
b) Encontre 𝑛𝑖=1 𝐴𝑖 = 𝐴1 ∩ 𝐴2 ∩ 𝐴3 .
⋂︀
c) Encontre ∞
⋂︀
𝑖=1 𝐴𝑖 .
30
3.4 Princípio da inclusão-exclusão
O princípio da inclusão-exclusão é uma técnica fundamental da teoria dos conjuntos e da análise
combinatória que permite calcular, de maneira precisa, a cardinalidade da união de conjuntos a partir
das cardinalidades individuais e de suas interseções. A ideia central é corrigir a contagem excessiva
que ocorre quando simplesmente somamos os tamanhos dos conjuntos: ao fazer isso, os elementos
comuns são contados mais de uma vez e, portanto, precisam ser subtraídos adequadamente. Esse
princípio é uma ferramenta poderosa tanto em problemas de contagem quanto em aplicações de pro-
babilidade, análise de algoritmos e teoria das redes.
Na prática, o princípio começa de forma simples para dois conjuntos e pode ser estendido para
três ou mais conjuntos, embora as expressões se tornem progressivamente mais complexas, alter-
nando somas e subtrações de interseções. Para o estudante de Computação, compreender e aplicar
o princípio da inclusão-exclusão é essencial para lidar com problemas clássicos de contagem, como
aqueles que envolvem sobreposições de condições, otimização de consultas em bancos de dados e
análise da complexidade de algoritmos.
A seguir veremos um importante resultado da teoria dos conjuntos sobre a contagem de elementos
na união de dois conjuntos quaisquer 𝐴 e 𝐵.
Teorema 9 (Princípio da Inclusão-Exclusão, caso 𝑛 = 2). Dados dois conjuntos finitos 𝐴 e 𝐵, então:
𝐴 ∪ 𝐵 = (𝐴 − 𝐵) ∪ (𝐴 ∩ 𝐵) ∪ (𝐵 − 𝐴).
31
4. Substituindo na equação, obtemos:
5. Simplificando:
|𝐴 ∪ 𝐵| = |𝐴| + |𝐵| − |𝐴 ∩ 𝐵|.
Exemplo: Dentre 4689 estudantes, 2112 cursaram pelo menos 60 créditos e 2678 cursaram no
máximo 60 créditos. Quantos deles cursaram exatamente 60 créditos?
Seja 𝐴 o conjunto dos alunos que cursaram pelo menos 60 créditos e 𝐵 o conjunto dos alunos que
cursaram no máximo 60 créditos. Então temos:
Substituindo os valores:
4689 = 2112 + 2678 − |𝐴 ∩ 𝐵|.
Assim:
|𝐴 ∩ 𝐵| = 2112 + 2678 − 4689 = 4790 − 4689 = 101.
32
Note que temos 7 conjuntos disjuntos, que são:
|(𝐴 ∩ 𝐵) − 𝐶| = |𝐴 ∩ 𝐵| − |𝐴 ∩ 𝐵 ∩ 𝐶|,
|(𝐵 ∩ 𝐶) − 𝐴| = |𝐵 ∩ 𝐶| − |𝐴 ∩ 𝐵 ∩ 𝐶|,
|(𝐴 ∩ 𝐶) − 𝐵| = |𝐴 ∩ 𝐶| − |𝐴 ∩ 𝐵 ∩ 𝐶|,
|𝐴 ∩ 𝐵 ∩ 𝐶| = |𝐴 ∩ 𝐵 ∩ 𝐶|.
Exemplo. Um total de 1232 estudantes cursaram Espanhol, 879 cursaram Francês e 114 cursaram
Russo. Além disso, 103 cursaram Espanhol e Francês, 23 cursaram Espanhol e Russo, e 14 cursaram
Francês e Russo. Se 2092 cursaram pelo menos um dos três cursos, quantos cursaram os três cursos?
Pelo princípio da inclusão-exclusão, temos:
33
Desejamos calcular |𝐸 ∩ 𝐹 ∩ 𝑅|. Isolando este termo, obtemos:
Efetuando os cálculos:
|𝐸 ∩ 𝐹 ∩ 𝑅| = 7.
Sendo assim, a fórmula para o número de elementos da união neste caso é dada por:
34
O teorema a seguir generaliza o princípio da inclusão-exclusão para um número 𝑛 arbitrário de
conjuntos.
A figura a seguir mostra uma visualização dos possíveis subconjuntos na união de 5 conjuntos:
𝐴, 𝐵, 𝐶, 𝐷, 𝐸. Note que há algumas intersecções faltantes na ilustração, uma vez que deveríamos ter
um total de 31 possíveis subconjuntos.
Iremos omitir a prova deste teorema, mas o leitor interessado pode encontrá-la na Seção 8.5,
página 579, do excelente livro a seguir: Rosen, K. H. Discrete Mathematics and its Applications,
8a edição, McGraw Hill, 2019. A definição a seguir mostra um conceito fundamental da teoria dos
conjuntos: a partição de um conjunto 𝐴.
Definição 14 (Partição). Uma coleção de conjuntos não vazios {𝐴1 , 𝐴2 , . . . , 𝐴𝑛 } é uma partição de
𝐴 se, e somente se:
35
1. Cobertura: a união das partições é igual a todo o conjunto 𝐴,
𝐴1 ∪ 𝐴2 ∪ · · · ∪ 𝐴𝑛 = 𝐴;
𝐴𝑖 ∩ 𝐴𝑗 = ∅.
𝑇0 = {𝑛 ∈ N : ∃𝑘 ∈ N / 𝑛 = 3𝑘},
𝑇1 = {𝑛 ∈ N : ∃𝑘 ∈ N / 𝑛 = 3𝑘 + 1},
𝑇2 = {𝑛 ∈ N : ∃𝑘 ∈ N / 𝑛 = 3𝑘 + 2}.
Sendo assim:
𝑇0 ∩ 𝑇1 = ∅, 𝑇1 ∩ 𝑇2 = ∅, 𝑇0 ∩ 𝑇2 = ∅.
36
Além disso:
𝑇0 ∪ 𝑇1 ∪ 𝑇2 = N.
Portanto, {𝑇0 , 𝑇1 , 𝑇2 } constitui uma partição válida do conjunto dos números naturais.
2𝐴 = {∅, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.
Note que:
|2𝐴 | = 2|𝐴| .
𝐴 × 𝐵 = {(𝑎, 𝑏) : 𝑎 ∈ 𝐴 ∧ 𝑏 ∈ 𝐵}.
Observação: O produto cartesiano não é comutativo! A ordem dos conjuntos altera o resultado
do produto.
Exemplo: Seja
𝐴1 = {𝑥, 𝑦}, 𝐴2 = {1, 2, 3}, 𝐴3 = {𝑎, 𝑏}.
1. Encontre 𝐴1 × 𝐴2 :
𝐴1 × 𝐴2 = {(𝑥, 1), (𝑥, 2), (𝑥, 3), (𝑦, 1), (𝑦, 2), (𝑦, 3)}.
2. Encontre 𝐴1 × 𝐴2 × 𝐴3 :
𝐴1 × 𝐴2 × 𝐴3 = {(𝑥, 1, 𝑎), (𝑥, 1, 𝑏), (𝑥, 2, 𝑎), (𝑥, 2, 𝑏), (𝑥, 3, 𝑎), (𝑥, 3, 𝑏),
(𝑦, 1, 𝑎), (𝑦, 1, 𝑏), (𝑦, 2, 𝑎), (𝑦, 2, 𝑏), (𝑦, 3, 𝑎), (𝑦, 3, 𝑏)}.
37
3.5 Propriedades de operações entre conjuntos
A seguir, veremos algumas propriedades dos operadores união, intersecção e de subconjuntos:
∀𝐴, 𝐵 (𝐴 ∪ 𝐵 = 𝐵 ∪ 𝐴) ∧ (𝐴 ∩ 𝐵 = 𝐵 ∩ 𝐴).
∀𝐴, 𝐵, 𝐶 (𝐴 ∪ (𝐵 ∩ 𝐶) = (𝐴 ∪ 𝐵) ∩ (𝐴 ∪ 𝐶)),
∀𝐴, 𝐵, 𝐶 (𝐴 ∩ (𝐵 ∪ 𝐶) = (𝐴 ∩ 𝐵) ∪ (𝐴 ∩ 𝐶)).
4. Leis da identidade:
∀𝐴 𝐴 ∪ ∅ = 𝐴, 𝐴 ∩ 𝑈 = 𝐴.
5. Leis da complementaridade:
𝐴 ∪ 𝐴𝑐 = 𝑈, 𝐴 ∩ 𝐴𝑐 = ∅, (𝐴𝑐 )𝑐 = 𝐴.
6. Leis de De Morgan:
(𝐴 ∩ 𝐵)𝑐 = 𝐴𝑐 ∪ 𝐵 𝑐 ,
(𝐴 ∪ 𝐵)𝑐 = 𝐴𝑐 ∩ 𝐵 𝑐 .
Iremos provar o item (a). Para isso, temos que mostrar que os conjuntos 𝐴 ∩ 𝐵 e 𝐴 ∪ 𝐵 são
idênticos. Lembre que dois conjuntos 𝐴 e 𝐵 são iguais se, e somente se,
𝐴 ⊆ 𝐵 ∧ 𝐵 ⊆ 𝐴.
38
Parte 1
ii. Então, 𝑥 ∈
/ 𝐴 ∩ 𝐵.
iii. Para não estar na interseção, 𝑥 pode estar em 𝐴 ou 𝐵 mas não em ambos:
𝑥∈
/𝐴 ∧ 𝑥∈
/ 𝐵.
v. Portanto, 𝑥 ∈ 𝐴𝑐 ∪ 𝐵 𝑐 .
Parte 2
i. Suponha 𝑦 ∈ 𝐴𝑐 ∪ 𝐵 𝑐 (arbitrário).
ii. Então, 𝑦 ∈ 𝐴𝑐 ∨ 𝑦 ∈ 𝐵 𝑐 .
iv. Se 𝑦 não está em 𝐴 e não está em 𝐵, ele não pode estar em 𝐴 e 𝐵 simultaneamente:
𝑦∈
/ 𝐴 ∩ 𝐵.
v. Portanto, 𝑦 ∈ (𝐴 ∩ 𝐵)𝑐 .
(𝐴 ∩ 𝐵)𝑐 = 𝐴𝑐 ∪ 𝐵 𝑐 .
Duas leis importantes da teoria dos conjuntos são: a lei da absorção e a lei da diferença. A lei
da absorção é definida como:
∀𝐴, 𝐵, 𝐴 ∪ (𝐴 ∩ 𝐵) = 𝐴, (76)
∀𝐴, 𝐵, 𝐴 ∩ (𝐴 ∪ 𝐵) = 𝐴. (77)
39
A lei da diferença é definida como:
∀𝐴, 𝐵, 𝐴 − 𝐵 = 𝐴 ∩ 𝐵. (78)
Demonstração: Para demonstrar esta lei, lembramos que a diferença entre conjuntos é definida
como
𝐴 − 𝐵 = {𝑥 | 𝑥 ∈ 𝐴 ∧ 𝑥 ∈ / 𝐵}.
𝑥∈𝐴−𝐵 ⇐⇒ 𝑥∈𝐴∧𝑥∈
/ 𝐵.
Assim, temos:
𝑥∈𝐴−𝐵 ⇐⇒ 𝑥 ∈ 𝐴 ∧ 𝑥 ∈ 𝐵𝑐.
Pela hipótese indutiva, o primeiro termo da união pode ser escrito como:
40
(︃𝑘+1 )︃𝑐 𝑘 𝑘+1
⋂︁ ⋃︁ ⋃︁
𝐴𝑖 = 𝐴𝑐𝑖 ∪ 𝐴𝑐𝑘+1 = 𝐴𝑐𝑖 (83)
𝑖=1 𝑖=1 𝑖=1
(a)
𝐴 − (𝐴 ∩ 𝐵) = 𝐴 − 𝐵
𝐴 − (𝐴 ∩ 𝐵) = 𝐴 ∩ (𝐴 ∩ 𝐵)𝑐
= 𝐴 ∩ (𝐴𝑐 ∪ 𝐵 𝑐 )
= (𝐴 ∩ 𝐴𝑐 ) ∪ (𝐴 ∩ 𝐵 𝑐 )
= ∅ ∪ (𝐴 ∩ 𝐵 𝑐 )
= 𝐴 ∩ 𝐵𝑐
= 𝐴 − 𝐵.
(b)
(𝐴 ∪ 𝐵) − 𝐶 = (𝐴 − 𝐶) ∪ (𝐵 − 𝐶)
(𝐴 ∪ 𝐵) − 𝐶 = (𝐴 ∪ 𝐵) ∩ 𝐶 𝑐
= (𝐴 ∩ 𝐶 𝑐 ) ∪ (𝐵 ∩ 𝐶 𝑐 )
= (𝐴 − 𝐶) ∪ (𝐵 − 𝐶).
(c)
𝐴 ∪ (𝐵 − 𝐶) = (𝐴 ∪ 𝐵) − (𝐶 − 𝐴)
𝐴 ∪ (𝐵 − 𝐶) = 𝐴 ∪ (𝐵 ∩ 𝐶 𝑐 )
= (𝐴 ∪ 𝐵) ∩ (𝐴 ∪ 𝐶 𝑐 )
= (𝐴 ∪ 𝐵) − (𝐶 − 𝐴).
Exemplo: Mostre que a diferença simétrica entre 𝐴 e 𝐵 pode ser expressa como a diferença entre
a união de 𝐴 e 𝐵 e a interseção de 𝐴 e 𝐵.
Sabemos que a diferença simétrica é definida como:
𝐴 ⊖ 𝐵 = (𝐴 − 𝐵) ∪ (𝐵 − 𝐴)
41
Pela lei da diferença, temos:
𝐴 ⊖ 𝐵 = (𝐴 ∩ 𝐵 𝑐 ) ∪ (𝐵 ∩ 𝐴𝑐 )
𝐴 ⊖ 𝐵 = (𝐴 ∪ 𝐵) ∩ (𝐴 ∪ 𝐴𝑐 ) ∩ (𝐵 ∪ 𝐵 𝑐 ) ∩ (𝐵 𝑐 ∪ 𝐴𝑐 )
𝐴 ⊖ 𝐵 = (𝐴 ∪ 𝐵) ∩ 𝑈 ∩ 𝑈 ∩ (𝐵 𝑐 ∪ 𝐴𝑐 )
𝐴 ⊖ 𝐵 = (𝐴 ∪ 𝐵) ∩ (𝐵 𝑐 ∪ 𝐴𝑐 )
𝐴 ⊖ 𝐵 = (𝐴 ∪ 𝐵) − (𝐵 𝑐 ∪ 𝐴𝑐 )𝑐
𝐴 ⊖ 𝐵 = (𝐴 ∪ 𝐵) − (𝐵 ∩ 𝐴) = (𝐴 ∪ 𝐵) − (𝐴 ∩ 𝐵)
42
base para desenvolvimentos mais sofisticados em matemática discreta, teoria das relações e análise
de algoritmos.
Em resumo, este capítulo buscou apresentar uma introdução sólida ao universo da teoria dos con-
juntos, preparando o terreno para conceitos mais avançados que surgirão nos capítulos seguintes. A
familiaridade com os conjuntos e suas operações é condição essencial para compreender relações,
funções, estruturas matemáticas e, sobretudo, para o desenvolvimento do pensamento lógico e abs-
trato necessário em computação e matemática aplicada.
43
4 Relações
As relações constituem um dos conceitos centrais da Matemática Discreta, pois permitem descre-
ver e analisar a maneira como elementos de um conjunto podem estar associados a elementos de outro
(ou do mesmo) conjunto. De forma geral, uma relação é um subconjunto do produto cartesiano entre
dois conjuntos, ou seja, um conjunto de pares ordenados que expressam ligações entre seus elemen-
tos. Esse formalismo simples é capaz de representar uma ampla gama de situações, desde relações
numéricas básicas, como “menor que” ou “divisível por”, até estruturas mais complexas empregadas
em ciência da computação, como grafos e bancos de dados relacionais.
O estudo das propriedades das relações — como reflexividade, simetria, antissimetria e transiti-
vidade — fornece ferramentas essenciais para compreender padrões de organização e classificação.
Por exemplo, relações de equivalência permitem agrupar elementos em classes que compartilham
características comuns, enquanto relações de ordem fornecem um arcabouço natural para organizar
informações em hierarquias ou sequências. Essas ideias estão na base de muitas áreas da computação,
como algoritmos de ordenação, estruturas de dados e teoria das linguagens formais.
Além disso, relações desempenham papel fundamental em aplicações práticas. Em bancos de
dados, as relações formam o núcleo da modelagem de tabelas e consultas; em redes de computa-
dores, podem representar conexões entre máquinas; e em teoria de grafos, tornam-se a base para o
estudo de vértices e arestas. Portanto, compreender o conceito de relações e suas propriedades não
apenas amplia a capacidade de abstração matemática do estudante, mas também fornece instrumentos
indispensáveis para o desenvolvimento de soluções computacionais eficientes.
Exemplo: Sejam
𝐴 = {0, 1, 2}, 𝐵 = {𝑎, 𝑏}.
Então,
𝑅 = {(0, 𝑎), (0, 𝑏), (1, 𝑎), (1, 𝑏)}
Introduziremos aqui uma notação para indicar a pertinência de um par ordenado em uma relação
𝑅. Para dizer que o par (𝑎, 𝑏) pertence à relação 𝑅, escrevemos:
(𝑎, 𝑏) ∈ 𝑅 ≡ 𝑎𝑅𝑏
dom(𝑅) = {𝑎 : ∃𝑏 (𝑎𝑅𝑏)},
img(𝑅) = {𝑏 : ∃𝑎 (𝑎𝑅𝑏)}.
44
Definição 19 (Endorrelação). Uma endorrelação é uma relação binária definida em 𝐴 × 𝐴.
Definição 20 (Relação Inversa). Seja 𝑅 uma relação. A relação inversa de 𝑅 é definida como:
Exemplo: Seja
𝐴 = {1, 2, 3, 4, 5, 6}, 𝐵 = {1, 2, 3, 4}.
𝑅 = {(1, 1), (1, 3), (2, 2), (2, 4), (3, 1), (3, 3), (4, 2), (4, 4), (5, 1), (5, 3), (6, 2), (6, 4)}.
Note que os pares (5, 5) e (6, 6) não pertencem à relação 𝑅. Eles só apareceriam se a relação fosse
definida de 𝐴 em 𝐴 (isto é, uma endorrelação).
Exemplo. Seja 𝐴 = {1, 2, 3, 4}. Defina 𝑅 como a relação binária de 𝐴 em 𝐴 a seguir:
𝑎𝑅𝑏 ⇔ 𝑎 divide 𝑏.
Uma pergunta interessante que surge neste momento é: quantas relações binárias de 𝐴 em 𝐴
existem em um conjunto de 𝑛 elementos 𝐴 = {1, 2, 3, . . . , 𝑛}?
Se 𝑅 ⊆ 𝐴 × 𝐴, então o produto cartesiano terá
|𝐴 × 𝐴| = 𝑛2
elementos.
Lembrando do conjunto potência, definido como o conjunto de todos os subconjuntos de um dado
conjunto, sabemos que o número de elementos é dado por:
|2𝑅 | = 2|𝑅| .
2
2𝑛 .
2|𝐴×𝐴| = 225
relações distintas.
Considere o caso mais simples em que 𝐴 = {1, 2}. Então, o produto cartesiano de 𝐴 com ele
45
mesmo é:
𝐴 × 𝐴 = {(1, 1), (1, 2), (2, 1), (2, 2)},
elementos, portanto temos 16 possíveis relações binárias (incluindo a relação vazia, que não associa
nenhum elemento a nenhum outro).
Definição 21 (Relação Reflexiva). Seja 𝐴 um conjunto qualquer e 𝑅 ⊆ 𝐴 × 𝐴 uma relação binária.
Dizemos que 𝑅 é reflexiva se:
∀𝑥 ∈ 𝐴, 𝑥𝑅𝑥.
Exemplo. Seja 𝐴 = {1, 2, 3} e considere as seguintes relações:
𝑅2 = {(1, 1), (2, 1), (2, 2), (3, 2), (3, 3)}.
∀𝑥 ∈ 𝐴, (𝑥, 𝑥) ∈
/ 𝑅.
𝑅2 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)}
𝑅3 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)} (simétrica e antissimétrica).
Note que, por exemplo, existe o par (2, 1) ∈ 𝑅3 , mas como não existe (1, 2), temos que a impli-
cação da definição da propriedade antissimétrica é verdadeira. De fato, a proposição lógica envolvida
46
é:
(𝑥𝑅𝑦 ∧ 𝑦𝑅𝑥) → (𝑥 = 𝑦).
Quando (𝑥𝑅𝑦 ∧ 𝑦𝑅𝑥) é falso, a implicação inteira é verdadeira. Isso pode ser melhor visualizado
na tabela verdade a seguir:
Outros exemplos:
𝑅4 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)} (antissimétrica),
𝑥 ̸= 𝑦 → ¬(𝑥𝑅𝑦 ∧ 𝑦𝑅𝑥).
Ou seja, para dois elementos distintos de 𝐴, não pode ocorrer simultaneamente 𝑥𝑅𝑦 e 𝑦𝑅𝑥.
𝑅 = {(3, 3)}.
Note que 𝑅 é simétrica (pois o par inverso de (3, 3) é ele mesmo) e também antissimétrica. Este
exemplo mostra que é possível uma relação ser simétrica e antissimétrica ao mesmo tempo.
Teorema 12. Seja 𝑅 uma relação binária qualquer em 𝐴. Se 𝑅 é simétrica, então a relação inversa
𝑅−1 também é simétrica.
Prova.
47
3. De 𝑥𝑅𝑦 e 𝑦𝑅𝑥, temos 𝑥𝑅−1 𝑦 e 𝑦𝑅−1 𝑥.
𝑅1 = {(1, 1), (1, 2), (2, 1)} não é transitiva (falta (2, 2)),
𝑅2 = {(1, 1), (1, 2), (1, 4), (2, 1), (2, 2), (3, 3), (4, 1), (4, 4)} não é transitiva (falta (4, 2)),
𝑅3 = {(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)} transitiva,
𝑅4 = {(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)} transitiva,
• 𝑅1 , pois ∀𝑥 ∈ Z, 𝑥 ≤ 𝑥.
• 𝑅4 , pois 𝑥 = 𝑦 ⇒ 𝑦 = 𝑥.
• 𝑅6 , pois (𝑥 + 𝑦 ≤ 3) ⇒ (𝑦 + 𝑥 ≤ 3).
48
• 𝑅1 , pois ((𝑥 ≤ 𝑦) ∧ (𝑦 ≤ 𝑥)) ⇒ 𝑥 = 𝑦.
• 𝑅1 , pois (𝑥 ≤ 𝑦 ∧ 𝑦 ≤ 𝑧) ⇒ 𝑥 ≤ 𝑧.
• 𝑅4 , pois (𝑥 = 𝑦 ∧ 𝑦 = 𝑧) ⇒ 𝑥 = 𝑧.
𝐴 = {1, 2, 3, 4}, 𝑅 = {(1, 1), (2, 3), (2, 4), (3, 3), (3, 4)}.
Pergunta-se:
𝑅 = {(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)}, 𝑆 = {(1, 0), (2, 0), (3, 1), (3, 2), (4, 1)}.
49
Calcule a composição 𝑆 ∘ 𝑅 (primeiro aplica 𝑅 e depois 𝑆):
𝑆 ∘ 𝑅 = {(1, 0), (1, 1), (2, 1), (2, 2), (3, 0), (3, 1)}.
𝑅 ∘ 𝑆 = {(3, 1), (3, 4), (3, 3), (4, 1), (4, 4)},
𝑆 ∘ 𝑅 ̸= 𝑅 ∘ 𝑆.
𝑅 ∘ 𝐼𝐴 = 𝐼𝐵 ∘ 𝑅 = 𝑅.
Exemplo: Sejam
𝐴 = {1, 2, 3}, 𝐵 = {10, 20, 30, 40}, 𝑅 = {(1, 20), (1, 30), (2, 30)}.
𝐼𝐴 = {(1, 1), (2, 2), (3, 3)}, 𝐼𝐵 = {(10, 10), (20, 20), (30, 30), (40, 40)}.
50
Sendo assim, note que:
𝑅 ∘ 𝐼𝐴 = {(1, 20), (1, 30), (2, 30)} = 𝑅, 𝐼𝐵 ∘ 𝑅 = {(1, 20), (1, 30), (2, 30)} = 𝑅.
Definição: Composição com a relação inversa Seja 𝑅 uma relação binária em 𝐴. Ao contrá-
rio do que ocorre com funções, a composição de 𝑅 com sua inversa 𝑅−1 em geral não resulta na
identidade.
Exemplo:
𝐴 = {1, 2, 3}, 𝑅 = {(1, 2), (1, 3), (2, 3)}, 𝑅−1 = {(2, 1), (3, 1), (3, 2)}, 𝐼𝐴 = {(1, 1), (2, 2), (3, 3)}.
Portanto:
𝑅−1 ∘ 𝑅 ̸= 𝑅 ∘ 𝑅−1 ̸= 𝐼𝐴 .
(𝑆 ∘ 𝑅)−1 = 𝑅−1 ∘ 𝑆 −1 .
Ou seja:
𝑅2 = 𝑅 ∘ 𝑅, 𝑅3 = 𝑅2 ∘ 𝑅 = (𝑅 ∘ 𝑅) ∘ 𝑅, . . .
Exemplo: Seja
𝑅 = {(1, 1), (2, 1), (3, 2), (4, 3)}.
51
Calcule 𝑅𝑛 para 𝑛 = 2, 3, 4, . . . :
Veremos a seguir um resultado muito importante que relaciona a propriedade transitiva com a
operação de composição.
Teorema 14. Seja 𝑅 uma relação binária em 𝐴. 𝑅 é transitiva se, e somente se,
𝑅 ∘ 𝑅 ⊆ 𝑅.
Em outras palavras, se 𝑅 é transitiva, ao compor 𝑅 consigo mesma, sempre se obtém uma relação
com o mesmo número ou menos de pares ordenados.
1. Seja (𝑥, 𝑦) ∈ 𝑅 ∘ 𝑅.
4. Portanto, (𝑥, 𝑦) ∈ 𝑅.
1. Sejam 𝑥, 𝑦, 𝑧 ∈ 𝐴 arbitrários.
5. Logo, 𝑅 é transitiva.
Na realidade, o teorema anterior pode ser generalizado para qualquer 𝑛 arbitrário, ou seja, ao
continuar compondo uma relação transitiva com ela mesma, o número de pares ordenados tende a
diminuir ainda mais.
52
Teorema 15. Seja 𝑅 uma relação binária em 𝐴. 𝑅 é transitiva se e somente se
2. Então (𝑥, 𝑦) ∈ 𝑅𝑘 ∘ 𝑅.
Portanto, (𝑥, 𝑦) ∈ 𝑅, o que conclui o passo de indução. Logo, 𝑅𝑛 ⊆ 𝑅 para todo 𝑛 > 0.
Parte 2 (volta): 𝑅𝑛 ⊆ 𝑅 para todo 𝑛 > 0 =⇒ 𝑅 é transitiva.
A prova é direta: basta tomar 𝑛 = 2 e aplicar o teorema anterior, que garante que 𝑅2 ⊆ 𝑅,
mostrando a transitividade.
A seguir estudaremos os fechamentos de uma relação. Eles são importantes pois definem a menor
relação que contém 𝑅 e possui a propriedade especificada pelo fecho (reflexivo, simétrico, transitivo,
etc.).
Definição 25 (Fecho reflexivo). Seja 𝑅 uma relação binária em 𝐴. Se 𝑅 não é reflexiva, então existe
𝑥 ∈ 𝐴 tal que (𝑥, 𝑥) ∈
/ 𝑅.
Se acrescentarmos todos esses pares (𝑥, 𝑥) faltantes a 𝑅, obtemos a menor relação reflexiva que
contém 𝑅, a qual denominamos fecho reflexivo de 𝑅.
Exemplo: Sejam
𝐴 = {𝑎, 𝑏, 𝑐}, 𝑅 = {(𝑎, 𝑎), (𝑎, 𝑏), (𝑏, 𝑎), (𝑐, 𝑏)}.
O fecho reflexivo 𝑅′ de 𝑅 é:
𝑅′ = {(𝑎, 𝑎), (𝑎, 𝑏), (𝑏, 𝑎), (𝑏, 𝑏), (𝑐, 𝑏), (𝑐, 𝑐)}.
Definição 26 (Fecho simétrico). Seja 𝑅 uma relação binária em 𝐴. O fecho simétrico de 𝑅 é a menor
relação simétrica que contém 𝑅.
É a relação 𝑅′ obtida acrescentando a 𝑅 todos os pares necessários para torná-la simétrica.
53
Exemplo: Sejam
𝐴 = {𝑎, 𝑏, 𝑐}, 𝑅 = {(𝑎, 𝑎), (𝑎, 𝑏), (𝑏, 𝑏), (𝑏, 𝑐), (𝑐, 𝑎), (𝑐, 𝑏)}.
𝑅′ = {(𝑎, 𝑎), (𝑎, 𝑏), (𝑎, 𝑐), (𝑏, 𝑎), (𝑏, 𝑏), (𝑏, 𝑐), (𝑐, 𝑎), (𝑐, 𝑏)}.
Definição 27. Seja 𝑅 uma relação binária em 𝐴. O fecho transitivo de 𝑅 é a menor relação transitiva
que contém 𝑅.
Ao contrário dos fechos reflexivos e simétricos, não é trivial encontrá-lo. A seguir, discutiremos
o porquê disso.
Podemos examinar todos os pares (𝑥, 𝑦) e (𝑦, 𝑧) que pertencem a 𝑅. Note, porém, que isso não é
suficiente.
Exemplo: Seja
𝐴 = {1, 2, 3, 4}, 𝑅 = {(1, 2), (2, 3), (3, 4)}.
𝑅′ = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 4)}.
𝑅′′ = {(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)},
que é transitiva.
Note que os pares que faltam em 𝑅 são da forma (𝑥, 𝑦) tal que existe 𝑧 para o qual (𝑥, 𝑧) e
(𝑧, 𝑦) ∈ 𝑅, ou seja, são exatamente os pares de
𝑅2 = 𝑅 ∘ 𝑅.
𝑅′ = 𝑅 ∪ 𝑅2 .
54
Da mesma forma, os pares que faltam em 𝑅′ estão em:
𝑅′′ = 𝑅′ ∪ (𝑅2 ∪ 𝑅3 ∪ 𝑅4 ) = 𝑅 ∪ 𝑅2 ∪ 𝑅3 ∪ 𝑅4 .
Continuando o processo, os pares que faltam em 𝑅′′ estão em 𝑅′′ ∘𝑅′′ . Pelo mesmo procedimento,
podemos verificar que o fecho transitivo é:
𝑅+ = 𝑅 ∪ 𝑅2 ∪ 𝑅3 ∪ . . .
Por essa razão, o fecho transitivo de 𝑅, denotado por 𝑅* , é definido como a união de todas as
potencias de 𝑅, ou seja:
∞
⋃︁
*
𝑅 = 𝑅𝑖 = 𝑅 ∪ 𝑅2 ∪ 𝑅3 ∪ 𝑅4 ∪ ... (84)
𝑖=1
𝑅* = 𝑅 ∪ 𝑅2 ∪ · · · ∪ 𝑅𝑖 ∪ · · · ∪ 𝑅𝑗 ∪ · · · ∪ 𝑅𝑖+𝑗 ∪ . . .
5. Portanto, (𝑥, 𝑧) ∈ 𝑅* .
𝑅1 ⊆ 𝑅2 e 𝑆1 ⊆ 𝑆2 ,
então
𝑅1 ∘ 𝑆1 ⊆ 𝑅2 ∘ 𝑆2 .
55
Essa propriedade é intuitiva: a composição de relações com poucos pares gera uma relação resul-
tante com número reduzido de pares.
𝑅𝑛 ⊆ 𝑆 𝑛 .
Teorema 18. Para qualquer relação 𝑅, toda relação transitiva 𝑆 que contém 𝑅 contém o fecho
transitivo 𝑅* de 𝑅. Em outras palavras, 𝑅* é a menor relação que contém 𝑅 e é transitiva.
56
partir deste capítulo, estamos preparados para avançar em temas como funções, classes de equivalên-
cia e estruturas de ordem, que se apoiam diretamente no arcabouço desenvolvido aqui.
57
5 Relações de equivalência
As relações de equivalência ocupam um papel central na matemática e na ciência da computação,
pois formalizam a noção intuitiva de que certos elementos podem ser considerados “iguais” em um
sentido mais amplo do que a simples identidade. Em vez de tratar cada objeto de forma isolada, as
relações de equivalência permitem agrupar elementos que compartilham uma propriedade comum,
criando uma estrutura organizada e reveladora.
Neste capítulo, estudaremos em detalhe as três propriedades que caracterizam uma relação de
equivalência: reflexividade, simetria e transitividade. Veremos como a presença simultânea dessas
condições garante que os elementos de um conjunto possam ser particionados em subconjuntos dis-
juntos, chamados de classes de equivalência. Esse particionamento fornece uma maneira poderosa
de simplificar problemas, ao permitir que trabalhemos com representantes de classes em vez de com
elementos individuais.
Além da teoria, exploraremos exemplos práticos de relações de equivalência, como a congruência
aritmética em teoria dos números, a relação de paralelismo em geometria e as partições em estru-
turas combinatórias. Cada exemplo mostrará como a noção de equivalência surge naturalmente em
diferentes áreas e como ela auxilia na modelagem de situações complexas.
Por fim, discutiremos o vínculo profundo entre relações de equivalência e partições de conjun-
tos, estabelecendo um teorema fundamental que conecta essas duas ideias. Esse resultado não ape-
nas fornece uma compreensão conceitual unificada, mas também abre caminho para aplicações mais
avançadas em álgebra, lógica matemática e ciência da computação.
Definição 28 (Relação de equivalência). Seja 𝑅 uma relação binária em 𝐴. Dizemos que 𝑅 é uma
relação de equivalência se 𝑅 é reflexiva, simétrica e transitiva. Em uma relação de equivalência 𝑅,
se 𝑎𝑅𝑏 então dizemos que 𝑎 é equivalente a 𝑏, e escrevemos 𝑎 ∼ 𝑏.
𝑥 𝑧
𝑅 ⇐⇒ 𝑥𝑤 = 𝑦𝑧.
𝑦 𝑤
Por exemplo,
1 2 2 3
𝑅 pois 1 · 4 = 2 · 2, 𝑅 pois 2 · 6 = 3 · 4.
2 4 4 6
58
𝑥 𝑥
Reflexividade: note que 𝑅 , pois 𝑥 · 𝑦 = 𝑦 · 𝑥. Logo, 𝑅 é reflexiva.
𝑦 𝑦
𝑥 𝑧 𝑥 𝑧
Simetria: suponha , ∈ 𝑆 tal que 𝑅 . Então, 𝑥 · 𝑤 = 𝑦 · 𝑧. Mas, como a ordem dos fatores
𝑦 𝑤 𝑦 𝑤
não altera o produto (comutatividade da multiplicação), 𝑧 · 𝑦 = 𝑤 · 𝑥, o que nos leva a
𝑧 𝑥
𝑅
𝑤 𝑦
𝑥𝑤 = 𝑦𝑧 e 𝑧𝑣 = 𝑤𝑢.
Assim 𝑥𝑤𝑣 = 𝑦𝑤𝑢. Como 𝑤 ̸= 0 (denominadores em 𝑆 são não nulos), podemos cancelar o fator 𝑤
na equação inteira (ou, de modo equivalente em Z, observar que 𝑤(𝑥𝑣 − 𝑦𝑢) = 0 implica 𝑥𝑣 − 𝑦𝑢 = 0
porque 𝑤 ̸= 0), obtendo
𝑥𝑣 = 𝑦𝑢.
𝑥 𝑢
Portanto 𝑅 . Assim 𝑅 é transitiva. Como 𝑅 é reflexiva, simétrica e transitiva, concluímos que 𝑅
𝑦 𝑣
é uma relação de equivalência em 𝑆.
(ou seja, o conjunto de todos os elementos 𝑥 que se relacionam com 𝑎) é denominado classe de
equivalência de 𝑎.
𝑅 = { (−2, −2), (−1, −1), (0, 0), (1, 1), (2, 2), (3, 3), (4, 4), (−2, 1), (−2, 4), (−1, 2), (85)
(0, 3), (1, −2), (1, 4), (2, −1), (3, 0), (4, −2), (4, 1) }
59
Note que existem no total 17 pares ordenados na relação 𝑅.
• Reflexiva: (−2, −2), (−1, −1), (0, 0), (1, 1), (2, 2), (3, 3), (4, 4)
Uma observação: lembre se que há duas versões utilizadas em computação: remainder (rem) e
modulo (mod). A função remainder (que calcula simplesmente o resto) permite valores negativos e
modulo retorna valores estritamente não negativos.
Nos exemplos, estamos adotando o operador mod, em que o retorno da função é sempre maior ou
igual a zero. Sua implementação em linguagem C é dada por:
60
int mod(int x, int m) {
int r = x % m;
return r < 0 ? r+m : r;
}
Dessa forma, temos que −1 mod 3 é calculado pelo retorno de mod(-1, 3).
O resto da divisão é negativo:
𝑟 = −1%3 = −1
−1 + 3 = 2
𝑥 − 𝑦 = 𝑘𝑚 para algum 𝑘 ∈ Z.
𝑦 − 𝑥 = −𝑘𝑚,
o que mostra que 𝑦−𝑥 também é múltiplo de 𝑚, ou seja, 𝑚 divide 𝑦−𝑥. Portanto, (𝑦−𝑥) mod 𝑚 = 0
e 𝑅 é simétrica.
3. Transitiva: Suponha que 𝑚 divide 𝑥 − 𝑦 e 𝑚 divide 𝑦 − 𝑧. Então
61
o que mostra que 𝑥−𝑧 também é múltiplo de 𝑚, ou seja, 𝑚 divide 𝑥−𝑧. Portanto, (𝑥−𝑧) mod 𝑚 = 0
e 𝑅 é transitiva. Como 𝑅 é reflexiva, simétrica e transitiva, concluímos que 𝑅 é uma relação de
equivalência em Z.
Teorema 20. Seja 𝑅 uma relação de equivalência sobre um conjunto 𝐴. As seguintes informações
são equivalentes:
1. 𝑥𝑅𝑦
2. [𝑥]𝑅 = [𝑦]𝑅
3. [𝑥]𝑅 ∩ [𝑦]𝑅 ̸= ∅
1. Seja 𝑎 ∈ [𝑥]𝑅 arbitrário. Então, por definição, 𝑎𝑅𝑥. Como 𝑅 é relação de equivalência, por
transitividade: (𝑎𝑅𝑥 ∧ 𝑥𝑅𝑦) ⇒ 𝑎𝑅𝑦
2. Assim, 𝑎 ∈ [𝑦]𝑅
4. Assim, 𝑎 ∈ [𝑥]𝑅
62
Portanto, [𝑥]𝑅 = [𝑦]𝑅 , ou seja, os dois conjuntos são iguais.
B) Prova de 𝑖𝑖. ⇒ 𝑖𝑖𝑖., ou seja, [𝑥]𝑅 = [𝑦]𝑅 ⇒ [𝑥]𝑅 ∩ [𝑦]𝑅 ̸= ∅
Ou seja, isso mostra que as classes de equivalência são disjuntas duas a duas.
Portanto, a partir das conclusões dos itens (1) e (2) acima, podemos enunciar o seguinte resultado.
Vamos mostrar a seguir que uma partição de um conjunto 𝐴 pode ser utilizada para construir uma
relação de equivalência em 𝐴: dois elementos estão relacionados se e somente se estão no mesmo
bloco da partição.
63
Teorema 22. Seja 𝑃 uma partição de 𝐴 e seja 𝑆 a relação
𝑆 = {(𝑥, 𝑦) : ∃𝐶 ∈ 𝑃 / 𝑥 ∈ 𝐶 ∧ 𝑦 ∈ 𝐶}.
Ou seja, 𝑥𝑆𝑦 se e somente se 𝑥 está no mesmo bloco que 𝑦. Então 𝑆 é uma relação de equivalência
e suas classes de equivalência são os blocos da partição 𝑃 .
Prova:
1. Note que 𝑆 é reflexiva, pois ∀𝑎 ∈ 𝐴, 𝑎𝑆𝑎, uma vez que todo 𝑎 pertence a algum bloco da
partição.
2. Note que 𝑆 é simétrica, pois temos 𝑎𝑆𝑏 se os elementos 𝑎, 𝑏 pertencem a um mesmo bloco de
𝑃 . Logo, por definição, 𝑏𝑆𝑎, uma vez que 𝑏, 𝑎 continuam pertencendo ao mesmo bloco de 𝑃 .
Assim, 𝑆 é reflexiva, simétrica e transitiva, ou seja, uma relação de equivalência. Além disso, suas
classes de equivalência coincidem exatamente com os blocos da partição 𝑃 .
64
toda relação de equivalência define uma partição. Esse resultado estabelece uma correspondência
fundamental entre dois conceitos que aparecem em diferentes áreas da matemática, como a teoria dos
números, a álgebra linear, a geometria e até em aplicações práticas da computação.
Por fim, pode-se concluir que o estudo das relações de equivalência não apenas fornece ferra-
mentas poderosas para a organização de conjuntos, mas também abre caminho para conceitos mais
avançados, como quocientes de grupos, espaços fatorados e classes residuais na aritmética modular.
Dessa forma, o capítulo sobre relações de equivalência deve ser visto como um alicerce sólido para
tópicos mais profundos e sofisticados da matemática.
65
6 Relações de ordem parcial
As relações de ordem parcial constituem uma extensão natural do estudo das relações binárias,
permitindo modelar situações em que alguns elementos podem ser comparados entre si, enquanto ou-
tros permanecem incomparáveis. Diferentemente de uma ordem total, onde qualquer par de elemen-
tos é comparável, as ordens parciais refletem cenários mais gerais e realistas, em que a comparação
completa não é sempre possível ou desejada.
Um exemplo clássico de ordem parcial aparece na relação de inclusão entre conjuntos. Dados dois
subconjuntos 𝐴 e 𝐵 de um conjunto universo 𝑈 , podemos afirmar que 𝐴 ⊆ 𝐵, mas nem sempre é
possível comparar 𝐴 e 𝐵, pois pode ocorrer que nenhum esteja contido no outro. Esse tipo de relação
surge em diversas áreas, como na hierarquia de tarefas em sistemas computacionais, na organização
de dependências em bancos de dados e até na estruturação de árvores de decisão.
O estudo das ordens parciais envolve identificar três propriedades fundamentais: reflexividade,
antissimetria e transitividade. Juntas, elas garantem uma estrutura lógica que permite raciocinar so-
bre hierarquias, níveis de prioridade e relações de precedência. Além disso, conceitos derivados,
como elementos mínimos, máximos, supremos e ínfimos, tornam-se essenciais para compreender as
propriedades mais refinadas das estruturas ordenadas.
Assim, este capítulo tem como objetivo apresentar os fundamentos das relações de ordem parcial,
ilustrar seus principais exemplos e discutir aplicações relevantes. O entendimento desse tema é es-
sencial não apenas para a Matemática Discreta, mas também para a Ciência da Computação e áreas
afins, uma vez que ordens parciais estão por trás de conjuntos parcialmente ordenados (POSETS) al-
goritmos de ordenação topológica, sistemas de classificação e modelagem de estruturas hierárquicas
complexas.
Definição 30 (Relação de Ordem Parcial (ROP)). Seja 𝐴 um conjunto e 𝑅 uma relação binária em 𝐴.
Dizemos que 𝑅 é uma relação de ordem parcial (ROP) se 𝑅 é reflexiva, anti-simétrica e transitiva.
Note que a mudança de uma única propriedade faz com que a classe de relações de equivalência seja
diferente da classe de relações de ordem parcial.
Definição 31 (Conjunto Parcialmente Ordenado (POSET)). A tupla (𝐴, 𝑅) em que 𝑅 é uma relação
de ordem parcial é chamada de conjunto parcialmente ordenado (POSET).
𝑅 = {(𝑥, 𝑦) ∈ 𝐴 × 𝐴 | 𝑥 ≤ 𝑦}.
1. Reflexiva: ∀𝑥 ∈ 𝐴, 𝑥 ≤ 𝑥 (OK)
66
3. Transitiva: ∀𝑥, 𝑦, 𝑧 ∈ 𝐴 ((𝑥 ≤ 𝑦 ∧ 𝑦 ≤ 𝑧) → 𝑥 ≤ 𝑧) (OK)
𝑆 = {(𝑋, 𝑌 ) ∈ 2𝐴 × 2𝐴 | 𝑋 ⊆ 𝑌 }.
1. Reflexiva: ∀𝑋 ∈ 2𝐴 , 𝑋 ⊆ 𝑋 (OK)
Como 𝑆 satisfaz as três propriedades simultaneamente, 𝑆 é uma relação de ordem parcial. Assim,
a tupla (2𝐴 , ⊆) representa um conjunto parcialmente ordenado (POSET). Veremos mais adiante como
representar graficamente POSETs através de um diagrama de Hasse.
𝑅 = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 6), (1, 12), (90)
(2, 2), (2, 4), (2, 6), (2, 12),
(3, 3), (3, 6), (3, 12),
(4, 4), (4, 12),
(6, 6), (6, 12),
(12, 12)}
(1, 1), (2, 2), (3, 3), (4, 4), (6, 6), (12, 12)
67
ii. Anti-simétrica: Temos, por exemplo: (1, 2) mas não (2, 1);
(1, 3) mas não (3, 1);
(1, 4) mas não (4, 1);
(1, 6) mas não (6, 1);
(1, 12) mas não (12, 1);
(2, 4) mas não (4, 2);
(2, 6) mas não (6, 2);
(2, 12) mas não (12, 2);
(3, 6) mas não (6, 3);
(3, 12) mas não (12, 3);
(4, 12) mas não (12, 4);
(6, 12) mas não (12, 6);
Logo, a relação é anti-simétrica.
iii. Transitiva: Alguns exemplos: (1, 2) e (2, 4) → (1, 4);
(1, 2) e (2, 6) → (1, 6);
(1, 2) e (2, 12) → (1, 12);
(1, 3) e (3, 6) → (1, 6);
(1, 3) e (3, 12) → (1, 12);
(1, 4) e (4, 12) → (1, 12);
(1, 6) e (6, 12) → (1, 12);
(2, 4) e (4, 12) → (2, 12);
(2, 6) e (6, 12) → (2, 12);
(3, 6) e (6, 12) → (3, 12);
Logo, a relação é transitiva.
Portanto, como a relação 𝑅 é reflexiva, anti-simétrica e transitiva, temos que 𝑅 é uma relação de
ordem parcial. Em uma ROP 𝑅, dizemos que os elementos 𝑎 e 𝑏 são comparáveis por 𝑅 se 𝑎𝑅𝑏 ou
𝑏𝑅𝑎. Por exemplo, na relação “divide” listada acima, temos que 2 e 4 são comparáveis, mas 2 e 3
não são.
Definição 32 (Relação de ordem total). Uma relação binária 𝑅 em 𝐴 é de ordem total se, e somente
se, 𝑅 é uma relação de ordem parcial e quaisquer dois elementos de 𝐴 são comparáveis por 𝑅.
Nesse caso, dizemos que a tupla (𝐴, 𝑅) é um conjunto totalmente ordenado. Um exemplo de
relação de ordem total é a relação:
𝑅 = {(𝑥, 𝑦) ∈ 𝐴 | 𝑥 ≤ 𝑦}
68
Definição 33. Seja 𝐴 um conjunto qualquer e seja a relação ≤2 definida em 𝐴 × 𝐴 como:
(︀ )︀
(𝑎1 , 𝑎2 ) ≤2 (𝑏1 , 𝑏2 ) ⇐⇒ (𝑎1 < 𝑏1 ) ∨ (𝑎1 = 𝑏1 ) ∧ (𝑎2 ≤ 𝑏2 )
A relação ≤2 induz uma ordenação lexicográfica no conjunto 𝐴 × 𝐴. Na prática, isso significa que
podemos impor uma ordem para pontos do plano, percorrendo linha a linha o conjunto bidimensional.
Exemplo. Mostre que a relação ≤2 definida em N × N é uma relação de ordem parcial. Devemos
mostrar que a relação é reflexiva, anti-simétrica e transitiva.
2. Anti-simétrica: ∀(𝑎, 𝑏), (𝑐, 𝑑) ∈ N × N, se ((𝑎, 𝑏) ≤2 (𝑐, 𝑑)) ∧ ((𝑐, 𝑑) ≤2 (𝑎, 𝑏)) ⇒ (𝑎, 𝑏) =
(𝑐, 𝑑).
Note que:
3. Transitiva: ∀(𝑎, 𝑏), (𝑐, 𝑑), (𝑒, 𝑓 ) ∈ N × N, se ((𝑎, 𝑏) ≤2 (𝑐, 𝑑)) ∧ ((𝑐, 𝑑) ≤2 (𝑒, 𝑓 )) ⇒ (𝑎, 𝑏) ≤2
(𝑒, 𝑓 ).
Note que:
69
ii. Se (𝑐, 𝑑) ≤2 (𝑒, 𝑓 ), então (𝑐 < 𝑒) ∨ (𝑐 = 𝑒 ∧ 𝑑 ≤ 𝑓 ).
ii. ∀(𝑎, 𝑏) ∈ 𝑅, com 𝑎 ̸= 𝑏, 𝑎 deve estar abaixo de 𝑏, sendo representado por uma linha que liga
os pontos 𝑎 e 𝑏.
iii. Não existem loops, nem triângulos no diagrama, ou seja, não representamos reflexividade nem
transitividade.
𝑅 = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (91)
(2, 2), (2, 3), (2, 4), (2, 5),
(3, 3), (3, 4), (3, 5),
(4, 4), (4, 5),
(5, 5),
(6, 6), (6, 5), (6, 9),
(7, 7), (7, 4), (7, 5),
(8, 8), (8, 7), (8, 5),
(9, 9), (9, 5)}.
70
Note que alguns pares não são comparáveis, como por exemplo: (4, 9), (7, 9), (8, 6), . . .
Apesar de existir (2, 4) ∈ 𝑅, não há linha no diagrama pois há (2, 3) e (3, 4), o que torna a ligação
(2, 4) redundante devido à transitividade. O diagrama de Hasse é ilustrado na figura a seguir.
Exemplo. Seja 𝐴 = {1, 2, 3, 5, 6, 10, 15, 30} e seja 𝑅 a relação binária dada por:
Responda:
𝑅 = {(1, 1), (1, 2), (1, 3), (1, 5), (1, 6), (1, 10), (1, 15), (1, 30),
(2, 2), (2, 6), (2, 10), (2, 30),
(3, 3), (3, 6), (3, 15), (3, 30),
(5, 5), (5, 10), (5, 15), (5, 30),
(6, 6), (6, 30),
(10, 10), (10, 30),
(15, 15), (15, 30),
(30, 30)}.
𝑅 = {(𝑋, 𝑌 ) ∈ 2𝐴 × 2𝐴 : 𝑋 ⊆ 𝑌 }.
71
Escreva os pares ordenados que compõem a relação 𝑅 e desenhe o diagrama de Hasse do POSET.
𝑅 = {(𝑥, 𝑦) ∈ 𝐴 × 𝐴 : 𝑥 ≤ 𝑦}.
Escreva os pares ordenados que compõem a relação 𝑅 e desenhe o diagrama de Hasse do POSET.
𝑅 = {(1, 1), (1, 2), (1, 3), (1, 4), (1, 5),
(2, 2), (2, 3), (2, 4), (2, 5),
(3, 3), (3, 4), (3, 5),
(4, 4), (4, 5),
(5, 5)}.
Note que não há elementos incomparáveis, portanto a estrutura do diagrama de Hasse é linear.
72
Definição 35 (Elemento mínimo). Seja 𝑅 uma relação de ordem parcial sobre o conjunto 𝐴. Um
elemento mínimo de 𝐴 sob 𝑅 é um 𝑚 ∈ 𝐴 tal que:
∀𝑥 ∈ 𝐴 𝑚𝑅𝑥.
Definição 36 (Elemento máximo). Seja 𝑅 uma relação de ordem parcial sobre o conjunto 𝐴. Um
elemento máximo de 𝐴 sob 𝑅 é um 𝑚 ∈ 𝐴 tal que:
∀𝑥 ∈ 𝐴 𝑥𝑅𝑚.
Definição 37 (Elemento minimal). Seja 𝑅 uma relação de ordem parcial sobre o conjunto 𝐴. Um
elemento minimal de 𝐴 sob 𝑅 é um 𝑚 ∈ 𝐴 tal que ∄𝑥 ∈ 𝐴, 𝑥 ̸= 𝑚, 𝑥𝑅𝑚. Em outras palavras, não
existe ninguém que preceda 𝑚.
73
Exemplo. Seja 𝐴 = N − {0, 1}, onde N denota o conjunto dos naturais, e seja 𝑅 a relação “é divisor
próprio de”, ou seja:
𝑅 = {(2, 4), (3, 6), (5, 15), (3, 21), (4, 16), (6, 18), (7, 21), . . .}
Definição 38. Seja 𝑅 uma relação de ordem parcial sobre o conjunto 𝐴. Um elemento maximal de
𝐴 sob 𝑅 é um 𝑚 ∈ 𝐴 tal que ∄𝑥 ∈ 𝐴, 𝑥 ̸= 𝑚, 𝑚𝑅𝑥. Em outras palavras, não existe ninguém que
sucede 𝑚.
Você consegue pensar em um conjunto parcialmente ordenado com um único elemento maximal,
mas que não é máximo? Pode parecer estranho, mas esse tipo de POSET de fato existe.
Exemplo: Seja 𝐴 o conjunto
Note que o elemento 3 não divide nenhum elemento do conjunto, ou seja, não há pares ordenados
do tipo (3, 𝑥). Isso significa que não há nenhum elemento que sucede 3. Portanto, 3 é maximal.
74
Além disso, observe que 3 é o único elemento maximal, pois toda potência de 2 divide a próxima
potência de 2, isto é, teremos infinitos pares do tipo (2𝑛 , 2𝑛+1 ). Assim, não há elemento máximo em
𝐴, uma vez que não existe um elemento de 𝐴 que seja divisível por todo outro elemento de 𝐴.
6.2 Reticulados
Reticulados são conjuntos parcialmente ordenados com propriedades especiais. Antes de definir-
mos o que é um reticulado, iremos definir o maior limite inferior e o menor limite superior de dois
elementos de um conjunto 𝐴.
Definição 39 (Maior limite inferior (meet ou ínfimo)). Seja (𝐴, 𝑅) um conjunto parcialmente orde-
nado e sejam 𝑥, 𝑦 ∈ 𝐴.
𝑧𝑅𝑥 e 𝑧 𝑅 𝑦.
• O maior limite inferior (ou meet), denotado por 𝑥 ∧ 𝑦, é o maior desses limitantes inferiores,
isto é, aquele que é mais próximo de 𝑥 e 𝑦 na ordem.
Definição 40 (Menor limite superior (join ou supremo)). Seja (𝐴, 𝑅) um conjunto parcialmente or-
denado e sejam 𝑥, 𝑦 ∈ 𝐴.
𝑥𝑅𝑧 e 𝑦 𝑅 𝑧.
• O menor limite superior (ou join), denotado por 𝑥 ∨ 𝑦, é o menor desses limitantes superiores,
isto é, aquele que é mais próximo de 𝑥 e 𝑦 na ordem.
Intuitivamente:
Exemplo
Exemplo. Seja 𝐴 = {2, 3, 4, 6, 8} e a relação binária 𝑅 dada por:
𝑅 = {(𝑥, 𝑦) ∈ 𝐴 × 𝐴 : 𝑥 divide 𝑦}
75
a) Liste os pares ordenados de 𝑅:
𝑅 = {(2, 2), (2, 4), (2, 6), (2, 8), (3, 3), (3, 6), (4, 4), (4, 8), (6, 6), (8, 8)}
c) Encontre os maiores limites inferiores (meet ∧) e os menores limites superiores (join ∨) dos
pares indicados:
4 ∧ 6 = 2,
4 ∨ 6 : não existe menor limite superior,
2 ∨ 3 = 6,
2 ∧ 3 : não existe maior limite inferior,
2 ∧ 6 = 2,
2 ∨ 6 = 6,
6 ∧ 8 = 2,
6 ∨ 8 : não existe menor limite superior.
Note que o diagrama de Hasse em questão não possui máximo nem mínimo. Por outro lado, há
dois elementos maximais (6 e 8, pois a partir deles não é possível ir para cima), e dois elementos
minimais (2 e 3, pois a partir deles não é possível ir para baixo).
Definição 41. Seja (𝐴, 𝑅) um conjunto parcialmente ordenado. Se todo par de elementos 𝑥, 𝑦 ∈ 𝐴
possui tanto um maior limite inferior (𝑥 ∧ 𝑦) quanto um menor limite superior (𝑥 ∨ 𝑦) e o POSET
tem um mínimo e um máximo, então dizemos que (𝐴, 𝑅) é um reticulado.
Exemplo. Seja 𝐴 = {𝑥, 𝑦, 𝑧} e o conjunto potência 2𝐴 = {∅, {𝑥}, {𝑦}, {𝑧}, {𝑥, 𝑦}, {𝑥, 𝑧}, {𝑦, 𝑧}, {𝑥, 𝑦, 𝑧}}.
76
Defina a relação binária 𝑅 em 2𝐴 por
𝑅 = {(𝑋, 𝑌 ) ∈ 2𝐴 × 2𝐴 : 𝑋 ⊆ 𝑌 }.
Resposta: O diagrama de Hasse de (2𝐴 , ⊆) é o cubo booleano de dimensão 3 (níveis de baixo para
cima: ∅; {𝑥}, {𝑦}, {𝑧}; {𝑥, 𝑦}, {𝑥, 𝑧}, {𝑦, 𝑧}; {𝑥, 𝑦, 𝑧}).
O POSET (2𝐴 , ⊆) é um reticulado.
Note que o conjunto vazio está contido em todos os conjuntos, então ele é o elemento mínimo.
Note também que o próprio conjunto só está contido nele mesmo; nenhum outro elemento diferente
dele mesmo o contém, logo ele é o elemento máximo.
Além disso, para todo par de elementos, existe um maior limite inferior e um menor limite supe-
rior. Por exemplo:
{𝑦} ∧ {𝑧} = ∅
Observe que, neste caso, as operações meet (∧) e join (∨) correspondem às operações usuais de
interseção e união de conjuntos, respectivamente.
77
a) Pares ordenados que compõem 𝑅
𝑅 = { (1, 1), (1, 2), (1, 3), (1, 4), (1, 6), (1, 8), (1, 9), (1, 12),
(2, 2), (2, 4), (2, 6), (2, 8), (2, 12),
(3, 3), (3, 6), (3, 9), (3, 12),
(4, 4), (4, 8), (4, 12),
(6, 6), (6, 12),
(8, 8),
(9, 9),
(12, 12) }.
Note que não temos um reticulado, uma vez que não existe menor limite superior para o par 6 e 9,
além do par 8 e 12.
Veremos a seguir a noção de limitantes superiores e inferiores.
Quem são os limitantes superiores de {2, 3}? São todos os elementos atingíveis a partir de 2 e 3
apenas por caminhos ascendentes. No caso do POSET acima, os limitantes superiores de {2, 3} são
6 e 12. O resultado da operação join (∨) é o menor dos limitantes superiores, no caso:
2 ∨ 3 = 6.
Da mesma forma, quem são os limitantes inferiores de {8, 12}? São todos os elementos atingíveis
a partir de 8 e 12 apenas por caminhos descendentes. No caso do POSET acima, os limitantes inferi-
ores de {8, 12} são 4, 2 e 1. O resultado da operação meet (∧) é o maior dos limitantes inferiores, no
78
caso:
8 ∧ 12 = 4.
Exemplo. Quais dos POSETS a seguir representam reticulados? Justifique suas respostas.
1. Estrutura típica do reticulado booleano 𝐵2 em que cada par de elementos possui ∧ e ∨. Possui
mínimo (elemento de baixo) e máximo (elemento de cima). Portanto, é um reticulado.
4. Note que o par (𝑏, 𝑑) não possui um menor limite superior (não é único), o que implica que o
POSET não é um reticulado.
Quem são os maiores limites inferiores e menores limites superiores dos pares a seguir?
a) (𝑏, 𝑐)
b) (𝑔, 𝑒)
c) (𝑓, 𝑔)
79
Definição 42 (Álgebra de Boole). Uma álgebra de Boole é um conjunto parcialmente ordenado em
que as operações meet (∧) e join (∨) satisfazem as seguintes propriedades:
i. Associatividade:
𝑥 ∧ (𝑦 ∧ 𝑧) = (𝑥 ∧ 𝑦) ∧ 𝑧, 𝑥 ∨ (𝑦 ∨ 𝑧) = (𝑥 ∨ 𝑦) ∨ 𝑧
ii. Comutatividade:
𝑥 ∧ 𝑦 = 𝑦 ∧ 𝑥, 𝑥∨𝑦 =𝑦∨𝑥
iii. Distributividade:
𝑥 ∧ (𝑦 ∨ 𝑧) = (𝑥 ∧ 𝑦) ∨ (𝑥 ∧ 𝑧), 𝑥 ∨ (𝑦 ∧ 𝑧) = (𝑥 ∨ 𝑦) ∧ (𝑥 ∨ 𝑧)
∃ 0, 1 ∈ 𝐴 tais que 0 ≤ 𝑥 ≤ 1, ∀𝑥 ∈ 𝐴
v. Complementaridade:
vi. Absorção:
𝑥 ∧ (𝑥 ∨ 𝑦) = 𝑥, 𝑥 ∨ (𝑥 ∧ 𝑦) = 𝑥
Essas propriedades são as mesmas operações introduzidas pela Teoria dos Conjuntos, como visto
80
nas aulas anteriores. No caso mais simples, podemos representar tal POSET através de um diagrama
de Hasse.
Aqui, temos o conjunto 𝐴 = {0, 1} e a relação 𝑅 é definida por “está contido em”. Uma boa
reflexão é pensar em maneiras de como definir uma álgebra de Boole em um conjunto com mais de
dois elementos, como por exemplo 𝐴 = {0, 1, 2}. Como ficaria o reticulado? E as operações meet e
join seriam definidas como?
81
Assim, as relações de ordem parcial constituem um tema fundamental, pois unem aspectos algé-
bricos, combinatórios e computacionais. A compreensão desses conceitos é essencial para avançar
em tópicos mais sofisticados da Matemática Discreta, como grafos, estruturas algébricas e teoria da
complexidade.
82
7 Funções
As funções desempenham um papel central em praticamente todos os ramos da Matemática. De
maneira intuitiva, uma função pode ser vista como uma “regra de associação” que, a cada elemento
de um conjunto de partida (o domínio), associa exatamente um elemento de um conjunto de chegada
(o contradomínio). Essa noção simples é suficientemente poderosa para descrever desde processos
aritméticos básicos até sistemas complexos em ciência da computação e engenharia.
No contexto da Matemática Discreta, estudamos funções como relações especiais entre conjun-
tos, caracterizadas pela propriedade de unicidade: para cada elemento do domínio existe um único
elemento associado no contradomínio. Esse enfoque nos permite tratar funções de maneira rigorosa,
analisando não apenas exemplos numéricos, mas também funções definidas em conjuntos abstratos,
finitos ou infinitos, que aparecem em algoritmos, estruturas de dados e modelos matemáticos.
Além de entender a definição formal, é fundamental distinguir diferentes tipos de funções, como
as injetoras, sobrejetoras e bijetoras, que classificam as funções de acordo com a maneira como seus
elementos associam o domínio ao contradomínio. Essas distinções são importantes porque determi-
nam a possibilidade de construir funções inversas, estabelecer correspondências entre conjuntos e
analisar propriedades de cardinalidade.
Neste capítulo, desenvolveremos as principais noções sobre funções, explorando definições, exem-
plos, propriedades e aplicações. Também faremos conexões com tópicos anteriores, como relações
e conjuntos, mostrando como as funções se encaixam naturalmente nesse contexto e ampliam nosso
repertório de ferramentas para o estudo de estruturas matemáticas discretas.
𝑔 = {(1, 2), (1, 3), (4, 7)} não é função, pois a entrada 1 é mapeada para 2 e 3.
Definição 44 (Notação). Seja 𝑓 uma função e 𝑎 ∈ 𝐴. A notação (𝑎, 𝑏) ∈ 𝑓 indica que 𝑓 (𝑎) = 𝑏.
Matematicamente:
𝑓 (𝑎) = 𝑏 ⇔ ∃𝑏 tal que (𝑎, 𝑏) ∈ 𝑓.
83
Exemplo. Expresse a função:
𝑓 (𝑥) = 𝑥2 , 𝑥 ∈ Z, −3 ≤ 𝑥 ≤ 3,
𝑓 = {(−3, 9), (−2, 4), (−1, 1), (0, 0), (1, 1), (2, 4), (3, 9)}.
Definição 45 (Domínio e Imagem). Seja 𝑓 uma função. O conjunto de todos os primeiros elemen-
tos possíveis dos pares ordenados de 𝑓 é o domínio da função. O conjunto de todos os segundos
elementos dos pares ordenados de 𝑓 é a imagem de 𝑓 .
Matematicamente:
dom(𝑓 ) = {𝑎 : ∃𝑏, (𝑎, 𝑏) ∈ 𝑓 },
Exemplo. Seja
𝑓 = {(1, 2), (2, 3), (3, 1), (4, 7)}.
Temos:
dom(𝑓 ) = {1, 2, 3, 4}, img(𝑓 ) = {1, 2, 3, 7}.
𝑓 : 𝐴 → 𝐵,
Observação. Para que 𝑓 seja uma função de 𝐴 em 𝐵, todos os elementos de 𝐴 devem ser mape-
ados (isto é, não pode sobrar nenhum elemento sem correspondência no conjunto 𝐴).
1. 𝑓 é uma função;
2. dom(𝑓 ) = 𝐴;
3. img(𝑓 ) ⊆ 𝐵.
84
Exemplo. Seja
𝐴 = {1, 2, 3, 4, 5, 6}, 𝐵 = {1, 2, 3, 4, 5}.
Considere
𝑓 = {(1, 3), (2, 1), (3, 2), (4, 4), (5, 5)}.
ii) dom(𝑓 ) = 𝐴? Não, pois o elemento 6 não está sendo mapeado para nenhum elemento de 𝐵.
Definição 47 (Função par e ímpar). Sejam 𝐴 e 𝐵 conjuntos infinitos que contenham elementos posi-
tivos e negativos (por exemplo, Z ou R), e seja 𝑓 : 𝐴 → 𝐵 uma função arbitrária.
• Dizemos que 𝑓 é par se, e somente se, (𝑥, 𝑦) ∈ 𝑓 implica (−𝑥, 𝑦) ∈ 𝑓 . Em outras palavras:
𝑓 (−𝑥) = 𝑓 (𝑥).
• Dizemos que 𝑓 é ímpar se, e somente se, (𝑥, 𝑦) ∈ 𝑓 implica (−𝑥, −𝑦) ∈ 𝑓 . Em outras palavras:
𝑓 (−𝑥) = −𝑓 (𝑥).
85
𝐴 = {1, 2, 3, . . . , 𝑚}, 𝐵 = {1, 2, 3, . . . , 𝑛}.
Note que, para cada elemento de 𝐴, temos 𝑛 possibilidades em 𝐵. Como temos 𝑚 elementos em
𝐴:
𝑛 × 𝑛 × 𝑛 × · · · × 𝑛 = 𝑛𝑚 (𝑚 vezes).
Definição 48 (Função Inversa). Seja 𝑓 : 𝐴 → 𝐵 uma função arbitrária. Dizemos que a função
inversa 𝑓 −1 é definida pela inversão dos pares ordenados de 𝑓 .
𝑓 = {(0, 5), (1, 7), (2, 8), (3, 9), (4, 7)}.
𝑓 −1 = {(5, 0), (7, 1), (8, 2), (9, 3), (7, 4)}.
No entanto, 𝑓 −1 não é uma função de 𝐵 → 𝐴, pois o elemento 7 está sendo mapeado para 1 e 4
ao mesmo tempo. Além disso, dom(𝑓 −1 ) ̸= 𝐵. Mais adiante, veremos as condições necessárias para
que a inversa de uma função 𝑓 seja também uma função.
86
Definição 49 (Função injetora). Uma função f é injetora se sempre que:
(𝑥, 𝑧) ∈ 𝑓 ∧ (𝑦, 𝑧) ∈ 𝑓 → 𝑥 = 𝑦
Em outras palavras, pela contrapositiva, 𝑥 ̸= 𝑦 → 𝑓 (𝑥) ̸= 𝑓 (𝑦), o que significa que elementos
distintos do domínio devem ser mapeados para elementos distintos do contra-domnínio.
Definição 50. Seja 𝑓 : 𝐴 → 𝐵 uma função arbitrária. A inversa 𝑓 −1 é uma função se, e somente se,
𝑓 é injetora.
É fácil notar que, se 𝑓 não é injetora, ao invertermos os pares ordenados de 𝑓 , haverá um elemento
que será mapeado para dois valores distintos.
𝑓 (𝑥) = 3𝑥 + 4.
87
Exemplo. Seja 𝑓 : Z → Z dada por:
𝑓 (𝑥) = 𝑥2 .
Note que não basta que 𝑓 seja injetora. Além disso, não deve sobrar nenhum elemento de 𝐵 sem
um valor associado. Por exemplo, a inversa da função 𝑓 : 𝑋 → 𝑌 definida em uma figura anterior
não é função de 𝑌 para 𝑋, pois o elemento 𝐶 ∈ 𝑌 não é mapeado para nenhum valor.
Matematicamente:
∃𝑧 ∈ 𝑌 | 𝑓 −1 (𝑧) indefinida.
ou seja, img(𝑓 ) = 𝐵. Em outras palavras, todos os elementos do contradomínio são atingidos (não
sobra nenhum elemento em 𝐵).
Exemplo. Sejam:
𝐴 = {1, 2, 3, 4, 5, 6}, 𝐵 = {7, 8, 9, 10},
𝑓 = {(1, 7), (2, 7), (3, 8), (4, 9), (5, 9), (6, 10)},
𝑔 = {(1, 7), (2, 7), (3, 7), (4, 9), (5, 9), (6, 10)}.
𝑓 (𝑥) = 3𝑥 + 4.
2. Defina:
𝑏−4
𝑎= .
3
88
3. Calculando 𝑓 (𝑎), temos:
(︂ )︂
𝑏−4
𝑓 (𝑎) = 3 + 4 = (𝑏 − 4) + 4 = 𝑏.
3
4. Portanto, 𝑓 é sobrejetora, pois para cada 𝑏 ∈ Q sempre é possível encontrar um 𝑎 ∈ Q tal que
𝑓 (𝑎) = 𝑏.
Teorema 23. Sejam 𝐴 e 𝐵 conjuntos arbitrários, e seja 𝑓 : 𝐴 → 𝐵 uma função. A função inversa
𝑓 −1 : 𝐵 → 𝐴 existe se, e somente se, 𝑓 é bijetora.
Prova.
Parte 1: (⇒)
3. Como img(𝑓 ) = dom(𝑓 −1 ) = 𝐵, temos que 𝑓 é sobrejetora (pois, como a inversa é função,
não pode sobrar nenhum elemento em 𝐵).
Parte 2: (⇐)
5. Logo, 𝑓 −1 : 𝐵 → 𝐴.
89
Definição 53 (Princípio da Casa dos Pombos). Sejam 𝐴 e 𝐵 conjuntos finitos e seja 𝑓 : 𝐴 → 𝐵.
Então:
Em outras palavras:
Sejam 𝐴 e 𝐵 conjuntos finitos com |𝐴| = 𝑚 e |𝐵| = 𝑛. Seja 𝑓 : 𝐴 → 𝐵 uma função injetora
arbitrária. Para isso, sabemos que 𝑚 ≤ 𝑛.
O número total de funções injetoras de 𝐴 em 𝐵 pode ser calculado da seguinte maneira:
• ...
𝑛!
𝑛(𝑛 − 1)(𝑛 − 2) · · · (𝑛 − (𝑚 − 1)) = .
(𝑛 − 𝑚)!
8! 8! 8 · 7 · 6 · 5 · 4 · 3!
= = = 8 · 7 · 6 · 5 · 4 = 6720.
(8 − 5)! 3! 3!
90
7.2.2 Contagem de funções sobrejetoras
Sejam 𝐴 e 𝐵 conjuntos finitos com |𝐴| = 𝑚 e |𝐵| = 𝑛. Seja 𝑓 : 𝐴 → 𝐵 uma função sobrejetora
arbitrária. Para isso, sabemos que 𝑚 ≥ 𝑛. A ideia consiste em subtrair o número de funções que não
são sobrejetoras do número total de funções, que é 𝑛𝑚 .
Iremos iniciar numerando os elementos de 𝐵 = {𝑏1 , 𝑏2 , 𝑏3 , . . . , 𝑏𝑛 }. Para cada 𝑖 = 1, 2, . . . , 𝑛,
seja 𝐹𝑖 o conjunto de funções de 𝐴 em 𝐵 que não mapeiam nenhum elemento a 𝑏𝑖 . Pelo princípio da
inclusão-exclusão, temos:
∑︁ ∑︁ ∑︁
|𝐹1 ∪ 𝐹2 ∪ · · · ∪ 𝐹𝑛 | = |𝐹𝑖 | − |𝐹𝑖 ∩ 𝐹𝑗 | + |𝐹𝑖 ∩ 𝐹𝑗 ∩ 𝐹𝑘 | − · · ·
1≤𝑖≤𝑛 1≤𝑖<𝑗≤𝑛 1≤𝑖<𝑗<𝑘≤𝑛
|𝐹𝑖 | = (𝑛 − 1)𝑚 ,
pois cada um dos 𝑚 elementos de 𝐴 pode ser mapeado para qualquer um dos 𝑛 − 1 elementos de
𝐵 (excluindo 𝑏𝑖 ). No primeiro somatório, que envolve excluir um único elemento de 𝐵, temos 𝑛1
(︀ )︀
𝑏𝑖 e 𝑏𝑗 , e o número de funções é:
|𝐹𝑖 ∩ 𝐹𝑗 | = (𝑛 − 2)𝑚 .
E assim sucessivamente. Portanto, a expressão resultante para o número total de funções sobreje-
toras torna-se:
(︂ )︂ (︂ )︂ (︂ )︂ (︂ )︂
𝑚 𝑛 𝑚 𝑛 𝑚 𝑛 𝑚 𝑛 𝑛
𝑛 − (𝑛 − 1) + (𝑛 − 2) − (𝑛 − 3) + · · · + (−1) (𝑛 − 𝑛)𝑚 .
1 2 3 𝑛
Exemplo. Seja
𝐴 = {1, 2, 3, 4, 5}, 𝐵 = {𝑎, 𝑏, 𝑐}.
Exemplo. Seja
𝐴 = {1, 2, 3, . . . , 𝑚}, 𝐵 = {𝑎, 𝑏, 𝑐}.
91
Exemplo. Seja
𝐴 = {1, 2, 3}, 𝐵 = {4, 5}.
Escreva todas as funções 𝑓 : 𝐴 → 𝐵 e indique quais são injetoras e quais são sobrejetoras.
Exemplo. Sejam
𝐴 = {1, 2, 3, 4}, 𝐵 = {5, 6, 7},
Preencha as interrogações de modo que 𝑓 satisfaça cada uma das situações a seguir:
𝑓 = {(1, 6), (2, 6), (3, 9), (4, 7), (5, 7)}, 𝑔 = {(6, 10), (7, 11), (8, 12), (9, 13)}.
𝑔 ∘ 𝑓 = 𝑔[𝑓 (𝑥)] = {(1, 10), (2, 10), (3, 13), (4, 11), (5, 11)}.
92
b) Note que o domínio da composição é o mesmo do domínio de 𝑓 :
dom(𝑔 ∘ 𝑓 ) = dom(𝑓 ) = 𝐴.
c) Cálculo específico:
(𝑔 ∘ 𝑓 )(2) = 𝑔[𝑓 (2)] = 𝑔(6) = 10.
Portanto,
𝑔 ∘ 𝑓 (4) = 2 · 42 + 5 = 2 · 16 + 5 = 32 + 5 = 37
93
Portanto,
𝑓 ∘ 𝑔(4) = 4 · 42 + 12 · 4 + 10 = 4 · 16 + 48 + 10 = 64 + 48 + 10 = 122
Portanto, a composição de funções não é uma operação comutativa. Porém, a seguir veremos que
ela é associativa.
ℎ ∘ (𝑔 ∘ 𝑓 ) = (ℎ ∘ 𝑔) ∘ 𝑓
Demonstração. Primeiramente, devemos verificar que os domínios das duas funções são iguais.
Como sabemos que dom(𝑔 ∘ 𝑓 ) = dom(𝑓 ), temos:
dom[(ℎ ∘ 𝑔) ∘ 𝑓 ] = dom(𝑓 ) = 𝐴
ℎ ∘ (𝑔 ∘ 𝑓 )(𝑎) = (ℎ ∘ 𝑔) ∘ 𝑓 (𝑎)
De fato,
ℎ ∘ (𝑔 ∘ 𝑓 )(𝑎) = ℎ[(𝑔 ∘ 𝑓 )(𝑎)] = ℎ{𝑔[𝑓 (𝑎)]}
(A) Mostre que se ambas as funções 𝑓 e 𝑔 são injetoras, então 𝑓 ∘ 𝑔 também é injetora.
𝑎1 = 𝑎2
94
(e) Portanto, 𝑓 ∘ 𝑔 é injetora.
(B) Mostre que se ambas as funções 𝑓 e 𝑔 são sobrejetoras, então 𝑓 ∘ 𝑔 também é sobrejetora.
𝑓 (𝑏) = 𝑐
𝑔(𝑎) = 𝑏
(d) Logo,
𝑓 ∘ 𝑔(𝑎) = 𝑓 [𝑔(𝑎)] = 𝑓 (𝑏) = 𝑐
e, portanto, 𝑓 ∘ 𝑔 é sobrejetora.
Esses dois resultados nos dizem que se temos duas bijeções 𝑓 : 𝐴 → 𝐵 e 𝑔 : 𝐵 → 𝐶, então a
composição 𝑓 ∘ 𝑔 também é uma bijeção.
𝐼𝐴 = {(𝑎, 𝑎) : 𝑎 ∈ 𝐴}
ou seja,
∀𝑎 ∈ 𝐴, 𝐼𝐴 (𝑎) = 𝑎.
𝑓 ∘ 𝐼𝐴 = 𝐼𝐵 ∘ 𝑓 = 𝑓.
Demonstração. Considere 𝑓 ∘ 𝐼𝐴 e 𝑓 :
2. Seja 𝑎 ∈ 𝐴 arbitrário:
𝑓 ∘ 𝐼𝐴 (𝑎) = 𝑓 [𝐼𝐴 (𝑎)] = 𝑓 (𝑎).
Considere agora 𝐼𝐵 ∘ 𝑓 e 𝑓 :
95
1. dom(𝐼𝐵 ∘ 𝑓 ) = dom(𝑓 ) = 𝐴.
2. Seja 𝑎 ∈ 𝐴 arbitrário:
𝐼𝐵 ∘ 𝑓 (𝑎) = 𝐼𝐵 [𝑓 (𝑎)] = 𝑓 (𝑎).
Portanto, 𝑓 ∘ 𝐼𝐴 = 𝐼𝐵 ∘ 𝑓 = 𝑓 .
(a) 𝑓 ∘ 𝑓 −1 = 𝐼𝐵
(b) 𝑓 −1 ∘ 𝑓 = 𝐼𝐴
𝐼𝐵 (𝑏) = 𝑏
Portanto, 𝑓 ∘ 𝑓 −1 = 𝐼𝐵 .
𝑓 −1 ∘ 𝑓 = 𝐼𝐴
𝑦+3
𝑦 = 2𝑥 − 3 =⇒ 𝑥 =
2
Portanto:
𝑦+3
𝑓 −1 (𝑦) =
2
Para verificar que 𝑓 −1 realmente inverte os pares ordenados de 𝑓 , consideremos 𝑥 = 7:
11 + 3
𝑓 (7) = 2 · 7 − 3 = 11 e 𝑓 −1 (11) = =7
2
96
Agora, as composições:
(︂ )︂
−1
(︁
−1
)︁ 𝑥+3 𝑥+3
𝑓 ∘𝑓 (𝑥) = 𝑓 𝑓 (𝑥) = 𝑓 =2· −3=𝑥
2 2
(︁ )︁ 2𝑥 − 3 + 3
𝑓 −1 ∘ 𝑓 (𝑥) = 𝑓 −1 𝑓 (𝑥) = 𝑓 −1 (2𝑥 − 3) = =𝑥
2
Logo, ambas as composições resultam na função identidade, que mapeia 𝑥 em 𝑥.
𝑥
𝑓 (𝑥) = 2𝑥 − 1, 𝑔(𝑥) = +4
2
Encontre:
(b) (𝑔 −1 ∘ 𝑓 −1 )(𝑥)
O que você conclui? Isso não é mera coincidência. O resultado a seguir formaliza o fato observado
na resolução do exercício anterior.
ℎ ∘ (𝑔 −1 ∘ 𝑓 −1 ) = (𝑓 ∘ 𝑔) ∘ (𝑔 −1 ∘ 𝑓 −1 )
𝑓 ∘ (𝑔 ∘ 𝑔 −1 ) ∘ 𝑓 −1 = 𝑓 ∘ 𝐼𝐵 ∘ 𝑓 −1 = 𝑓 ∘ 𝑓 −1 = 𝐼𝐴
Definição 56 (Composição de ordem 𝑛). A composição de ordem 𝑛 de uma função 𝑓 consigo mesma,
denotada por 𝑓 (𝑛) , é dada por:
𝑓 (𝑛) = 𝑓 ∘ 𝑓 ∘ · · · ∘ 𝑓
⏟ ⏞
𝑛 vezes
97
O resultado a seguir mostra que a composição de ordem 𝑛 da função inversa é a inversa da com-
posição de ordem 𝑛:
Teorema 28.
(𝑓 −1 )(𝑛) = (𝑓 (𝑛) )−1
ℎ∘(𝑓 −1 )(𝑛) = 𝑓 (𝑛) ∘(𝑓 −1 )(𝑛) = 𝑓 (𝑛−1) ∘𝑓 ∘𝑓 −1 ∘(𝑓 −1 )(𝑛−1) = 𝑓 (𝑛−1) ∘𝐼𝐴 ∘(𝑓 −1 )(𝑛−1) = 𝑓 (𝑛−1) ∘(𝑓 −1 )(𝑛−1)
Repetindo esse processo mais 𝑛 − 1 vezes, chegamos na função identidade. Portanto, a inversa da
composição de ordem 𝑛 é igual à composição das inversas, e a prova está concluída.
98
8 Somatórios
O conceito de somatório é uma ferramenta fundamental da Matemática, utilizada para expressar
de maneira compacta a soma de uma sequência de termos. Em vez de escrevermos explicitamente
∑︀
cada parcela, utilizamos a notação sigma ( ), que nos permite representar grandes somas de forma
clara, organizada e eficiente. Essa notação é especialmente útil quando lidamos com padrões ou
progressões, onde os termos seguem uma regra específica.
Na Matemática Discreta, os somatórios aparecem com frequência no estudo de séries numéricas,
análise de algoritmos, probabilidade, estatística e em diversas áreas da computação. Por exemplo,
ao calcularmos o número total de operações de um algoritmo, muitas vezes precisamos somar uma
sequência de valores que representam o custo em cada etapa. A notação de somatório fornece a
formalização necessária para descrever esses cálculos com precisão.
Além da definição básica, é importante conhecer as principais propriedades algébricas dos so-
matórios, que permitem simplificar expressões e facilitar a resolução de problemas. Propriedades
como linearidade, decomposição e manipulação de índices tornam o trabalho com somatórios mais
sistemático e reduzem cálculos complexos a formas mais tratáveis.
Neste capítulo, estudaremos a notação e as propriedades dos somatórios, explorando exemplos
clássicos, como a soma dos primeiros números naturais e a soma de progressões aritméticas e geomé-
tricas. Também veremos como os somatórios se relacionam com outras ferramentas matemáticas já
apresentadas, estabelecendo um elo entre estruturas discretas e métodos de cálculo mais avançados.
21 + 22 + 23 + 24 + . . . + 210
10
∑︁
2𝑘
𝑘=1
em que 𝑓 (𝑘) é uma função arbitrária de 𝑘. Também é possível utilizar um predicado para expressar
a regra de cada termo do somatório:
99
∑︁
𝑓 (𝑘)
𝑘∈𝐴 / 𝑃 (𝑘)
onde o conjunto 𝐴 é o conjunto dos naturais (N), o predicado 𝑃 (𝑘) denota que 𝑘 é um número
primo e a função 𝑓 (𝑘) = 𝑘1 (inverso de 𝑘). Esse somatório corresponde a:
1 1 1 1 1 1
+ + + + + + ...
2 3 5 7 11 13
A seguir apresentamos uma lista de somatórios básicos que já demonstramos durante a aula sobre
indução matemática:
1. 𝑛
∑︁
1 = 1 + 1 + 1 + ... + 1 = 𝑛
𝑘=1
2. 𝑛
∑︁ 𝑛(𝑛 + 1)
𝑘= (já provamos por indução)
𝑘=1
2
3. 𝑛
∑︁ 𝑛(𝑛 + 1)(2𝑛 + 1)
𝑘2 = (já provamos por indução)
𝑘=1
6
4. 𝑛 [︂ ]︂2
∑︁ 𝑛(𝑛 + 1)
3
𝑘 = (iremos provar por indução a seguir)
𝑘=1
2
5.
𝑛−1
∑︁
2𝑘 = 2𝑛 − 1 (já provamos por indução)
𝑘=0
Para relembrar como podemos provar que esses somatórios são válidos, iremos demonstrar a
validade do item (4) por indução matemática.
Devemos iniciar com a base. Seja 𝑃 (𝑛) a afirmação a seguir:
𝑛 )︂2
𝑛2 (𝑛 + 1)2
(︂
∑︁
3 𝑛(𝑛 + 1)
𝑃 (𝑛) : 𝑘 = =
𝑘=1
2 4
Base:
1
∑︁ 12 (1 + 1)2 4
𝑃 (1) : 𝑘 3 = 13 = 1, e = = 1.
𝑘=1
4 4
Passo de indução: Suponha que 𝑃 (𝑛) seja válida para um 𝑛 arbitrário, isto é:
100
𝑛
∑︁ 𝑛2 (𝑛 + 1)2
𝑘3 = .
𝑘=1
4
𝑛+1
(︃ 𝑛 )︃
∑︁ ∑︁
3 3
𝑘 = 𝑘 + (𝑛 + 1)3
𝑘=1 𝑘=1
𝑛+1
∑︁ 𝑛2 (𝑛 + 1)2
𝑘3 = + (𝑛 + 1)3 .
𝑘=1
4
𝑛+1
∑︁ 𝑛2 (𝑛 + 1)2 + 4(𝑛 + 1)3
𝑘3 = .
𝑘=1
4
2
Fatorando (𝑛 + 1) :
𝑛+1 (︀ )︀
∑︁ (𝑛 + 1)2 𝑛2 + 4𝑛 + 4
3
𝑘 = .
𝑘=1
4
𝑛+1
∑︁ (𝑛 + 1)2 (𝑛 + 2)2
3
𝑘 = .
𝑘=1
4
Ou seja:
𝑛+1 (︂ )︂2
∑︁
3 (𝑛 + 1)(𝑛 + 2)
𝑘 = .
𝑘=1
2
Conclusão: Portanto, pelo princípio da indução matemática, 𝑃 (𝑛) é válida para todo 𝑛 ∈ N. Note
que a prova por indução nos permite mostrar que a igualdade apresentada é válida para todo 𝑛, porém
não nos permite resolver o somatório, isto é, partir da notação de somatório e chegar a uma fórmula
fechada em função de 𝑛. Para isso, devemos utilizar propriedades algébricas que simplifiquem os
somatórios.
101
1) Substituição de variáveis
2) Distributiva
Em outras palavras, é possível mover as constantes para fora do somatório colocando-as em evidência.
3) Associativa
4) Decomposição de domínio
Ou seja, podemos decompor o somatório em dois somatórios menores, desde que cada valor de índice
apareça apenas em um dos subconjuntos.
Por exemplo: se 𝐴 é o conjunto dos números naturais, 𝐴1 o conjunto dos pares e 𝐴2 o conjunto
dos ímpares, então todo índice em 𝐴1 não está em 𝐴2 .
5) Comutatividade
102
Ou seja, podemos embaralhar os termos de um somatório que o valor final não se altera.
6) Somas telescópicas
Ou seja, o valor do somatório das diferenças é igual à diferença entre o último elemento e o primeiro.
Prova:
𝑛+1
∑︁ 𝑛
∑︁
𝑆= 𝑥𝑖 − 𝑥𝑘
𝑖=2 𝑘=1
(c) Removendo o último termo do primeiro somatório e o primeiro termo do segundo, obtemos:
(︃ 𝑛 )︃ (︃ 𝑛
)︃
∑︁ ∑︁
𝑆= 𝑥𝑖 + 𝑥𝑛+1 − 𝑥1 + 𝑥𝑘 = 𝑥𝑛+1 − 𝑥1
𝑖=2 𝑘=2
Assim, temos:
𝑛
∑︁ 𝑛
]︀ ∑︁
(𝑘 + 1)2 − 𝑘 2 =
[︀
(2𝑘 + 1).
𝑘=1 𝑘=1
103
Portanto: 𝑛
∑︁
(𝑛 + 1)2 − 1 = (2𝑘 + 1).
𝑘=1
Ou seja:
𝑛
∑︁
2
(𝑛 + 1) − 1 = 2 𝑘 + 𝑛.
𝑘=1
de modo que:
(𝑘 + 1)3 − 𝑘 3 = 3𝑘 2 + 3𝑘 + 1.
Aplicando o somatório em ambos os lados, temos uma soma telescópica do lado esquerdo:
𝑛
∑︁ 𝑛
∑︁
3 3 3
[︀ ]︀ (︀ 2 )︀
(𝑘 + 1) − 𝑘 = (𝑛 + 1) − 1 = 3𝑘 + 3𝑘 + 1 .
𝑘=1 𝑘=1
Assim: 𝑛 𝑛 𝑛
∑︁ ∑︁ ∑︁
3 2
(𝑛 + 1) − 1 = 3 𝑘 +3 𝑘+ 1.
𝑘=1 𝑘=1 𝑘=1
Sabemos que:
𝑛 𝑛
∑︁ ∑︁ 𝑛(𝑛 + 1)
1=𝑛 e 𝑘= .
𝑘=1 𝑘=1
2
104
Substituindo:
𝑛 3𝑛(𝑛+1)
∑︁
2 (𝑛 + 1)3 − 1 − 2
−𝑛
𝑘 = .
𝑘=1
3
portanto:
𝑛 3𝑛2 +3𝑛
∑︁
2 𝑛3 + 3𝑛2 + 3𝑛 − 2
−𝑛
𝑘 = .
𝑘=1
3
Reduzindo os termos: 𝑛
∑︁ 2𝑛3 + 3𝑛2 + 𝑛
𝑘2 = .
𝑘=1
6
Colocando 𝑛 em evidência: 𝑛
∑︁ 𝑛(2𝑛2 + 3𝑛 + 1)
2
𝑘 = .
𝑘=1
6
Note que
2𝑘 + 1 = 2𝑘 · 2,
o que implica
2𝑘 + 1 = 2𝑘 + 2𝑘,
e, portanto,
2𝑘 = 2𝑘 + 1 − 2𝑘.
𝑛−1
∑︁
(2𝑘 + 1 − 2𝑘).
𝑘=0
105
Pela definição de somas telescópicas, temos:
𝑛−1
∑︁
(2𝑘 + 1 − 2𝑘) = 2𝑛 − 20 = 2𝑛 − 1.
𝑘=0
2𝑘−1 = 2𝑘 − 2𝑘−1 .
Assim,
𝑛
∑︁ 𝑛
∑︁ 𝑛
∑︁
𝑘 𝑘−1 𝑘
𝑆= 𝑘(2 − 2 )= 𝑘2 − 𝑘 2𝑘−1 .
𝑘=1 𝑘=1 𝑘=1
𝑛
∑︁ 𝑛−1
∑︁ 𝑛−1
∑︁ 𝑛−1
∑︁
𝑘 2𝑘−1 = (𝑖 + 1)2𝑖 = 𝑖 2𝑖 + 2𝑖 .
𝑘=1 𝑖=0 𝑖=0 𝑖=0
Portanto,
𝑛
∑︁ 𝑛−1
∑︁ 𝑛−1
∑︁
𝑘 𝑖
𝑆= 𝑘2 − 𝑖2 − 2𝑖 .
𝑘=1 𝑖=0 𝑖=0
Note que a diferença entre os dois primeiros somatórios é apenas o 𝑛-ésimo termo:
𝑛−1
∑︁
𝑛
𝑆 = 𝑛2 − 2𝑖 .
𝑖=0
𝑆 = 𝑛 2𝑛 − (2𝑛 − 1) = 2𝑛 (𝑛 − 1) + 1.
Exemplo. Calcule o somatório dos 𝑛 primeiros termos de uma P.A. com termo inicial 𝑎0 e razão 𝑟,
dado por:
𝑛−1
∑︁
𝑆= (𝑎0 + 𝑘𝑟).
𝑘=0
106
Aplicando a distributiva, temos:
𝑛−1 𝑛−1
∑︁ ∑︁ (𝑛 − 1)𝑛
𝑆= 𝑎0 + 𝑘𝑟 = 𝑛𝑎0 + 𝑟 .
𝑘=0 𝑘=0
2
𝑛(𝑎0 + 𝑎𝑛 )
𝑆= .
2
Observe que
𝑏𝑘+1 − 𝑏𝑘 = 𝑏𝑘 (𝑏 − 1),
𝑏𝑘+1 − 𝑏𝑘
𝑏𝑘 = .
𝑏−1
Utilize essa propriedade para escrever o somatório como uma soma telescópica.
Exercício: Calcule o somatório dos 𝑛 primeiros termos de uma P.G. com termo inicial 𝑎 e razão 𝑟,
dado por:
𝑛−1
∑︁
𝑆= 𝑎𝑟𝑘 .
𝑘=0
Observe que
1 1 1
= − .
𝑘(𝑘 + 1) 𝑘 𝑘+1
Portanto, o somatório pode ser calculado utilizando a soma telescópica:
𝑛 (︂ )︂
∑︁ 1 1 1 𝑛
𝑆= − =1− = .
𝑘=1
𝑘 𝑘+1 𝑛+1 𝑛+1
107
8.3 Considerações Finais
Neste capítulo, exploramos os conceitos fundamentais relacionados a somatórios, apresentando
técnicas e propriedades que facilitam o cálculo de séries finitas e infinitas. Abordamos desde soma-
tórios simples envolvendo progressões aritméticas e geométricas até somatórios mais complexos que
podem ser resolvidos utilizando a técnica de soma telescópica.
Observou-se que, apesar da aparente complexidade de algumas expressões, a aplicação sistemá-
tica das propriedades dos somatórios, juntamente com manipulações algébricas adequadas, permite
simplificações significativas. Ressaltamos também a importância da notação sigma, que fornece uma
forma concisa e organizada de representar somatórios, sendo amplamente utilizada em Matemática
Discreta, Probabilidade, Algoritmos e Análise de Complexidade.
Por fim, os exercícios propostos ao longo do capítulo visam consolidar a compreensão das técni-
cas apresentadas, desenvolvendo a habilidade de identificar padrões, aplicar propriedades e resolver
somatórios de forma eficiente. O domínio dessas ferramentas é essencial para o estudo de tópicos
subsequentes em Matemática Discreta, como recorrências, combinatória e análise de algoritmos.
108
9 Sequências e relações de recorrência
Sequências desempenham um papel fundamental em Matemática Discreta, servindo como uma
ferramenta essencial para modelar e analisar padrões, contagens e processos discretos. Uma sequência
é, de maneira geral, uma lista ordenada de números ou objetos, em que cada elemento é identificado
por sua posição na lista. Compreender o comportamento de sequências permite aos estudantes explo-
rar propriedades numéricas, desenvolver raciocínio lógico e preparar o terreno para tópicos avançados,
como combinatória, análise de algoritmos e teoria dos grafos.
As relações de recorrência são equações que definem os termos de uma sequência com base em
seus valores anteriores. Elas surgem naturalmente em muitos problemas discretos, como contagem
de caminhos, crescimento de populações discretas, análise de algoritmos recursivos e geração de
números combinatórios. Resolver uma relação de recorrência consiste em encontrar uma expressão
explícita para o 𝑛-ésimo termo da sequência, permitindo previsões e análises sem a necessidade de
calcular todos os termos anteriores.
O estudo de sequências e recorrências também está intimamente ligado à identificação de padrões
e à formulação de generalizações. Por meio de exemplos como progressões aritméticas, progressões
geométricas e sequências mais complexas, os alunos aprendem a aplicar técnicas algébricas e mé-
todos de indução matemática para deduzir fórmulas gerais. Além disso, o domínio de recorrências
lineares com coeficientes constantes é uma ferramenta poderosa, amplamente utilizada na resolução
de problemas combinatórios e na análise de desempenho de algoritmos recursivos.
Este capítulo tem como objetivo apresentar conceitos fundamentais, técnicas de resolução e apli-
cações de sequências e relações de recorrência, oferecendo uma base sólida para o estudo de tópicos
avançados em Matemática Discreta. Exercícios e exemplos práticos ilustram como essas ferramentas
podem ser aplicadas em diferentes contextos, incentivando o desenvolvimento do raciocínio lógico e
da habilidade de modelar problemas discretos de forma eficiente.
9.1 Recorrências
Recorrências são sequências matemáticas que obedecem a uma lei de formação, ou seja, o pró-
ximo elemento da série é uma função de um ou mais elementos anteriores. Existem diversas recorrên-
cias que surgem naturalmente na matemática e outras ciências exatas como a física e a computação.
Um dos exemplos mais conhecidos de recorrência é a sequência de Fibonacci, em que dados os dois
primeiros termos iguais a 1, cada novo termo é computado pela soma dos 2 termos anteriores. Um
problema bastante relevante no estudo de recorrências consiste em resolver analiticamente uma recor-
rência. Isso significa encontrar uma fórmula fechada para calcular o n-ésimo termo da sequência sem
a necessidade de gerar todos os n - 1 termos anteriores. O objetivo desta aula consiste em apresen-
tar uma introdução as recorrências lineares homogêneas de primeira, segunda e terceira ordens, bem
como técnicas algébricas de como resolvê-las analiticamente.
Definição 57 (Recorrência). Uma recorrência é uma regra que nos permite calcular um termo qual-
109
quer de uma sequência em função de termos anteriores.
O objetivo aqui consiste em estudar sequências numéricas que possuem uma lei de formação. Por
exemplo, considere a sequência 𝑆 a seguir:
𝑆 ′ = (1, 3, 5, . . .)
Quem é o próximo termo? Seria o número 7? Parece que sim. Mas e se a lei de formação oculta fosse
dada por:
𝑛3 𝑛2 𝑛
𝑇𝑛 = − + + .
6 2 3
Note que:
13 12 1 1 1 1
𝑇1 = − + + = − + + = 1,
6 2 3 6 2 3
23 22 2 8 2 4 8
𝑇2 = − + + = − + 2 + = − + = 3,
6 2 3 6 3 3 3
33 32 3 27 9 9 9
𝑇3 = − + + = − + + 1 = − + + 1 = 5,
6 2 3 6 2 2 2
43 42 4 64 4 32 4 28 24
𝑇4 = − + + =− +8+ =− +8+ =− + = 6.
6 2 3 6 3 3 3 3 3
Veja que o quarto termo da sequência deveria ser 6 e não 7. Portanto, em nossos estudos, dese-
jamos aplicar um formalismo matemático e não simplesmente usar a intuição. Essa lei de formação
está na forma fechada, pois basta plugarmos o valor de 𝑛 para obtermos o 𝑛-ésimo elemento da
sequência.
Porém, em diversos problemas, a lei de formação aparece na forma recursiva, como:
𝑇𝑛+1 = 2𝑇𝑛 + 1, 𝑇1 = 3.
3, 7, 15, 31, . . .
Uma possível desvantagem da forma recursiva é que, para gerar o 𝑛-ésimo termo da sequência,
temos que calcular os 𝑛 − 1 termos anteriores.
Nossos objetos de estudo são as sequências numéricas com lei de formação na forma recursiva.
110
Dizemos que resolver uma recorrência consiste em gerar a forma fechada a partir da forma recur-
siva.
Uma observação interessante é que uma mesma lei de formação pode ser utilizada para gerar mais
de uma sequência. Por exemplo, seja a lei:
𝑇𝑛+1 = 𝑇𝑛 + 2.
Ela pode ser utilizada para gerar todos os números ímpares, se 𝑇1 = 1, ou todos os números pares, se
𝑇1 = 0. Portanto, os termos iniciais possuem um papel muito importante.
Definição 58 (Progressão Aritmética (P.A.)). Uma progressão aritmética é uma recorrência em que:
𝑇𝑛+1 = 𝑇𝑛 + 𝑟, 𝑇1 = 𝑎,
onde 𝑎 é o primeiro elemento da sequência e 𝑟 é a razão. Sendo assim, uma P.A. é da forma:
onde 𝑎 é o primeiro elemento da sequência e 𝑞 é a razão. Sendo assim, uma P.G. é da forma:
O objetivo consiste em mover todos os discos para uma outra haste, obedecendo apenas duas
regras:
111
1. Podemos mover apenas um disco por vez;
Move A → B
Move A → C
Move B → C
Move A → B
Move A → C
Move B → C
Move A → B
Move C → A
Move C → B
Move A → B
Utilizando uma abordagem recursiva, note que são 3 movimentos para os dois menores discos,
1 movimento para o maior e mais 3 movimentos para os dois menores.
• Para 𝑛 = 5, teremos:
15 + 1 + 15 = 31 movimentos.
A essa altura, deve estar claro que temos a seguinte estrutura recursiva:
112
Assim, a recorrência fica definida como:
𝑇𝑛 = 2𝑇𝑛−1 + 1, 𝑇1 = 1.
Porém, se quisermos descobrir o número de movimentos para 𝑛 = 100, devemos calcular todos
os termos da sequência de 2 até 100.
Como resolver essa recorrência, ou seja, obter uma fórmula fechada? Vamos expandir a recorrên-
cia:
𝑇1 = 1
𝑇2 = 2𝑇1 + 1
𝑇3 = 2𝑇2 + 1
𝑇4 = 2𝑇3 + 1
𝑇5 = 2𝑇4 + 1
𝑇6 = 2𝑇5 + 1
..
.
𝑇𝑛−2 = 2𝑇𝑛−3 + 1
𝑇𝑛−1 = 2𝑇𝑛−2 + 1
𝑇𝑛 = 2𝑇𝑛−1 + 1
A ideia consiste em somar tudo do lado esquerdo e tudo do lado direito e utilizar a igualdade para
chegar em uma expressão fechada. Porém, gostaríamos que a soma fosse telescópica, para simplificar
os cálculos. Partindo de baixo para cima, note que para o termo 𝑇𝑛−1 ser cancelado, a penúltima
equação precisa ser multiplicada por 2. Para que o termo 𝑇𝑛−2 seja cancelado, a antepenúltima equa-
113
ção precisa ser multiplicada por 22 . E assim sucessivamente, o que nos leva ao seguinte conjunto de
equações:
2𝑛−1 𝑇1 = 2𝑛−1
2𝑛−2 𝑇2 = 2𝑛−1 𝑇1 + 2𝑛−2
2𝑛−3 𝑇3 = 2𝑛−2 𝑇2 + 2𝑛−3
2𝑛−4 𝑇4 = 2𝑛−3 𝑇3 + 2𝑛−4
2𝑛−5 𝑇5 = 2𝑛−4 𝑇4 + 2𝑛−5
2𝑛−6 𝑇6 = 2𝑛−5 𝑇5 + 2𝑛−6
..
.
22 𝑇𝑛−2 = 23 𝑇𝑛−3 + 22
2𝑇𝑛−1 = 22 𝑇𝑛−2 + 2
𝑇𝑛 = 2𝑇𝑛−1 + 1
Somando todas as linhas, temos uma soma telescópica, pois os mesmos termos aparecem do lado
esquerdo e direito das igualdades, o que resulta em:
𝑛−1
∑︁
𝑇𝑛 = 2𝑘 = 2𝑛 − 1,
𝑘=0
como já vimos nas aulas anteriores. Portanto, essa é a fórmula fechada para a recorrência da Torre de
Hanói. Testando alguns elementos, temos exatamente a mesma sequência obtida anteriormente:
𝑥𝑛 = 3𝑥𝑛−1 + 5, 𝑥1 = 2
114
𝑥1 = 2
𝑥2 = 3𝑥1 + 5
𝑥3 = 3𝑥2 + 5
𝑥4 = 3𝑥3 + 5
𝑥5 = 3𝑥4 + 5
𝑥6 = 3𝑥5 + 5
..
.
𝑥𝑛−2 = 3𝑥𝑛−3 + 5
𝑥𝑛−1 = 3𝑥𝑛−2 + 5
𝑥𝑛 = 3𝑥𝑛−1 + 5
De baixo para cima, vamos multiplicar por potências de 3 para tornar a soma telescópica:
3𝑛−1 𝑥1 = 2 · 3𝑛−1
3𝑛−2 𝑥2 = 3𝑛−1 𝑥1 + 5 · 3𝑛−2
3𝑛−3 𝑥3 = 3𝑛−2 𝑥2 + 5 · 3𝑛−3
3𝑛−4 𝑥4 = 3𝑛−3 𝑥3 + 5 · 3𝑛−4
3𝑛−5 𝑥5 = 3𝑛−4 𝑥4 + 5 · 3𝑛−5
3𝑛−6 𝑥6 = 3𝑛−5 𝑥5 + 5 · 3𝑛−6
..
.
32 𝑥𝑛−2 = 33 𝑥𝑛−3 + 5 · 32
3𝑥𝑛−1 = 32 𝑥𝑛−2 + 5 · 3
𝑥𝑛 = 3𝑥𝑛−1 + 5
Agora, temos uma soma telescópica. Ao somar todos os lados esquerdos e igualar com todos os
lados direitos, obtemos:
ou, equivalentemente,
𝑛−2
∑︁
𝑛−1
𝑥𝑛 = 2 · 3 +5 3𝑘 . (*)
𝑘=0
Note que o somatório representa a soma dos 𝑛 − 1 primeiros termos de uma PG cujo termo inicial
é 1 e a razão é 3. Pela fórmula já provada em aulas anteriores:
𝑞𝑚 − 1
𝑆𝑚 = ,
𝑞−1
115
temos, para 𝑚 = 𝑛 − 1, 𝑞 = 3:
3𝑛−1 − 1 3𝑛−1 − 1
𝑆𝑛−1 = = .
3−1 2
Voltando à equação (*), temos:
3𝑛−1 − 1
𝑥𝑛 = 2 · 3 𝑛−1 + 5 · .
2
Após alguma álgebra, obtemos:
3 𝑛+1 − 5
𝑥𝑛 = .
2
𝑥1 = 12 (32 − 5) = 12 (9 − 5) = 2,
𝑥2 = 12 (33 − 5) = 12 (27 − 5) = 11,
𝑥3 = 12 (34 − 5) = 12 (81 − 5) = 38,
𝑥4 = 12 (35 − 5) = 12 (243 − 5) = 119.
Portanto, a fórmula fechada está correta. A seguir, veremos uma metodologia simples para a
resolução de recorrências lineares de primeira ordem.
𝑥𝑛+1 = 2𝑥𝑛 + 3𝑛 , 𝑥1 = 1.
𝑥1 = 1,
𝑥2 = 2 · 1 + 3 = 5,
𝑥3 = 2 · 5 + 9 = 19,
𝑥4 = 2 · 19 + 27 = 65.
116
Passo 1: Dividir tudo por 2 𝑛+1 :
𝑥𝑛+1 2𝑥𝑛 3𝑛
= + .
2 𝑛+1 2𝑛+1 2 𝑛+1
Ou seja, (︂ )︂𝑛
𝑥𝑛+1 𝑥𝑛 1 3
𝑛+1
= 𝑛+
2 2 2 2
𝑥𝑛
𝑦𝑛 = .
2𝑛
Note que, ao aplicar um somatório de 1 até 𝑛 − 1 em ambos os lados, temos os seguintes termos:
(︂ )︂1
1 3
𝑦2 − 𝑦1 = ,
2 2
(︂ )︂2
1 3
𝑦3 − 𝑦2 = ,
2 2
..
.
(︂ )︂𝑛−1
1 3
𝑦𝑛 − 𝑦𝑛−1 =
2 2
3
Note que o termo entre colchetes é a soma dos 𝑛 − 1 primeiros termos de uma P.G. de razão 2
e
termo inicial 32 . Aplicando a fórmula da soma de uma P.G., chegamos em:
⎡ (︁(︀ )︀𝑛−1 )︁ ⎤
3 3
1 ⎣2 2
−1
𝑦𝑛 − 𝑦1 = 3
⎦
2 2
−1
117
Simplificando a expressão, temos:
(︃(︂ )︂ )︃ (︂ )︂
𝑛−1 𝑛
3 3 3 3
𝑦𝑛 − 𝑦1 = −1 = −
2 2 2 2
𝑥𝑛 𝑥1 1
Como 𝑦𝑛 = 𝑛
, temos que 𝑦1 = = o que nos leva a:
2 2 2
(︂ )︂𝑛
𝑥𝑛 1 3 3
𝑛
− = −
2 2 2 2
𝑥𝑛 = 3𝑛 − 2𝑛 .
𝑥1 = 3 − 2 = 1 (92)
𝑥2 = 9 − 4 = 5 (93)
𝑥3 = 27 − 8 = 19 (94)
𝑥4 = 81 − 16 = 65 (95)
o que mostra que temos a mesma sequência produzida pela recorrência inicial.
𝑏 𝑐
𝑥𝑛+2 = − 𝑥𝑛+1 − 𝑥𝑛 .
𝑎 𝑎
118
Muitas recorrências que modelam fenômenos da natureza podem ser expressas por esse padrão.
O exemplo mais famoso é a sequência de Fibonacci, dada por:
𝑥𝑛+2 − 𝑥𝑛+1 − 𝑥𝑛 = 0.
𝑦𝑛+1 − 2𝑦𝑛 = 0,
ou seja,
𝑦𝑛+1 = 2𝑦𝑛 .
𝑦1 = 𝑥2 − 3𝑥1 = 13 − 15 = −2,
119
Mas de (*) sabemos que:
𝑥𝑛+1 − 3𝑥𝑛 = −2𝑛 ,
𝑥𝑛+1 = 3𝑥𝑛 − 2𝑛 .
Utilizando o método apresentado na seção anterior, temos que 𝑎 = 3, o que nos leva a:
(︂ )︂𝑛
𝑥𝑛+1 𝑥𝑛 1 2
𝑛+1
− 𝑛 =−
3 3 3 3
Definindo
𝑥𝑛
𝑧𝑛 = ,
3𝑛
podemos escrever: (︂ )︂𝑛
1 2
𝑧𝑛+1 − 𝑧𝑛 = −
3 3
Ao aplicar somatório para 𝑛 variando de 1 até 𝑛 − 1 em ambos os lados, temos uma soma teles-
cópica, uma vez que:
(︂ )︂1 (︂ )︂2 (︂ )︂𝑛−1
1 2 1 2 1 2
𝑧2 − 𝑧1 = − , 𝑧3 − 𝑧2 = − , , ..., 𝑧𝑛 − 𝑧𝑛−1 =− , ,
3 3 3 3 3 3
O somatório denota a soma dos 𝑛 − 1 primeiros termos de uma P.G. com primeiro termo igual a
2
3
e razão igual a 23 . Aplicando a fórmula da soma da P.G., temos:
[︃ (︀ )︀𝑛−1 ]︃ (︂ )︂
2 𝑛
1 2 3 − 1 2 2
𝑧𝑛 − 𝑧1 = − 2 = −
3 3 3 −1 3 3
120
Calculando os 4 primeiros termos da sequência, temos:
𝑥1 = 2 + 3 = 5,
𝑥2 = 4 + 9 = 13,
𝑥3 = 8 + 27 = 35,
𝑥4 = 16 + 81 = 97,
...
o que mostra que a fórmula fechada está correta. Note que a recorrência original era dada por
𝑥2 − 5𝑥 + 6 = 0
são justamente 2 e 3 (que são as bases das duas funções componentes da recorrência: 2𝑛 e 3𝑛 ). Isso
não é mera coincidência. O resultado que veremos a seguir mostra essa relação entre recorrências
lineares homogêneas de segunda ordem e equações do segundo grau.
𝑥𝑘 = 𝑝𝑥𝑘−1 + 𝑞𝑥𝑘−2
𝑡2 − 𝑝𝑡 − 𝑞 = 0.
Teorema 29. Seja uma recorrência linear homogênea de segunda ordem dada por
𝑏 𝑐
𝑥𝑛+2 = − 𝑥𝑛+1 − 𝑥𝑛 = 𝑝𝑥𝑛+1 + 𝑞𝑥𝑛 .
𝑎 𝑎
𝑎𝑥2 + 𝑏𝑥 + 𝑐 = 0.
121
i. Se 𝑟 ̸= 𝑠, então
𝑥𝑛 = 𝛼𝑟𝑛 + 𝛽𝑠𝑛 , com 𝛼, 𝛽 constantes.
ii. Se 𝑟 = 𝑠, então
𝑥𝑛 = (𝛼𝑛 + 𝛽)𝑟𝑛 ,
No caso (i), as constantes 𝛼, 𝛽 são definidas a partir dos termos iniciais da sequência:
𝑛=0: 𝛼 + 𝛽 = 𝑥0 ,
𝑛=1: 𝛼𝑟 + 𝛽𝑠 = 𝑥1 ,
𝑛=2: 𝛼𝑟2 + 𝛽𝑠2 = 𝑥2 ,
..
.
No caso (ii), as constantes são obtidas de outra forma, pois em 99% dos casos o sistema de
equações anterior (caso i) não possui solução. Veremos um exemplo a seguir de como tratar esse caso
particular.
122
Aplicando a distributiva, temos:
Como 𝑟 e 𝑠 são raízes da equação característica, elas satisfazem a relação de recorrência (Lema).
Portanto, podemos concluir que:
𝑎𝑥2 + 𝑏𝑥 + 𝑐 = 0,
Prova:
𝑎𝑥2 + 𝑏𝑥 + 𝑐 = 0,
𝑏 𝑐
𝑥2 + 𝑥 = − .
𝑎 𝑎
𝑏2
2. Note que podemos completar o quadrado, adicionando em ambos os lados:
4𝑎2
𝑏 𝑏2 𝑏2 𝑐
𝑥2 + 𝑥 + 2 = 2 − .
𝑎 4𝑎 4𝑎 𝑎
123
4. Aplicando a raiz quadrada em ambos os lados, temos:
√
𝑏 𝑏2 − 4𝑎𝑐
𝑥+ =± .
2𝑎 2𝑎
Em termos numéricos:
1 → 1 → 2 → 3 → 5 → 8 → 13 → . . .
𝑥2 − 𝑥 − 1 = 0.
124
A partir das condições iniciais, temos que:
𝑛 = 1 ⇒ 𝐴Φ + 𝐵Ψ = 1.
𝐹0 = 𝐹2 − 𝐹1 = 1 − 1 = 0.
Assim,
𝑛 = 0 ⇒ 𝐴 + 𝐵 = 0.
Dessa forma, temos que 𝐴 e 𝐵 são soluções do seguinte sistema linear de equações:
⎧
⎨𝐴 + 𝐵 = 0 (*)
⎩𝐴Φ + 𝐵Ψ = 1 (**)
𝐴Φ − 𝐴Ψ = 1 ⇒ 𝐴(Φ − Ψ) = 1.
Mas como √ √
1+ 5 1− 5
Φ= , Ψ= ,
2 2
então √ √
1+ 5 1− 5 √
Φ−Ψ= − = 5.
2 2
Logo,
1
𝐴= √ .
5
1
Voltando à equação (*), temos que 𝐵 = − √ .
5
Portanto, a fórmula fechada para a sequência de Fibonacci é:
(︃(︃ √ )︃𝑛 (︃ √ )︃𝑛 )︃
Φ𝑛 − Ψ𝑛 1 1+ 5 1− 5
𝐹𝑛 = √ =√ − .
5 5 2 2
A princípio parece que há algo de errado com a expressão anterior, pois se a sequência de Fi-
bonacci é composta apenas por inteiros, como isso pode acontecer se temos um número irracional
elevado à 𝑛-ésima potência? Porém, ao aplicar a fórmula, vemos que o resultado é exatamente o es-
perado. Faça os cálculos com o auxílio de um computador e verifique que a fórmula fechada é capaz
de gerar toda a sequência de Fibonacci de maneira exata.
125
Exemplo. Seja a sequência (𝑥𝑛 ) tal que 𝑥1 = 0 e, para todo 𝑛 > 0,
√︀
𝑥𝑛+1 = 5𝑥𝑛 + 24𝑥2𝑛 + 1.
Encontre uma fórmula fechada para 𝑥𝑛 e verifique que todo elemento da sequência é um inteiro.
𝑥1 = 0, 𝑥2 = 1, 𝑥3 = 5 + 5 = 10, 𝑥4 = 50 + 49 = 99.
Expandindo o quadrado:
𝑥2𝑛+1 − 10𝑥𝑛 𝑥𝑛+1 + 25𝑥2𝑛 = 24𝑥2𝑛 + 1,
ou seja,
(︀ )︀
(𝑥𝑛+2 − 𝑥𝑛 ) 𝑥𝑛+2 + 𝑥𝑛 − 10𝑥𝑛+1 = 0.
𝑥𝑛+2 + 𝑥𝑛 − 10𝑥𝑛+1 = 0,
isto é,
𝑥𝑛+2 = 10𝑥𝑛+1 − 𝑥𝑛 .
126
Assim, a sequência também satisfaz a recorrência linear homogênea de segunda ordem
𝑥𝑛+2 − 10𝑥𝑛+1 + 𝑥𝑛 = 0,
com raízes
√
𝑟1,2 = 5 ± 2 6.
Aplicando a distributiva:
√ √ √
𝛼(5 + 2 6) − (5 − 2 6) − 𝛼(5 − 2 6) = 0.
Colocando 𝛼 em evidência:
(︀ √ √ )︀ √
𝛼 (5 + 2 6) − (5 − 2 6) = 5 − 2 6.
Logo: √
5−2 6
𝛼= √ .
4 6
127
Substituindo na expressão de 𝛽:
√ √
5−2 6 5+2 6
𝛽 = −1 − 𝛼 = −1 − √ =− √
4 6 4 6
Como
√ √
(5 − 2 6)(5 + 2 6) = 25 − 24 = 1,
temos finalmente: √ √
(5 + 2 6) 𝑛−1 − (5 − 2 6) 𝑛−1
𝑥𝑛 = √ .
4 6
Observando a expressão, não é intuitivo que todos os elementos da sequência sejam inteiros, mas
de fato eles são. Calculando os 4 primeiros elementos da sequência, temos:
𝑥1 = 0
𝑥2 = 1
√
40 6
𝑥3 = √ = 10
4 6
√
396 6
𝑥4 = √ = 99
4 6
Teorema 31. Sejam 𝑐1 , 𝑐2 , . . . , 𝑐𝑘 números reais arbitrários. Suponha que a equação característica
de grau 𝐾
𝑥𝑘 − 𝑐1 𝑥𝑘−1 − 𝑐2 𝑥𝑘−2 − · · · − 𝑐𝑘 = 0
128
se, e somente se,
Note que
𝑎3 = 90 − 55 + 12 = 47.
𝑥3 − 6𝑥2 + 11𝑥 − 6 = 0
𝑎𝑛 𝑥𝑛 + 𝑎𝑛−1 𝑥𝑛−1 + · · · + 𝑎0 = 0
com coeficientes inteiros. Se 𝑎0 , 𝑎𝑛 são diferentes de zero, então cada solução racional
𝑝
𝑥=
𝑞
satisfaz:
i. 𝑝 é um fator inteiro de 𝑎0 ;
Vamos listar todas as possíveis raízes inteiras do polinômio em questão. Elas são:
Agora, vamos testar para ver se encontramos uma das soluções válidas.
129
𝑥=1 ⇒ 1 − 6 + 11 − 6 = 0.
Portanto, 𝑥 = 1 é raiz da equação do terceiro grau. Assim, podemos fatorá-lo para obter um
polinômio de grau 2, que é facilmente solucionado.
𝑥2 − 5𝑥 + 6
)︀
𝑥−1 𝑥3 − 6𝑥2 + 11𝑥 − 6
− 𝑥3 + 𝑥2
− 5𝑥2 + 11𝑥
5𝑥2 − 5𝑥
6𝑥 − 6
− 6𝑥 + 6
0
O quociente é:
𝑥2 − 5𝑥 + 6
e o resto é:
0.
(𝑥 − 1)(𝑥2 − 5𝑥 + 6) = 0
𝑥1 = 2, 𝑥2 = 3
𝑎𝑛 = 𝐴 · 1𝑛 + 𝐵 · 2𝑛 + 𝐶 · 3𝑛
130
Para encontrar as constantes 𝐴, 𝐵 e 𝐶, usamos as condições iniciais:
𝑛=0 ⇒ 𝐴+𝐵+𝐶 =2
𝑛=1 ⇒ 𝐴 + 2𝐵 + 3𝐶 = 5
𝑛=2 ⇒ 𝐴 + 4𝐵 + 9𝐶 = 15
𝐴+𝐵+𝐶 =2
𝐵 + 2𝐶 = 3
3𝐵 + 8𝐶 = 13
𝐴+𝐵+𝐶 =2
𝐵 + 2𝐶 = 3
2𝐶 = 4
𝑎0 = 2, 𝑎1 = 1 − 2 + 6 = 5, 𝑎2 = 1 − 4 + 18 = 15, 𝑎3 = 1 − 8 + 54 = 47
𝑎𝑛
𝑎𝑛+1 = , com 𝑎1 = 1
1 + 𝑛𝑎𝑛
Calcule 𝑎2012 .
131
9.7 Considerações finais
O estudo de sequências e relações de recorrência é fundamental em Matemática Discreta, pois
fornece as ferramentas necessárias para modelar e resolver problemas que envolvem processos defi-
nidos de forma recursiva. Desde exemplos simples, como a sequência de Fibonacci, até aplicações
mais complexas em algoritmos e ciência da computação, as recorrências permitem descrever o com-
portamento de sistemas que evoluem ao longo do tempo.
Ao longo deste capítulo, vimos que muitas recorrências podem ser resolvidas de maneira exata,
seja por manipulações algébricas diretas, seja por meio da equação característica associada. Esse
processo não apenas revela fórmulas fechadas, mas também evidencia a importância da análise das
raízes da equação característica, que determinam o formato da solução final.
Além disso, discutimos que o estudo de recorrências não se restringe a sequências lineares de
baixa ordem: os métodos apresentados podem ser generalizados, permitindo lidar com recorrências
de ordem superior e com diferentes tipos de comportamento. Essa generalização amplia o leque de
aplicações, que incluem desde a análise de algoritmos até a modelagem em biologia, economia e
engenharia.
Concluímos, portanto, que compreender sequências e recorrências é essencial não apenas para
o domínio teórico da Matemática Discreta, mas também para sua aplicação prática em diferentes
áreas do conhecimento. Nos capítulos seguintes, veremos como essas ideias se conectam com outros
tópicos fundamentais, como indução matemática, teoria dos grafos e análise de algoritmos.
132
10 Teoria dos grafos: fundamentos básicos e conectividade
A teoria dos grafos é uma das áreas mais importantes da Matemática Discreta e tem aplicações
diretas em diversos campos do conhecimento, como ciência da computação, engenharia, logística,
biologia e redes sociais. De maneira intuitiva, um grafo é uma estrutura matemática usada para
modelar relações entre objetos. Esses objetos são representados por pontos, chamados vértices, e as
relações entre eles são representadas por linhas que conectam pares de vértices, chamadas arestas.
Um grafo pode ser formalmente definido como um par 𝐺 = (𝑉, 𝐸), onde 𝑉 é o conjunto de
vértices e 𝐸 é o conjunto de arestas. Dependendo do contexto, as arestas podem ser orientadas,
dando origem aos grafos direcionados, ou não orientadas, no caso dos grafos simples. Em muitas
situações práticas, as arestas também podem receber valores numéricos, chamados pesos, que podem
representar distâncias, custos, capacidades ou outros atributos relevantes.
O estudo dos grafos envolve a análise de suas propriedades estruturais e topológicas. Conceitos
como grau de um vértice, caminhos, ciclos, conectividade e componentes são fundamentais para
compreender a dinâmica interna de um grafo. Por exemplo, problemas como determinar se todos
os vértices de um grafo estão conectados ou encontrar o caminho mais curto entre dois vértices são
questões centrais tanto na teoria quanto nas aplicações práticas.
Assim, os fundamentos da teoria dos grafos oferecem não apenas um arcabouço conceitual para a
resolução de problemas abstratos, mas também uma linguagem matemática unificada para descrever
fenômenos do mundo real. Ao longo deste capítulo, estudaremos as definições formais, exemplos
clássicos e algumas aplicações básicas, preparando o terreno para tópicos mais avançados, como
árvores, planaridade e algoritmos em grafos.
133
Definição 61. O grau de um vértice 𝑣, denotado por 𝑑(𝑣), é o número de vezes que 𝑣 é extremidade
de uma aresta. Em um grafo simples, esse valor coincide com o número de vizinhos de 𝑣.
Exemplo:
𝑑(𝑎) = 1, 𝑑(𝑏) = 2, 𝑑(𝑐) = 4, . . .
Definição 62. A lista de graus de um grafo 𝐺 = (𝑉, 𝐸), denotada por 𝐿𝐺 , é a lista que armazena os
graus dos vértices em ordem crescente.
Exemplo:
𝐿𝐺 = (1, 2, 2, 2, 3, 4).
Teorema 33 (Handshaking Lema). A soma dos graus dos vértices de um grafo 𝐺 = (𝑉, 𝐸) é igual a
duas vezes o número de arestas. Isto é,
𝑛
∑︁
𝑑(𝑣𝑖 ) = 2𝑚,
𝑖=1
Base da indução: Para 𝑛 = 1, temos apenas um único vértice. Nesse caso, para todo 𝑚 ≥ 0 (número
de arestas), a soma dos graus será sempre um número par, pois ambas as extremidades das arestas
incidem sobre o mesmo vértice de 𝐺.
Passo de indução: Assuma que 𝑃 (𝑘) é verdadeiro, ou seja,
𝑘
∑︁
𝑃 (𝑘) : 𝑑(𝑣𝑖 ) = 2𝑚.
𝑖=1
134
Ao adicionarmos exatamente um vértice a mais, temos 𝑘 + 1 vértices. Logo:
𝑘+1
∑︁
𝑃 (𝑘 + 1) : 𝑑(𝑣𝑖 ) = 2𝑚′ ,
𝑖=1
b) o grau do novo vértice é maior que zero (novas arestas são adicionadas, cada uma contribuindo
com 2 no somatório dos graus).
Caso a): Nessa situação, o número de arestas permanece inalterado, ou seja, 𝑚 = 𝑚′ . Pela hipótese
de indução e sabendo que o grau do novo vértice é zero, podemos escrever:
𝑘+1
∑︁ 𝑘
∑︁
𝑑(𝑣𝑖 ) = 𝑑(𝑣𝑖 ) + 𝑑(𝑣𝑘+1 ) = 2𝑚 + 0 = 2𝑚′ ,
𝑖=1 𝑖=1
ou seja, 𝑃 (𝑘 + 1) é válida.
Caso b): Nessa situação, temos que o número de arestas 𝑚′ > 𝑚. Seja 𝑚′ = 𝑚 + 𝑎, onde 𝑎 denota o
número de arestas adicionadas ao inserir o novo vértice 𝑣𝑘+1 .
Então, pela hipótese de indução e sabendo que o grau do novo vértice será 𝑎, podemos escrever:
𝑘+1
∑︁ 𝑘
∑︁
𝑑(𝑣𝑖 ) = 𝑑(𝑣𝑖 ) + 𝑑(𝑣𝑘+1 ) + 1 + 1 + 1 + · · · + 1,
𝑖=1 𝑖=1
(sendo 𝑎 vezes o número 1), pois para cada extremidade das arestas no novo vértice, haverá outra
extremidade em algum outro vértice.
Isso implica em:
𝑘+1
∑︁
𝑑(𝑣𝑖 ) = 2𝑚 + 𝑎 + 𝑎 = 2𝑚 + 2𝑎 = 2(𝑚 + 𝑎) = 2𝑚′ ,
𝑖=1
ou seja, 𝑃 (𝑘 + 1) é válida.
Note que mesmo que alguma das arestas inseridas possuam ambas as extremidades no novo vértice
𝑣𝑘+1 , a soma dos graus também será igual a 2𝑚 + 2𝑎, o que continuará validando 𝑃 (𝑘 + 1). Portanto,
a prova está concluída.
Teorema 34. Em um grafo 𝐺 = (𝑉, 𝐸) o número de vértices com grau ímpar é sempre par.
Demonstração. Podemos particionar 𝑉 em dois conjuntos: 𝑃 (grau par) e 𝐼 (grau ímpar). Assim,
𝑛
∑︁ ∑︁ ∑︁
𝑑(𝑣𝑖 ) = 𝑑(𝑣) + 𝑑(𝑢) = 2𝑚
𝑖=1 𝑣∈𝑃 𝑢∈𝐼
135
o que implica em
∑︁ ∑︁
𝑑(𝑢) = 2𝑚 − 𝑑(𝑣).
𝑢∈𝐼 𝑣∈𝑃
Como 2𝑚 é par e a soma de números pares é sempre par, resulta que a soma dos números ímpares
também é par. Para que isso ocorra, temos que ter |𝐼| par (isto é, o número de elementos do conjunto
𝐼 é par).
Exercício: Seja 𝐺 = (𝑉, 𝐸) um grafo básico simples com |𝑉 | = 𝑛 e |𝐸| = 𝑚. Mostre que para que 𝐺
possua 𝑡 vértices de grau 𝑘 e o restante dos vértices de grau 𝑘+1, então devemos ter 𝑡 = (𝑘+1)𝑛−2𝑚.
𝑛2
Exercício: Seja 𝐺 = (𝑉, 𝐸) um grafo bipartido com 𝑛 vértices. Mostre que 𝐺 tem no máximo
4
arestas.
Definição 65. Um grafo completo 𝐺 é um grafo de 𝑛 vértices, denotado por 𝐾𝑛 , se cada vértice é
ligado a todos os demais, ou seja, se
𝐿𝐺 = (𝑛 − 1, 𝑛 − 1, 𝑛 − 1, . . . , 𝑛 − 1).
136
Definição 66. Seja 𝐺 = (𝑉, 𝐸) um grafo simples. O grafo complementar de 𝐺, denotado por 𝐺, é o
grafo definido sobre o mesmo conjunto de vértices 𝑉 , tal que:
Ou seja, em 𝐺 dois vértices são adjacentes se, e somente se, não forem adjacentes em 𝐺.
Seja 𝐺 = (𝑉, 𝐸) um grafo com 𝑛 vértices. O grafo completo 𝐾𝑛 contém todas as possíveis arestas
entre os 𝑛 vértices. O grafo complementar 𝐺 é formado exatamente pelas arestas que não pertencem
a 𝐺. Assim, temos a relação fundamental:
𝐺 ∪ 𝐺 = 𝐾𝑛 e 𝐺 ∩ 𝐺 = ∅.
Em outras palavras:
onde 𝑑𝐾𝑛 (𝑣) denota o grau de 𝑣 no grafo completo. Isso é válido pois em 𝐺 o vértice 𝑣 se conecta
exatamente aos vértices com os quais não possuía aresta em 𝐺.
137
Definição 67 (Subgrafo). Seja 𝐺 = (𝑉, 𝐸) um grafo. Dizemos que 𝐻 = (𝑉 ′ , 𝐸 ′ ) é um subgrafo de
𝐺 se:
𝑉 ′ ⊆ 𝑉 e 𝐸 ′ ⊆ 𝐸,
𝑃 = 𝑣1 𝑒1 𝑣2 𝑒1 𝑣1 𝑒1 𝑣2
𝑇 = 𝑣1 𝑒1 𝑣2 𝑒3 𝑣3 𝑒4 𝑣2
138
c) Caminho: não há repetição de vértices.
𝐶 = 𝑣1 𝑒1 𝑣2 𝑒3 𝑣3 𝑒6 𝑣4 𝑒7 𝑣5
Observação:
• O comprimento (ou tamanho) de um caminho, trilha ou passeio é dado pelo número de arestas
percorridas.
Definição 69. 𝐺 = (𝑉, 𝐸) é conexo se e somente se existe um caminho entre qualquer par de vértices:
Definição 70. Seja 𝐺 = (𝑉, 𝐸) um grafo. Um componente conexo de 𝐺 é subgrafo conexo máximo.
|𝐸| ≥ |𝑉 | − 1.
139
3. Podemos notar que não há como 𝐺 ser conexo, uma vez que sempre haverá um vértice 𝑢 isolado.
então 𝐺 é conexo.
2. Sendo assim, deve existir ao menos um vértice 𝑢 isolado, mesmo que todos os outros 𝑛 − 1
vértices sejam totalmente conectados.
3. Suponha que todos os vértices, com exceção de 𝑢, sejam totalmente conectados. Então, o
subgrafo formado por eles define o 𝐾𝑛−1 .
140
5. Note que, neste caso limite, a inserção de qualquer nova aresta torna 𝐺 conexo.
Portanto, se 𝐺 tem |𝑉 2|−1 + 1 arestas, ele certamente será conexo.
(︀ )︀
Teorema 37. Seja 𝐺 um grafo conexo. Então, 𝐺 é bipartido se, e somente se, todo ciclo de 𝐺 tem
comprimento par.
3. Isso implica que o comprimento de qualquer ciclo será múltiplo de 2, ou seja, par.
(Volta): 𝐺 contém apenas ciclos pares ⇒ 𝐺 é bipartido. Equivalente: 𝐺 não bipartido ⇒ 𝐺 contém
ciclo ímpar.
Portanto, 𝐺 é bipartido se, e somente se, todos os seus ciclos têm comprimento par.
Definição 71. A distância geodésica entre 𝑢 e 𝑣, denotada por 𝑑(𝑢, 𝑣), é o comprimento do menor
caminho entre 𝑢 e 𝑣.
Teorema 38. Seja 𝐺 = (𝑉, 𝐸) um grafo finito e conexo. Denotemos por ecc(𝑣) a excentricidade de
um vértice 𝑣,
ecc(𝑣) = max 𝑑(𝑣, 𝑢),
𝑢∈𝑉
e o diâmetro de 𝐺 é
𝑑(𝐺) = max ecc(𝑣).
𝑣∈𝑉
Então vale
𝑟(𝐺) ≤ 𝑑(𝐺) ≤ 2 𝑟(𝐺).
141
Demonstração. Primeiro, 𝑟(𝐺) ≤ 𝑑(𝐺) é imediato pela definição: o raio é o menor valor entre as
excentricidades e o diâmetro é o maior, logo o menor não pode ser maior que o maior.
Agora provemos 𝑑(𝐺) ≤ 2 𝑟(𝐺). Seja 𝑐 ∈ 𝑉 um centro de 𝐺, isto é, um vértice cuja excentri-
cidade atinge o mínimo: ecc(𝑐) = 𝑟(𝐺). Para quaisquer vértices 𝑢, 𝑣 ∈ 𝑉 temos, pela desigualdade
triangular em grafos (concatenando um caminho geodésico de 𝑢 a 𝑐 com outro de 𝑐 a 𝑣),
Como a desigualdade acima vale para todo par 𝑢, 𝑣, segue que o máximo das distâncias (isto é, o
diâmetro) satisfaz
𝑑(𝐺) = max 𝑑(𝑢, 𝑣) ≤ 2𝑟(𝐺).
𝑢,𝑣∈𝑉
Combinando as duas desigualdades obtemos 𝑟(𝐺) ≤ 𝑑(𝐺) ≤ 2𝑟(𝐺), como queríamos demons-
trar.
142
desses conceitos prepara o leitor para aplicações práticas e para a exploração de propriedades mais
sofisticadas em grafos complexos.
143
11 Teoria dos grafos: o problema do isomorfismo
O problema do isomorfismo em grafos é um dos conceitos fundamentais da Teoria dos Grafos, que
trata da equivalência estrutural entre grafos. Informalmente, dois grafos são considerados isomorfos
se forem estruturalmente idênticos, ou seja, se existe uma correspondência entre seus vértices que
preserva as arestas. Determinar se dois grafos são isomorfos é essencial em diversas áreas da ciência
da computação e da matemática, incluindo química computacional, análise de redes e reconhecimento
de padrões.
Formalmente, dados dois grafos 𝐺1 = (𝑉1 , 𝐸1 ) e 𝐺2 = (𝑉2 , 𝐸2 ), um isomorfismo é uma bijeção
𝑓 : 𝑉1 → 𝑉2 tal que (𝑢, 𝑣) ∈ 𝐸1 se, e somente se, (𝑓 (𝑢), 𝑓 (𝑣)) ∈ 𝐸2 . Se tal função existir, dizemos
que 𝐺1 e 𝐺2 são isomorfos, denotado por 𝐺1 ∼ = 𝐺2 . Caso contrário, os grafos são não isomorfos.
O desafio central do problema é que, embora a definição seja simples, encontrar um isomorfismo, ou
provar sua inexistência, pode ser computacionalmente complexo, especialmente para grafos grandes
ou densamente conectados. A figura a seguir ilustra um par de grafos isomorfos.
Definição 72. Sejam 𝐺1 = (𝑉1 , 𝐸1 ) e 𝐺2 = (𝑉2 , 𝐸2 ). Dizemos que 𝐺1 e 𝐺2 são isomorfos se:
144
satisfazendo a seguinte restrição (*):
Em termos práticos, 𝐺1 e 𝐺2 são isomorfos se é possível obter 𝐺2 a partir de 𝐺1 com uma trans-
formação que não corta ou religa arestas, mas apenas move seus vértices.
i) 𝑒1 = (𝑎, 𝑏) → 𝑔(𝑒1 ) deve ser a aresta que une 𝑓 (𝑎) com 𝑓 (𝑏): (𝐴, 𝐶) = 𝑧2 .
145
ii) 𝑒2 = (𝑏, 𝑐) → 𝑔(𝑒2 ) deve ser a aresta que une 𝑓 (𝑏) com 𝑓 (𝑐): (𝐶, 𝐸) = 𝑧3 .
iii) 𝑒3 = (𝑐, 𝑑) → 𝑔(𝑒3 ) deve ser a aresta que une 𝑓 (𝑐) com 𝑓 (𝑑): (𝐶, 𝐸) = 𝑧4 .
iv) 𝑒4 = (𝑑, 𝑒) → 𝑔(𝑒4 ) deve ser a aresta que une 𝑓 (𝑑) com 𝑓 (𝑒): (𝐵, 𝐷) = 𝑧5 .
v) 𝑒5 = (𝑒, 𝑎) → 𝑔(𝑒5 ) deve ser a aresta que une 𝑓 (𝑒) com 𝑓 (𝑎): (𝐷, 𝐴) = 𝑧1 .
Note que 𝐺1 é isomorfo a 𝐺2 (prove isso, encontrando os mapeamentos 𝑓 e 𝑔). Porém, 𝐻1 não
é isomorfo a 𝐻2 , pois enquanto 𝐻1 admite ciclo de comprimento 3 (contém um triângulo), 𝐻2 não
admite (não contém um triângulo).
146
• Ambos possuem o mesmo número de vértices: 8;
A princípio, parece que 𝐺 é isomorfo a 𝐻. Porém, isso não é verdade. Note que, apesar de não
ferir nenhuma das propriedades invariantes, não podemos afirmar que os grafos são isomorfos. Na
verdade, os grafos em questão não são isomorfos.
Note que, em 𝐺, todos os vértices de grau 4 possuem como vizinhos exatamente um único outro
vértice de grau 4, enquanto em 𝐻, cada vértice de grau 4 possui exatamente 2 vértices de grau 4
como vizinhos. Isso significa uma ruptura em uma aresta, o que altera a topologia (você consegue
identificar qual aresta foi cortada e religada?).
Teorema 39. Dois grafos são isomorfos se e somente se seus complementares também o forem, ou
seja,
𝐺1 ≡ 𝐺2 ⇐⇒ 𝐺1 ≡ 𝐺2 .
147
Note que, no complementar do primeiro grafo, os vértices de grau 2 são adjacentes, o que não
ocorre no complementar do segundo grafo. Portanto, 𝐺 e 𝐻 não são isomorfos.
Propriedades básicas:
i) diag(𝐴) = 0.
v) 𝐴 é esparsa.
148
Teorema 40. Dois grafos são isomorfos, ou seja, 𝐺1 ≡ 𝐺2 se e somente se, a partir da matriz de
adjacências de 𝐺1, é possível obter a matriz de adjacências de 𝐺2 através de uma sequência de
permutações de linhas e colunas.
Exercício: Os seis grafos a seguir consistem de três pares de objetos isomorfos. Identifique quais são
os pares de grafos isomorfos.
Exercício: Os dois grafos a seguir são isomorfos ou não? Prove sua resposta.
149
Exercício: Um grafo simples 𝐺 é chamado de autocomplementar se ele for isomorfo ao seu próprio
complemento 𝐺.
𝑛 = 4𝑡 ou 𝑛 = 4𝑡 + 1
1 𝑛
(︀ )︀
e use que, se 𝐺 é autocomplementar, então |𝐸(𝐺)| = |𝐸(𝐺)| = 2 2
.
150
11.2 Considerações finais
O problema do isomorfismo em grafos ocupa uma posição singular dentro da teoria dos grafos e
da ciência da computação. Apesar de sua formulação aparentemente simples - verificar se dois gra-
fos são estruturalmente idênticos - o tema envolve desafios conceituais e computacionais de grande
relevância. A inexistência de um algoritmo eficiente de complexidade polinomial para o caso geral
o coloca em uma classe especial de problemas cuja dificuldade teórica ainda não foi completamente
resolvida, o que desperta interesse tanto no campo da matemática discreta quanto na teoria da com-
plexidade.
Ao longo deste capítulo, discutimos definições formais, propriedades invariantes e métodos prá-
ticos que auxiliam na identificação ou na refutação de isomorfismo entre grafos. Observou-se que,
embora tais propriedades invariantes sejam ferramentas poderosas para excluir rapidamente a possi-
bilidade de isomorfismo, elas não garantem uma prova construtiva em todos os casos. Além disso,
destacamos o papel das matrizes de adjacências e das transformações por permutação, ressaltando as
dificuldades associadas à explosão combinatória do número de possibilidades.
Outro aspecto importante é a relevância prática do problema, presente em diversas áreas como
química, biologia, redes de computadores e ciência de dados, nas quais a identificação de estruturas
equivalentes é uma tarefa recorrente. Nessas aplicações, algoritmos heurísticos e métodos especializa-
dos para classes restritas de grafos (como árvores e grafos planares) desempenham papel fundamental.
Em síntese, o estudo do isomorfismo em grafos não apenas aprofunda a compreensão teórica
sobre as estruturas discretas, mas também ilustra os limites entre o que pode ser resolvido de maneira
eficiente e o que ainda permanece como um desafio em aberto. Esse tema serve, portanto, como
ponte entre a teoria dos grafos, a matemática aplicada e a ciência da computação, motivando novas
investigações e soluções criativas.
151
12 Teoria dos grafos: árvores
O estudo de grafos é uma das áreas centrais da matemática discreta, fornecendo ferramentas fun-
damentais para modelar e analisar estruturas de relações entre objetos. Dentro deste contexto, as
árvores constituem uma classe especial de grafos que possuem propriedades únicas e aplicações vari-
adas, tanto teóricas quanto práticas. Diferentemente de grafos gerais, as árvores são conectadas e não
contêm ciclos, o que lhes confere uma estrutura hierárquica natural.
Uma árvore pode ser vista como um modelo abstrato de sistemas hierárquicos, como genealogias,
organizações de arquivos em computadores, redes de transmissão e estruturas de decisão. A ausência
de ciclos garante que entre quaisquer dois vértices da árvore exista um único caminho simples, o que
facilita a análise de caminhos, distâncias e conexões dentro da estrutura.
Além disso, as árvores desempenham um papel crucial em algoritmos clássicos de computação,
como busca em profundidade, busca em largura, construção de árvores geradoras mínimas e otimiza-
ção de redes. O estudo das árvores permite compreender não apenas propriedades combinatórias de
grafos, mas também desenvolver métodos eficientes para manipulação e exploração de dados estrutu-
rados.
Neste capítulo, abordaremos definições fundamentais, propriedades básicas, tipos especiais de
árvores, bem como resultados importantes relacionados à sua contagem e caracterização. Serão apre-
sentados exemplos e exercícios que ilustram a utilidade das árvores em diversos contextos da mate-
mática discreta e da ciência da computação.
Teorema 41. 𝐺 é uma árvore ⇐⇒ existe um único caminho 𝑃𝑢𝑣 entre quaisquer dois vértices
𝑢, 𝑣 ∈ 𝑉 .
Demonstração. 1. (Ida) 𝑝 → 𝑞 = ¬𝑞 → ¬𝑝
Se não existe um único caminho entre quaisquer 𝑢, 𝑣, então 𝐺 não é uma árvore.
(a) Pode existir um par 𝑢, 𝑣 tal que não exista caminho entre eles. Isso implica que 𝐺 é
desconexo, o que implica que 𝐺 não é uma árvore.
(b) Pode existir um par 𝑢, 𝑣 tal que existam mais de um caminho. Porém, neste caso temos a
formação de um ciclo e, portanto, 𝐺 não pode ser uma árvore.
152
2. (Volta) 𝑞 → 𝑝 = ¬𝑝 → ¬𝑞
Se 𝐺 não é uma árvore, então não existe um único caminho entre quaisquer 𝑢, 𝑣.
Para que 𝐺 não seja uma árvore, 𝐺 deve ser desconexo ou conter um ciclo. Note que:
• No primeiro caso, existe um par 𝑢, 𝑣 tal que não há caminho entre eles.
• No segundo caso, existem dois caminhos entre 𝑢 e 𝑣, conforme ilustra a figura.
Definição 75. Uma aresta 𝑒 ∈ 𝐸 é ponte se 𝐺 − 𝑒 é desconexo. Ou seja, a remoção de uma aresta
ponte desconecta o grafo.
Demonstração. 1. (Ida) 𝑝 → 𝑞 = ¬𝑞 → ¬𝑝
𝑒 ∈ 𝐶 =⇒ aresta não é ponte.
Como a aresta pertence a um ciclo 𝐶, há dois caminhos entre os vértices 𝑢 e 𝑣.
153
Logo, a remoção da aresta 𝑒 = (𝑢, 𝑣) não impede que o grafo seja conexo, ou seja, 𝐺 − 𝑒 ainda
é conexo. Portanto, 𝑒 não é ponte.
2. (Volta) 𝑞 → 𝑝 = ¬𝑝 → ¬𝑞
Aresta não é ponte =⇒ 𝑒 ∈ 𝐶.
Se a aresta não é ponte, então 𝐺 − 𝑒 ainda é conexo. Se isso ocorre, deve-se ao fato de que
em 𝐺 − 𝑒 ainda existe um caminho entre 𝑢 e 𝑣 que não passa por 𝑒. Logo, em 𝐺 existem dois
caminhos, de modo que a união deles gera um ciclo 𝐶.
Demonstração. 1. (Ida) 𝑝 → 𝑞 = ¬𝑞 → ¬𝑝
Se existe uma aresta que não é ponte, então 𝐺 não é árvore.
A existência de uma aresta não ponte implica na existência de ciclo. A presença de um ciclo 𝐶
faz com que 𝐺 não seja uma árvore.
2. (Volta) 𝑞 → 𝑝 = ¬𝑝 → ¬𝑞
Se 𝐺 não é árvore, então existe uma aresta que não é ponte.
Para que 𝐺 não seja uma árvore, deve existir um ciclo em 𝐺. Logo, todas as arestas pertencentes
ao ciclo não são pontes.
Teorema 44. Seja 𝑇 = (𝑉, 𝐸) uma árvore. Então, 𝑇 + 𝑒, em que 𝑒 é uma aresta que não pertence
ao conjunto 𝐸, contém exatamente um único ciclo.
154
Prova por contradição. Assumamos a negação da conclusão: suponha que existe uma árvore 𝑇 =
(𝑉, 𝐸) com 𝑛 vértices, mas que não possui 𝑛 − 1 arestas. Isso significa que o número de arestas de 𝑇
é diferente de 𝑛 − 1.
Existem duas possibilidades:
Caso 1: |𝐸| < 𝑛 − 1
Se um grafo conexo com 𝑛 vértices tem menos de 𝑛 − 1 arestas, então ele não pode ser conexo.
• Lógica: Para conectar 𝑛 vértices, precisamos de pelo menos 𝑛 − 1 arestas. Com menos do que
isso, é impossível que todos os vértices estejam conectados. Por exemplo, com 𝑛 vértices e
𝑛 − 2 arestas, o grafo terá pelo menos duas componentes conexas.
• Lógica: Um grafo conexo com 𝑛 vértices e exatamente 𝑛−1 arestas é uma árvore e não contém
ciclos. Adicionar uma aresta a uma árvore cria necessariamente um ciclo, pois cria um caminho
adicional entre dois vértices que já estão conectados.
Teorema 46. A soma dos graus de uma árvore com 𝑛 vértices não depende da lista de graus, sendo
dada por
∑︁𝑛
𝑑(𝑣𝑖 ) = 2|𝐸| = 2(𝑛 − 1) = 2𝑛 − 2.
𝑖=1
Teorema 47. Toda árvore com mais de um vértice possui ao menos duas folhas (vértices de grau 1).
Prova por contradição. Suponha que exista ao menos um vértice 𝑣 tal que 𝑑(𝑣) = 1.
Caso a): ∄𝑣 ∈ 𝑉 | 𝑑(𝑣) = 1
155
3. Mas, nesse caso, todos os vértices têm 𝑑(𝑣) ≥ 2, ou seja, a soma dos graus deve ser
∑︁
𝑑(𝑣) ≥ 2𝑛 > 2(𝑛 − 1),
𝑣∈𝑉
2. Mas, como há (𝑛 − 1) vértices com 𝑑(𝑣) ≥ 2, a soma dos graus deve ser
∑︁
𝑑(𝑣) ≥ 2(𝑛 − 1) + 1 > 2(𝑛 − 1),
𝑣∈𝑉
6. Como 𝑇 não possui ciclos, toda aresta de 𝑇 tem uma extremidade em 𝑉𝐼 e outra em 𝑉𝑃 .
7. Portanto, 𝑇 é bipartido.
Dentre as árvores que podem ser extraídas a partir de um grafo, há um tipo que é, sem dúvidas,
o mais importante: as árvores geradoras. Em resumo, uma árvore geradora representa uma forma
resumida de representar um grafo 𝐺, pois há um e apenas um caminho entre qualquer par de vértices.
156
Definição 76 (Árvore geradora (spanning tree)). Seja 𝐺 = (𝑉, 𝐸) um grafo. Dizemos que 𝑇 =
(𝑉, 𝐸𝑇 ) é uma árvore geradora de 𝐺 se 𝑇 é um subgrafo de 𝐺 que é uma árvore, ou seja, conecta
todos os vértices de 𝐺.
Teorema 49. Seja 𝐺 = (𝑉, 𝐸) um grafo conexo. Uma aresta 𝑒 ∈ 𝐸 é uma ponte se e somente se ela
pertence a toda árvore geradora de 𝐺.
Prova:
A. (ida): 𝑝 → 𝑞 = ¬𝑞 → ¬𝑝
Suponha que exista uma árvore geradora que não contém a aresta 𝑒 → 𝑒 não seja ponte.
5. Logo, 𝐺 − 𝑒 é conexo.
6. Portanto, 𝑒 não pode ser ponte (sua remoção não desconecta o grafo).
Como pode ser visto, um grafo 𝐺 admite inúmeras árvores geradoras. A pergunta que surge é:
Quantas árvores geradoras existem em um grafo 𝐺 = (𝑉, 𝐸) de 𝑛 vértices? Para entender a resposta
dessa pergunta, iremos discutir o código de Prüfer.
157
12.1 O código de Prüfer
O Código de Prüfer é uma sequência única de 𝑛 − 2 inteiros que representa uma árvore rotulada
com n vértices. Desenvolvido por Heinz Prüfer em 1918, ele oferece uma forma elegante e biunívoca
de codificar e decodificar árvores, estabelecendo uma conexão direta entre o número de árvores rotu-
ladas em n vértices e as permutações, o que levou à prova do Teorema de Cayley. Essa codificação é
particularmente útil em combinatória e teoria dos grafos, permitindo a enumeração e a geração siste-
mática de árvores, além de ser um excelente exemplo da beleza da correspondência entre diferentes
estruturas matemáticas. Dada uma rotulação dos vértices, é um código que identifica unicamente cada
possível árvore com 𝑛 > 2 vértices. De maneira bem grosseira, é como se fosse o CPF de uma árvore,
cada possível árvore distinta tem o seu próprio código. Foi descoberto que existe uma bijeção entre o
conjunto das árvores de n vértices e o conjunto de sequencias de inteiros de tamanho 𝑛 − 2.
Cada sequencia é composta por 𝑛 − 2 inteiros que podem assumir valores de 1 até 𝑛.
158
Teorema de Cayley: O grafo completo 𝐾𝑛 possui 𝑛 𝑛−2 árvores geradoras.
Ou seja, o número de árvores com 𝑛 vértices é
𝑛 𝑛−2 .
2. Identificar a folha de menor rótulo. O vértice 𝑣 incidente a essa folha é único (ou seja, 𝑣 é o pai
da folha de menor rótulo).
4. Repetir os passos 2 e 3 até que reste apenas um único vértice ou uma única aresta.
159
2. Definir o conjunto 𝑆 = {1, 2, 3, . . . , 𝑛}.
3. Buscar em 𝑆 o menor inteiro que não está no código 𝐶. Chamaremos esse número de 𝑠min .
7. Por fim, adicione à árvore 𝑇 a aresta correspondente aos dois vértices restantes em 𝑆.
160
Os resultados teóricos apresentados, incluindo o Teorema de Cayley e os algoritmos de codifica-
ção e decodificação de Prüfer, demonstram a riqueza combinatória das árvores e a possibilidade de
enumerar e manipular suas estruturas de forma sistemática. Além disso, as árvores revelam-se ferra-
mentas poderosas na resolução de problemas práticos em ciência da computação, engenharia e redes
de comunicação.
A compreensão das árvores permite não apenas a aplicação direta em algoritmos e estruturas de
dados, mas também serve como base para o estudo de grafos mais complexos. As propriedades das ár-
vores fornecem insights fundamentais sobre conectividade, ciclos e hierarquias, elementos essenciais
em diversas áreas da matemática discreta e suas aplicações.
Em síntese, o estudo das árvores oferece tanto uma sólida base teórica quanto ferramentas práticas,
preparando o leitor para a análise de grafos gerais e para o desenvolvimento de algoritmos eficientes
em estruturas conectadas.
161
13 Teoria dos grafos: grafos Eulerianos e Hamiltonianos
Os grafos constituem um instrumento poderoso para modelar problemas em que a estrutura de
conexões desempenha papel central. Entre as várias classes de problemas relacionados a grafos,
destacam-se aqueles que envolvem a existência de caminhos ou ciclos que percorrem arestas ou vér-
tices de maneira particular. Dois desses conceitos fundamentais são os grafos Eulerianos e Hamilto-
nianos, que receberam esses nomes em homenagem a dois grandes matemáticos: Leonhard Euler e
William Rowan Hamilton.
Um grafo Euleriano está associado à possibilidade de percorrer todas as arestas exatamente uma
vez, retornando ao ponto de partida. Esse conceito tem origem histórica no célebre problema das
pontes de Königsberg, resolvido por Euler no século XVIII, considerado o marco inicial da teoria dos
grafos. Já um grafo Hamiltoniano relaciona-se à existência de um ciclo que percorre todos os vértices
exatamente uma vez, um problema que surge em diferentes contextos de roteamento, logística e
otimização.
Embora ambos tratem de percursos em grafos, os problemas Euleriano e Hamiltoniano apresentam
diferenças marcantes: enquanto a caracterização dos grafos Eulerianos é relativamente simples e
elegante, a determinação de grafos Hamiltonianos é substancialmente mais complexa, envolvendo
desafios computacionais e conexões com a teoria da complexidade.
Neste capítulo, exploraremos as definições formais, teoremas caracterizadores e exemplos clás-
sicos de grafos Eulerianos e Hamiltonianos. Além disso, discutiremos algumas aplicações práticas,
que vão desde problemas de transporte e redes até questões em algoritmos e ciência da computação,
evidenciando a importância desses conceitos na matemática discreta e em áreas afins.
Definição 77 (Trilha de Euler). Uma trilha de Euler é uma trilha que engloba toda aresta de 𝐺, ou
seja, passa exatamente uma única vez em cada aresta. A trilha pode ter origem e destino diferentes.
162
Definição 78 (Tour de Euler / Circuito Euleriano). Um tour de Euler, ou circuito Euleriano, é toda
trilha de Euler fechada.
Teorema 50 (Euler, 1976). Seja 𝐺 = (𝑉, 𝐸) um grafo conexo. Então, 𝐺 é Euleriano se, e somente
se, satisfaz a seguinte propriedade:
Prova.
(Ida) 𝐺 é Euleriano ⇒ 𝐺 satisfaz a propriedade 𝐸.
𝑑(𝑣) = 2𝑘𝑣 ,
que também é par, pois na primeira visita apenas saímos de 𝑠 e na última visita apenas entramos
em 𝑠.
163
(Volta) 𝐺 satisfaz a propriedade 𝐸 ⇒ 𝐺 contém um circuito Euleriano.
A prova dessa afirmação é feita apresentando um algoritmo que, dado um grafo 𝐺 que satisfaz 𝐸,
sempre produz um tour de Euler.
2. Fato: Enquanto não retornamos a 𝑣, não podemos ficar presos (pois todos os graus são pares).
Para todo 𝑢 ∈ 𝑉 − {𝑣}:
4. Caso contrário, um dos vértices visitados ainda possui grau positivo (> 0). Como 𝐺 é conexo
e, ao deletar as arestas de 𝐶, subtraímos 2 dos graus dos vértices em 𝐶, ainda há arestas a serem
percorridas. Além disso, todos os vértices restantes ainda têm grau par.
5. Escolha um vértice 𝑣 ∈ 𝐶 e percorra outro circuito 𝐶 ′ , até retornar ao ponto de partida. Isso é
possível pelo passo 2.
164
6. Assim, temos dois circuitos disjuntos em arestas com ao menos um vértice em comum, que
podem ser combinados em um novo circuito 𝐶. Por exemplo:
𝐶 = 𝑎 → 𝑓 → 𝑑 → 𝑎, 𝐶 ′ = 𝑓 → 𝑒 → 𝑑 → 𝑐 → 𝑓,
então:
𝐶 = 𝑎 → 𝑓 → 𝑒 → 𝑑 → 𝑐 → 𝑓 → 𝑑 → 𝑎.
Exemplo:
𝐶 = 𝑎 → 𝑓 → 𝑒 → 𝑑 → 𝑐 → 𝑓 → 𝑑 → 𝑎, 𝐶 ′′ = 𝑐 → 𝑏 → 𝑎 → 𝑐,
165
combinando:
𝐶 = 𝑎 → 𝑓 → 𝑒 → 𝑑 → 𝑐 → 𝑏 → 𝑎 → 𝑐 → 𝑓 → 𝑑 → 𝑎.
Ao fim do processo, obtemos um circuito que contém todas as arestas 𝑒 ∈ 𝐸. Esse resultado é
importante, pois nos fornece uma maneira eficiente de decidir se um grafo 𝐺 é Euleriano. Essa decisão
é trivial e pode ser feita em tempo polinomial, bastando verificar se todos os graus dos vértices são
pares.
Definição 80. Um ciclo Hamiltoniano é um ciclo que engloba todo vértice de 𝐺 (ciclo não permite
repetição).
Definição 81. Um grafo 𝐺 é Hamiltoniano se, e somente se, 𝐺 possui um ciclo Hamiltoniano.
𝐺 → 𝐺′ → 𝐺′′ → 𝐺′′′ → · · · → 𝐾𝑛
onde a cada passo uma aresta 𝑒 é inserida em 𝐺. Como 𝐾𝑛 é Hamiltoniano, segue que em algum
momento entre 𝐺 e 𝐾𝑛 , o grafo torna-se Hamiltoniano. Essa noção motiva a definição a seguir.
Definição 82. Um grafo 𝐺 é não Hamiltoniano maximal se 𝐺 não é Hamiltoniano, mas a adição de
qualquer nova aresta o torna Hamiltoniano (isto é, está na iminência de se tornar Hamiltoniano).
166
Considere o grafo 𝐺 a seguir. Note que 𝐺 não admite um ciclo Hamiltoniano, mas ao adicionar
qualquer aresta nova, 𝐺 torna-se Hamiltoniano.
𝑣6 − 𝑣4 − 𝑣5 − 𝑣2 − 𝑣1 − 𝑣3 − 𝑣6
𝑣6 − 𝑣5 − 𝑣4 − 𝑣1 − 𝑣2 − 𝑣3 − 𝑣6
Teorema 51 (Dirac, 1952). Seja 𝐺 = (𝑉, 𝐸) um grafo básico simples com |𝑉 | = 𝑛 > 2. Então,
𝑛
∀𝑣 ∈ 𝑉, 𝑑(𝑣) ≥ =⇒ 𝐺 é Hamiltoniano.
2
Em outras palavras, esse resultado nos diz que se cada vértice de 𝐺 se liga a pelo menos metade
dos demais vértices, então 𝐺 é Hamiltoniano. Esse resultado ainda é considerado estado da arte na
identificação de grafos Hamiltonianos, no sentido de que não há um critério mais poderoso conhecido
até o momento.
Prova: (por contradição)
A ideia é verificar que não pode existir um grafo 𝐺 que satisfaça a propriedade 𝐻 e não seja
Hamiltoniano.
Suponha que ∃ 𝐺 = (𝑉, 𝐸) básico simples que satisfaz a propriedade, mas não é Hamiltoniano.
Considere 𝐺 como sendo não Hamiltoniano maximal. Então, ∃ 𝑢, 𝑤 ∈ 𝑉 não adjacentes.
167
Defina 𝐻 = 𝐺 + (𝑢, 𝑤). Como 𝐻 é Hamiltoniano, ∃ um ciclo 𝐶 que passa por ∀𝑣 ∈ 𝑉 .
Chamaremos 𝑢 = 𝑣1 e 𝑤 = 𝑣𝑛 .
Observação: Quem está em 𝑆 não importa, mas quantos elementos estão em 𝑆 é fundamental.
Assim, temos:
|𝑆| = 𝑑(𝑢), |𝑇 | = 𝑑(𝑤),
i) 𝑣𝑛 ∈
/ 𝑆: de fato, para que 𝑣𝑛 ∈ 𝑆, seria necessário ∃ aresta que liga 𝑢 a 𝑣𝑛+1 = 𝑢. Mas isso não
ocorre, pois não há loops.
ii) 𝑣𝑛 ∈
/ 𝑇 : de fato, para que 𝑣𝑛 ∈ 𝑇 , seria necessário ∃ aresta que liga 𝑤 a 𝑣𝑛 = 𝑤. Mas isso não
ocorre, pois não há loops.
Dessa forma, 𝑣𝑛 ∈
/ 𝑆 ∪ 𝑇 , o que implica que |𝑆 ∪ 𝑇 | < 𝑛.
O próximo passo consiste em responder à pergunta: ∃𝑣𝑘 ∈ 𝑆 ∩ 𝑇 ?
Suponha que sim. Se chegarmos a uma contradição, é porque tal vértice não pode existir. Vamos
considerar que 𝑣𝑘 ∈ 𝑆 ∩ 𝑇 . Então:
168
i) Se 𝑣𝑘 ∈ 𝑆: ∃ aresta que liga 𝑢 a 𝑣𝑘+1 .
Porém, nesse caso 𝐺 seria Hamiltoniano, pois existiria um ciclo 𝐶 ′ que envolve todo vértice de
𝐺. Isso fere a definição inicial de que 𝐺 é não Hamiltoniano maximal, gerando uma contradição e,
portanto, invalidando a suposição de que ∃𝑣𝑘 ∈ 𝑆 ∩ 𝑇 .
O fato é que ∄𝑣𝑘 ∈ 𝑆 ∩ 𝑇 , ou seja:
𝑆 ∩ 𝑇 = ∅.
Isso é uma contradição para a primeira suposição, pois todo grafo que satisfaz 𝐻 tem:
𝑛 𝑛
𝑑(𝑢) ≥ e 𝑑(𝑤) ≥ ,
2 2
Em outras palavras, a hipótese de que existe um grafo 𝐺 que satisfaz 𝐻 e não seja Hamiltoniano
é falsa.
169
Conclusão: Não existe grafo 𝐺 que satisfaça a propriedade 𝐻 e não seja Hamiltoniano. Se 𝐻 é
verdadeira, então é certeza que 𝐺 é Hamiltoniano.
Mas isso garante que é simples decidir se um dado grafo 𝐺 é Hamiltoniano? Não, pois podemos
ter grafos 𝐺 para os quais 𝐻 falha e, mesmo assim, eles são Hamiltonianos.
Exemplo: grafo 2-regular conexo.
Problema em aberto: ninguém nunca demonstrou a volta. Nem mesmo foi proposto um critério
mais efetivo (do tipo “se e somente se”).
O teorema anterior, apesar de poderoso, não nos fornece uma caracterização completa de grafos
Hamiltonianos. Basicamente, ele diz que todo grafo que satisfaz a propriedade 𝐻 é Hamiltoniano,
mas nem todo grafo Hamiltoniano satisfaz a propriedade 𝐻.
Teorema 52 (Ore). Seja 𝐺 = (𝑉, 𝐸) um grafo básico simples de 𝑛 vértices e sejam 𝑢 e 𝑣 vértices não
adjacentes tais que:
𝑑(𝑢) + 𝑑(𝑣) ≥ 𝑛.
Prova.
170
A. (ida) 𝑝 → 𝑞
Se 𝐺 é Hamiltoniano, é trivial que a adição de qualquer aresta faz com que ele permaneça
Hamiltoniano.
𝑑(𝑢) + 𝑑(𝑣) ≥ 𝑛,
Teorema 53 (Bondy e Chvátal, 1976). Um grafo básico simples 𝐺 é Hamiltoniano se, e somente se,
seu fechamento 𝑐(𝐺) é Hamiltoniano.
Demonstração.
(ida) 𝑝 → 𝑞: É fácil perceber que se 𝐺 é Hamiltoniano, a adição de qualquer aresta em 𝐺 o
mantém Hamiltoniano.
(volta) 𝑞 → 𝑝:
171
3. Como 𝑐(𝐺) = 𝐺𝐾 é obtido de 𝐺𝐾−1 por
Corolário 1. Seja 𝐺 = (𝑉, 𝐸) um grafo básico simples com |𝑉 | > 2. Se 𝑐(𝐺) = 𝐾𝑛 , ou seja, o
fechamento é Hamiltoniano, então 𝐺 é Hamiltoniano.
Teorema 54 (Pósa, 1962). Seja 𝐺 = (𝑉, 𝐸) um grafo básico simples com |𝑉 | > 2 e 𝑑1 , 𝑑2 , 𝑑3 , . . . , 𝑑𝑛
a sequência dos graus dos vértices em ordem crescente. Se, para todo 𝑖 tal que 1 ≤ 𝑖 ≤ 𝑛2 , tivermos
𝑑𝑖 ≥ 𝑖 + 1,
então 𝐺 é Hamiltoniano.
𝐿𝐺 = (2, 3, 4, 4, 5, 5, 5, 6).
𝑛
= 4, 𝑖 = 1, 2, 3, 4
2
𝑑1 = 2 ≥ 1 + 1 ok,
𝑑2 = 3 ≥ 2 + 1 ok,
𝑑3 = 4 ≥ 3 + 1 ok,
𝑑4 = 4 ≥ 4 + 1 falhou.
Portanto, não podemos afirmar que 𝐺 é Hamiltoniano. Ele pode ser ou não Hamiltoniano: trata-
se de um caso de indeterminação.
Observação: Uma mesma sequência de graus pode representar dois grafos distintos: um grafo 𝐺
Hamiltoniano e um grafo 𝐺′ não Hamiltoniano.
172
13.3 Considerações finais
O estudo de grafos Eulerianos e Hamiltonianos constitui uma parte fundamental da Teoria dos
Grafos, conectando conceitos estruturais de grafos com problemas clássicos e modernos de otimiza-
ção e combinatória. Grafos Eulerianos nos fornecem critérios claros e eficientes para a existência de
trilhas e circuitos que percorrem todas as arestas de um grafo, sendo possível determinar sua exis-
tência em tempo polinomial por meio da análise dos graus dos vértices. A abordagem construtiva de
Euler e os algoritmos associados permitem não apenas a identificação desses grafos, mas também a
construção prática de trilhas e circuitos.
Por outro lado, grafos Hamiltonianos apresentam uma complexidade significativamente maior. A
determinação da existência de ciclos que percorrem todos os vértices de um grafo é, em geral, um pro-
blema NP-Completo, e a caracterização completa desses grafos ainda permanece aberta. Resultados
importantes, como os teoremas de Dirac, Ore, Bondy–Chvátal e Pósa, fornecem condições suficien-
tes para a existência de ciclos Hamiltonianos, embora não constituam condições necessárias. Estes
teoremas permitem a identificação de classes de grafos Hamiltonianos e oferecem ferramentas para
análise estrutural, mas ainda deixam espaço para indeterminações e casos excepcionais.
A distinção entre grafos Eulerianos e Hamiltonianos evidencia como pequenas variações nas de-
finições de caminhos e ciclos em grafos podem alterar completamente a complexidade do problema
associado. Enquanto a existência de trilhas e circuitos Eulerianos depende apenas de condições locais
simples (graus dos vértices), a existência de ciclos Hamiltonianos depende de propriedades globais
do grafo, exigindo técnicas mais sofisticadas e a consideração de toda a estrutura do grafo.
Por fim, o estudo desses grafos é de grande relevância não apenas do ponto de vista teórico, mas
também prático, com aplicações em roteirização de veículos, design de circuitos, bioinformática,
problemas de logística e planejamento. O conhecimento das condições e métodos para a identificação
de grafos Eulerianos e Hamiltonianos permite ao estudante desenvolver habilidades de raciocínio
combinatório e algoritmos eficientes, consolidando a compreensão da teoria dos grafos como uma
ferramenta central da Matemática Discreta.
173
14 Teoria dos grafos: grafos planares
Os grafos planares representam uma classe especial de grafos que podem ser desenhados no plano
de tal forma que suas arestas não se cruzem, exceto nos vértices comuns. Esse conceito é fundamental
na Teoria dos Grafos, pois relaciona propriedades combinatórias dos grafos com suas representações
geométricas. O estudo de grafos planares surgiu de problemas práticos, como a disposição de circuitos
elétricos, mapas geográficos e redes de transporte, onde a minimização de cruzamentos é essencial
para simplificação e clareza.
Um ponto central ao estudar grafos planares é a representação planar. Um grafo é considerado
planar se houver pelo menos uma forma de desenhá-lo no plano sem que duas arestas se cruzem.
Nem todos os grafos são planares; por exemplo, o grafo completo com cinco vértices (𝐾5 ) e o grafo
bipartido completo com três vértices em cada partição (𝐾3,3 ) são exemplos clássicos de grafos não
planares. A identificação de tais grafos não planares é essencial para compreender os limites da
planaridade.
Além disso, grafos planares estão intimamente ligados a conceitos topológicos e geométricos. Um
dos resultados mais importantes é a fórmula de Euler, que estabelece uma relação entre o número de
vértices, arestas e faces de um grafo planar conexo. Essa fórmula fornece uma ferramenta poderosa
para analisar a estrutura de grafos planares e é base para muitos teoremas subsequentes, incluindo
limites superiores para o número de arestas e critérios para planaridade.
O estudo de grafos planares combina técnicas de raciocínio combinatório, algoritmos de repre-
sentação e conceitos geométricos, tornando-se uma ponte natural entre a matemática discreta e apli-
cações práticas em ciência da computação, engenharia e design de redes. Ao longo deste capítulo,
serão exploradas definições formais, teoremas fundamentais, exemplos clássicos de grafos planares e
não planares, e métodos para verificar a planaridade de um grafo dado.
Definição 84. Um grafo 𝐺 é plano se ele pode ser desenhado numa superfície plana sem que haja
cruzamento de arestas. Um grafo 𝐺 é planar se ele for isomorfo a um grafo plano.
174
Importância dos grafos planares:
Definição 85 (Curva de Jordan). Uma curva de Jordan é toda curva fechada no plano que não inter-
cepta a si própria.
Observação: A noção de curva de Jordan, para nosso estudo com grafos, será a de ciclo. Todo ciclo
pode ser visto como uma curva de Jordan, uma vez que é uma trajetória fechada e que não repete
vértices.
Teorema 55. Se 𝐶 é uma curva de Jordan, com 𝑥 ∈ int(𝐶) e 𝑦 ∈ ext(𝐶), então qualquer curva que
una 𝑥 a 𝑦 intercepta 𝐶.
Queremos encontrar pistas sobre quais são os menores blocos não planares que existem. Nessa
busca, pode-se verificar o seguinte fato.
175
Teorema 56. O grafo completo 𝐾5 não é planar.
Demonstração. Iremos assumir que ele é planar. Veremos então que chegamos a um absurdo, o que
contradiz a hipótese inicial.
a) 𝑣4 ∈ int(𝐶)
b) 𝑣4 ∈ ext(𝐶)
𝐶1 = 𝑣1 𝑣2 𝑣4 𝑣1 , 𝐶2 = 𝑣2 𝑣3 𝑣4 𝑣2 , 𝐶3 = 𝑣3 𝑣4 𝑣1 𝑣3
Logo, obtemos a subdivisão do plano em quatro regiões. Para o vértice 𝑣5 , temos as seguintes
possibilidades:
176
iii) 𝑣5 ∈ int(𝐶2 ): a aresta (𝑣1 , 𝑣5 ) cruza.
Sendo assim, para 𝑣4 ∈ int(𝐶), não é possível que 𝐾5 seja planar. Vamos agora ao caso (b), onde
𝑣4 ∈ ext(𝐶). Assim, temos:
𝐶 = 𝑣1 𝑣2 𝑣3 𝑣1 , 𝐶1 = 𝑣1 𝑣3 𝑣4 𝑣1 , 𝐶2 = 𝑣2 𝑣3 𝑣4 𝑣2 , 𝐶3 = 𝑣1 𝑣2 𝑣4 𝑣1
Novamente, temos a partição do plano em quatro regiões, de modo que, para o vértice 𝑣5 , ocorre:
Em todos os casos chegamos a uma contradição, concluindo que 𝐾5 não pode ser planar.
Teorema 57 (Fórmula de Euler). Seja 𝐺 = (𝑉, 𝐸) um grafo plano conexo com |𝑉 | = 𝑛, |𝐸| = 𝑚 e
𝑓 faces (ou regiões). Então,
𝑛 − 𝑚 + 𝑓 = 2.
1−0+1=2 ✓
177
Passo de indução (𝑃 (𝑘) → 𝑃 (𝑘 + 1)):
Hipótese de indução 𝑃 (𝑘): Suponha que para todo grafo 𝐺 com 𝑘 arestas, vale
𝑛 − 𝑘 + 𝑓 = 2.
𝑛′ − 𝑚′ + 𝑓 ′ = 2.
𝑛 − 𝑚 + 𝑓 = 𝑛′ − (𝑚′ + 1) + (𝑓 ′ + 1) = 𝑛′ − 𝑚′ + 𝑓 ′ = 2.
178
Prova por contradição. 1. Suponha que o grafo 𝐾3,3 seja representado por um grafo plano.
3. Como 𝐾3,3 é bipartido, o comprimento do menor ciclo é 4 (não possui ciclos ímpares).
4. Assim, todas as faces (ou regiões) devem ter pelo menos 4 arestas.
6. Seja
𝑓
∑︁
𝑁= 𝐵(𝑅𝑖 ).
𝑖=1
𝑁 ≥ 4𝑓.
7. Entretanto, como cada aresta pode ser contada no máximo duas vezes (quando pertence à fron-
teira entre duas regiões), temos:
𝑁 ≤ 2𝑚 = 18.
𝑛 − 𝑚 + 𝑓 = 6 − 9 + 𝑓 = −3 + 𝑓.
o que é uma contradição, pois de acordo com a fórmula de Euler, o valor deveria ser 2.
Portanto, o grafo bipartido completo 𝐾3,3 não é planar.
𝑚 ≤ 3(𝑛 − 2).
Demonstração. Represente 𝐺 como um grafo plano (imersão planar). Pela fórmula de Euler, temos:
𝑛 − 𝑚 + 𝑓 = 2.
179
Se 𝑚 é o número máximo de arestas, toda face de 𝐺 deve ser um triângulo, pois, caso contrário,
seria possível adicionar arestas dividindo uma face maior.
Como cada face é composta por 3 arestas e cada aresta é contada exatamente duas vezes (pois
pertence à fronteira de duas faces), temos:
3𝑓 = 2𝑚.
2𝑚
𝑛−𝑚+ = 2.
3
Multiplicando por 3:
3𝑛 − 3𝑚 + 2𝑚 = 6,
3𝑛 − 𝑚 = 6,
𝑚 = 3𝑛 − 6.
180
Pelo Lema do Aperto de Mãos (Handshaking Lemma), temos:
𝑛
∑︁
𝑑(𝑣𝑖 ) = 2𝑚.
𝑖=1
Logo,
6𝑛 ≤ 2𝑚 ⇒ 𝑚 ≥ 3𝑛.
𝑚 ≤ 3𝑛 − 6 ⇒ 3𝑛 ≤ 3𝑛 − 6
Os resultados anteriores são interessantes, mas não podem ser usados para decidir se 𝐺 é planar. De
fato, para serem aplicados, o grafo precisa estar desenhado como plano, o que implica que já devemos
saber previamente que ele é planar.
Veremos a seguir algumas definições importantes para a apresentação do resultado fundamental
para a detecção de planaridade: o Teorema de Kuratowski.
Vimos que ambos 𝐾5 e 𝐾3,3 não são planares. Portanto, todo grafo que os contenha como subgrafo
também não pode ser planar. No entanto, existem grafos que não contêm 𝐾5 nem 𝐾3,3 como subgrafo
e, mesmo assim, não são planares. Entretanto, tais grafos podem ser reduzidos a 𝐾5 ou 𝐾3,3 pela
operação conhecida como redução de série.
Definição 86 (Redução de série). Se um grafo 𝐺 tem um vértice 𝑣 de grau 2 e arestas (𝑣1 , 𝑣) e (𝑣, 𝑣2 )
com 𝑣1 ̸= 𝑣2 , diz-se que as arestas (𝑣1 , 𝑣) e (𝑣, 𝑣2 ) estão em série.
Definição 87 (Grafos homeomorfos). Dois grafos 𝐺1 e 𝐺2 são ditos homeomorfos se podem ser
reduzidos a grafos isomorfos por meio de sucessivas reduções de série.
181
Por exemplo, os dois grafos a seguir são homeomorfos. Isso pode ser facilmente percebido uma vez
que, ao aplicarmos reduções de série em ambos, obtemos o seguinte resultado: 𝐻1 é isomorfo a 𝐻2 .
Teorema 61 (Teorema de Kuratowski). Um grafo 𝐺 é planar se, e somente se, 𝐺 não contiver um
subgrafo homeomorfo a 𝐾5 ou 𝐾3,3 .
Este resultado fornece um critério objetivo para caracterizar planaridade, embora seja de difícil apli-
cação prática em algoritmos. Em resumo, o Teorema de Kuratowski descreve como determinar se um
grafo 𝐺 é planar ou não por meio de três operações básicas:
i) remoção de arestas;
Exemplo ilustrativo:
182
2. Redução de séries: 𝑣1 − 𝑣4 − 𝑣8 e 𝑣3 − 𝑣6 − 𝑣7 .
183
15 Teoria dos grafos: coloração de vértices
A coloração de grafos é um dos temas mais fascinantes e estudados da teoria dos grafos, tanto
pelo seu apelo visual quanto pela diversidade de aplicações práticas. O problema básico consiste em
atribuir “cores” aos vértices de um grafo de modo que vértices adjacentes recebam cores diferentes.
Apesar da simplicidade de sua formulação, esse problema envolve questões profundas de caráter
combinatório e algorítmico.
Do ponto de vista teórico, a coloração de vértices está intimamente relacionada a propriedades
estruturais dos grafos, como o grau dos vértices, a presença de ciclos e a existência de subgrafos
especiais. A noção central é o número cromático de um grafo, definido como o menor número de
cores necessárias para realizar uma coloração própria. Determinar esse número, em geral, é um
problema difícil e que ocupa posição central na teoria dos grafos.
Além da relevância matemática, problemas de coloração surgem naturalmente em diversas apli-
cações reais. Exemplos incluem a elaboração de horários escolares (onde aulas que compartilham
alunos não podem ocorrer no mesmo horário), a alocação de frequências em redes de comunicação
sem fio (evitando interferências entre transmissores próximos), e o projeto de circuitos eletrônicos.
Assim, o estudo da coloração de vértices combina elegância teórica com utilidade prática.
Neste capítulo, exploraremos definições fundamentais, exemplos clássicos e teoremas importantes
que ajudam a compreender a complexidade do problema de coloração. Também veremos limites
superiores e inferiores para o número cromático, algoritmos de coloração e, finalmente, resultados
marcantes como o Teorema das Quatro Cores, que garante que qualquer grafo planar pode ser colorido
com no máximo quatro cores.
Ideia: Dado um grafo 𝐺 = (𝑉, 𝐸), particionar o conjunto de vértices 𝑉 em conjuntos independentes.
Definição 89. Uma 𝑘-coloração de 𝐺 atribui uma entre 𝑘 cores a cada vértice de 𝐺, de modo que
vértices adjacentes sempre recebam cores (ou rótulos) diferentes.
Assim, podemos descrever a partição induzida por uma 𝑘-coloração da seguinte forma:
Pergunta: Dado um grafo 𝐺 = (𝑉, 𝐸), existe uma 𝑘-coloração para 𝐺 (com 𝑘 > 2)?
184
Trata-se de um problema NP-Completo. Em outras palavras, queremos responder se, para um
dado 𝐺, é possível encontrar 2, 3, 4, . . . subconjuntos independentes.
Definição 90. O número mínimo 𝑘 para o qual existe uma coloração de 𝐺 é chamado de número
cromático de 𝐺, denotado por 𝜒(𝐺). Este é um atributo do grafo.
Propriedades
As seguintes propriedades nos ajudam a limitar os valores de 𝜒(𝐺) em problemas reais, forne-
cendo limites inferiores e superiores:
a) Se |𝑉 | = 𝑛, então 𝜒(𝐺) ≤ 𝑛.
Demonstração. Antes de provar a equivalência, vale uma observação importante sobre casos degene-
rados: o grafo sem arestas (grafo nulo) é bipartido, mas tem 𝜒(𝐺) = 1. Assim, a equivalência acima
deve ser entendida com a convenção usual:
Ainda assim, para clareza, provaremos a implicação nos dois sentidos e indicaremos a observação
quando necessário.
(⇒) Suponha que 𝐺 é bipartido. Então existe uma bipartição 𝑉 (𝐺) = 𝑋 ∪ 𝑌 com 𝑋 ∩ 𝑌 = ∅
e tais que não há arestas internas em 𝑋 nem em 𝑌 (todas as arestas ligam um vértice de 𝑋 a um
vértice de 𝑌 ). Basta então definir uma 2–coloração própria atribuindo a mesma cor, digamos cor 1, a
todos os vértices de 𝑋 e a cor 2 a todos os vértices de 𝑌 . Como não existem arestas entre vértices da
mesma parte, vértices adjacentes têm cores diferentes; logo existe uma coloração própria com 2 cores
e 𝜒(𝐺) ≤ 2.
Se 𝐺 possui pelo menos uma aresta, então 𝜒(𝐺) ≥ 2 (pois uma aresta exige duas cores distintas).
Portanto, nesse caso 𝜒(𝐺) = 2. (No caso degenerado em que 𝐺 não tem arestas, a mesma construção
dá 𝜒(𝐺) = 1, conforme observado.)
(⇐) Suponha que 𝜒(𝐺) = 2. Então existe uma coloração própria de 𝐺 com exatamente duas
cores; seja 𝑉 (𝐺) = 𝐶1 ∪ 𝐶2 a partição dos vértices segundo as cores (com 𝐶1 ∩ 𝐶2 = ∅). Como
a coloração é própria, não há arestas entre vértices dentro de 𝐶1 nem dentro de 𝐶2 . Assim, todas as
arestas ligam um vértice de 𝐶1 a um vértice de 𝐶2 , e portanto 𝐺 é bipartido com bipartição 𝐶1 , 𝐶2 .
185
Esses dois argumentos mostram que, salvo o caso trivial do grafo sem arestas (que é bipartido mas
tem 𝜒(𝐺) = 1), ter uma bipartição é equivalente a admitir uma coloração própria com duas cores.
Concluímos que, para grafos com pelo menos uma aresta,
𝐺 é bipartido ⇐⇒ 𝜒(𝐺) = 2.
Observação: Uma consequência prática: um grafo é bipartido ⇐⇒ ele não contém ciclos de com-
primento ímpar. Essa caracterização é frequentemente usada para testar biparticidade (por exemplo,
via busca em largura).
Teorema 63. Seja 𝐺 = (𝑉, 𝐸) um grafo e seja ∆(𝐺) = max{𝑑(𝑣) : 𝑣 ∈ 𝑉 } o grau máximo de 𝐺.
Então, 𝜒(𝐺) ≤ ∆(𝐺) + 1.
2. Um vértice deve sempre receber uma cor livre, ou seja, diferente da cor de todos os seus vizi-
nhos.
4. Pelo princípio da casa dos pombos, sempre irá existir uma cor livre no conjunto definido como
{1, 2, . . . , ∆(𝐺) + 1}.
Teorema 64. Seja 𝐺 = (𝑉, 𝐸) um grafo conexo com ∆(𝐺) ≥ 3. Se 𝐺 não é completo, então
𝜒(𝐺) ≤ ∆(𝐺).
Definição 91 (Grafo dual). Seja 𝐺 = (𝑉, 𝐸) um grafo básico simples planar. Um grafo dual 𝐺′ de
𝐺 é definido da seguinte forma: cada região (ou face) de 𝐺 corresponde a um vértice de 𝐺′ , e para
cada aresta de 𝐺 que delimita duas regiões adjacentes, há uma aresta em 𝐺′ ligando os vértices
correspondentes.
Em outras palavras, o centro de cada face do mapa se torna um vértice de 𝐺′ , e se duas faces com-
partilham uma fronteira, então existe uma aresta entre os vértices correspondentes no dual. Assim,
todo mapa pode ser transformado em um grafo planar, já que mapas são, por definição, estruturas
planares.
186
Teorema 65 (Teorema das 4 cores). Todo mapa pode ser colorido com apenas 4 cores, de modo que
duas regiões vizinhas não recebam a mesma cor.
Em termos de grafos: o dual de um grafo planar simples básico satisfaz
𝜒(𝐺) ≤ 4.
O Teorema das 4 Cores afirma que todo mapa pode ser colorido com apenas quatro cores de
forma que regiões vizinhas recebam cores distintas. Em termos de grafos, o resultado pode ser for-
mulado assim: o número cromático de qualquer grafo planar é no máximo 4. A seguir, apresentamos
um esboço intuitivo da prova.
1. Tradução para grafos planares: Cada região do mapa é representada por um vértice de um
grafo planar, e duas regiões vizinhas são ligadas por uma aresta. Assim, o problema de colorir
mapas é equivalente ao problema de colorir vértices de grafos planares.
2. Hipótese de contraexemplo mínimo: Suponha, por contradição, que exista um grafo planar 𝐺
que não pode ser colorido com 4 cores. Escolhe-se um contraexemplo mínimo, isto é, um grafo
𝐺 tal que todos os seus subgrafos possam ser 4-coloridos, mas 𝐺 não.
187
3. Propriedades estruturais: Pela fórmula de Euler e restrições de planaridade, todo grafo planar
possui ao menos um vértice de grau no máximo 5. Logo, o contraexemplo mínimo teria essa
propriedade.
5. Uso das cadeias de Kempe: Para os casos de vértices de grau 5, utiliza-se a técnica das cadeias
de Kempe. Trata-se de trocar cores em certos subgrafos conexos de modo a liberar uma cor
distinta para o vértice removido.
6. Conclusão: Esse processo mostra que sempre é possível colorir o grafo com 4 cores, o que
contradiz a suposição da existência de um contraexemplo mínimo. Assim, todo grafo planar é
4-colorível.
A conjectura foi feita em 1852 por Francis Guthrie. Em 1890, Heawood provou o Teorema das 5
Cores. A prova completa do Teorema das 4 Cores só foi estabelecida em 1976 por Appel e Haken,
com auxílio de computador para verificar milhares de configurações críticas.
Do ponto de vista da classificação dos problemas em computação, encontrar o número cromático
𝜒(𝐺) de grafos arbitrários é um problema NP-Hard. Alguns fatos relevantes:
1. Não se conhece algoritmo polinomial que colore um grafo arbitrário com exatamente 𝜒(𝐺)
cores.
2. Existe um algoritmo polinomial para coloração de grafos que colore qualquer grafo 𝐺 com no
máximo 𝑂(𝜒(𝐺) log 𝑛) cores, onde 𝑛 = |𝑉 | é o número de vértices de 𝐺.
2. 𝛽𝑣,𝑤 (𝐺) = 𝐺 ∖ (𝑣, 𝑤): condensação dos vértices 𝑣 e 𝑤, onde 𝐺 ∖ (𝑣, 𝑤) é o grafo resultante da
fusão dos vértices 𝑣 e 𝑤 seguida da eliminação de loops e arestas paralelas que possam surgir.
188
A figura a seguir ilustra um exemplo dessas operações.
Teorema 66. Seja 𝐺 = (𝑉, 𝐸) um grafo não completo e 𝑣, 𝑤 ∈ 𝑉 um par de vértices não adjacentes.
Então, o número cromático de 𝐺 satisfaz:
2. Se os vértices 𝑣, 𝑤 possuem cores distintas em 𝐶, então a aresta (𝑣, 𝑤) pode ser adicionada em
𝐺 sem alterar 𝐶. Neste caso, 𝜒(𝐺) = 𝜒(𝛼𝑣,𝑤 (𝐺)).
189
4. Portanto, 𝜒(𝐺) deve ser o menor valor entre 𝜒(𝛼𝑣,𝑤 (𝐺)) e 𝜒(𝛽𝑣,𝑤 (𝐺)).
Note que 𝜒(𝐺) é igual ao número de vértices do menor grafo completo obtido através das opera-
ções 𝛼𝑣,𝑤 (𝐺) e 𝛽𝑣,𝑤 (𝐺).
O método a seguir define um algoritmo exato para o problema da coloração de vértices.
Algoritmo 1 Chromatic_Number(G)
1: 𝑛 ← |𝑉 |
2: if 𝐺 = 𝐾𝑛 then
3: 𝜒 ← min{𝜒, 𝑛}
4: else
5: Encontre um par de vértices não adjacentes 𝑣, 𝑤 ∈ 𝑉
6: call Chromatic_Number(𝛼𝑣,𝑤 (𝐺))
7: call Chromatic_Number(𝛽𝑣,𝑤 (𝐺))
8: end if
190
Análise da complexidade
Note que o número máximo de grafos a serem examinados é igual ao número total de nós na
árvore binária. Como em cada nível ligamos/fundimos apenas dois vértices, a profundidade da árvore
é proporcional ao número de arestas no grafo complementar de 𝐺, denotado por 𝑚′ .
𝑚 ′
𝑚′
∑︁
0 1 2
2 + 2 + 2 + ··· + 2 = 2𝑖
𝑖=0
Note que 2𝑖+1 = 2 · 2𝑖 = 2𝑖 + 2𝑖 , o que nos leva a 2𝑖 = 2𝑖+1 − 2𝑖 . Dessa forma, temos:
𝑚 ′
′ ′
∑︁
(2𝑖+1 − 2𝑖 ) = 2𝑚 +1 − 20 = 2𝑚 +1 − 1
𝑖=0
′
Ou seja, a complexidade é exponencial, 𝑂(2𝑚 ). Portanto, esse algoritmo torna-se inviável para
grafos com muitos vértices. Para isso, existem algoritmos gulosos aproximados, como o algoritmo de
Welsh & Powell, por exemplo.
Suponha que os vértices estejam ordenados em ordem decrescente dos graus, ou seja, temos
𝑣1 , 𝑣2 , . . . , 𝑣𝑛 com respectivos graus ∆ = 𝑑1 ≥ 𝑑2 ≥ · · · ≥ 𝑑𝑛 .
Teorema 67.
𝜒(𝐺) ≤ max min{𝑑𝑖 + 1, 𝑖}
1≤𝑖≤𝑛
(a) No máximo 𝑖 − 1 cores foram utilizadas em seus vizinhos, pois antes dele foram exatamente
𝑖 − 1 vértices.
Esse resultado fundamenta o algoritmo de Welsh & Powell, utilizado para colorir um grafo e
aproximar o verdadeiro valor do número cromático 𝜒(𝐺).
1. Note que a ordenação dos vértices pode ser realizada em 𝑂(𝑛 log 𝑛).
2. A criação das listas de cores envolve trabalhar com 𝑛 listas de tamanhos variáveis. Para o
𝑖-ésimo vértice, a lista de cores tem tamanho 𝑖, de modo que o número de operações é dado por:
𝑛
∑︁
1 + 2 + 3 + ··· + 𝑛 = 𝑖
𝑖=1
191
Algoritmo 2 Welsh_Powell(G)
1: Ordene os vértices 𝑣𝑖 ∈ 𝑉 em ordem decrescente de grau
2: for cada 𝑣𝑖 ∈ 𝑉 do
3: 𝐶𝑖 = [1, 2, . . . , 𝑖] ◁ Lista de cores do vértice 𝑣𝑖
4: end for
5: for 𝑖 = 1 to 𝑛 do
6: color = 𝐶𝑖 [1] ◁ Escolhe a primeira cor da lista
7: 𝑣𝑖 .𝑐 = color ◁ Colore 𝑣𝑖 com a cor escolhida
8: for cada 𝑣𝑗 ∈ 𝑁 (𝑣𝑖 ) do
9: 𝐶𝑗 = 𝐶𝑗 − color ◁ Remove a cor da lista dos vizinhos
10: end for
11: end for
12: 𝜒 = 0
13: for cada 𝑣𝑖 ∈ 𝑉 do
14: if 𝑣𝑖 .𝑐 > 𝜒 then
15: 𝜒 = 𝑣𝑖 .𝑐
16: end if
17: end for
18: return 𝜒
3. Porém, é possível reduzir esse custo, sabendo que o número cromático em um grafo que não
é 𝐾𝑛 é limitado superiormente pelo maior grau. Seja 𝐾 o maior grau de um vértice em 𝐺,
então basta que as listas de cores contenham 𝐾 cores distintas, e não 𝑛, ou seja, o número de
operações gastas é:
1 + 2 + 3 + · · · + 𝐾 + 𝐾 + 𝐾 ≤ 𝑛𝐾
4. O loop principal do algoritmo percorre todos os vértices 𝑣 ∈ 𝐺 uma vez e, para cada vértice,
acessa os seus 𝑑(𝑣) vizinhos. Se utilizarmos um array estático, podemos apagar a cor color da
lista 𝐶𝑖 em 𝑂(1). Logo, a complexidade desse loop é:
5. Por fim, o último loop serve apenas para encontrar o maior rótulo utilizado como cor, o que é
equivalente a encontrar o máximo do vetor. Assim, o custo é 𝑂(𝑛).
Note que, no pior caso, 𝑚 = 𝑂(𝑛2 ), o que nos leva à conclusão de que a complexidade do algoritmo
Welsh & Powell é 𝑂(𝑛2 ).
A seguir, apresentaremos alguns exemplos de problemas que podem ser resolvidos através da
coloração de vértices.
192
O Problema da Alocação de Frequências
Considere 7 antenas de transmissão de sinais de telefonia. Sabe-se que, devido a fatores como
localização geográfica e tipo de serviço oferecido, as antenas possuem regiões de influência de modo
que temos a seguinte matriz de interferências:
Essa matriz indica quando duas antenas interferem uma na outra, representado por um “x”.
Pergunta-se:
1. Qual o menor número de frequências necessárias para que a comunicação se dê de forma cor-
reta?
1. Construção do grafo de incompatibilidade: Neste grafo, dois vértices são ligados por uma
aresta se existe interferência entre as duas antenas.
193
2. Ordenação dos vértices: Ordenar os vértices em ordem decrescente de graus: 𝑣1 , 𝑣3 , 𝑣5 , 𝑣6 , 𝑣4 , 𝑣2 , 𝑣7 .
3. Definição das listas de cores: Para cada vértice, criam-se listas de cores possíveis:
4. Coloração iterativa: Colorir os vértices seguindo a ordem e removendo as cores já usadas dos
vizinhos:
A aproximação para o número cromático obtida pelo algoritmo guloso é 𝜒(𝐺) = 3, o que, neste
caso, corresponde ao verdadeiro valor de 𝜒(𝐺). As partições obtidas são:
𝑃1 = {𝑣1 , 𝑣4 },
𝑃2 = {𝑣3 , 𝑣6 },
𝑃3 = {𝑣2 , 𝑣5 , 𝑣7 }.
194
O problema do semáforo
1º passo: Consiste em gerar o grafo de incompatibilidade. Para isso, cada uma das faixas de A a
H deve ser representada por um vértice, e a cada possível cruzamento de faixas deve existir uma aresta
(ou seja, deve existir uma aresta sempre que for possível ocorrer uma batida). O grafo resultante é
ilustrado na figura a seguir.
2º passo: Consiste na aplicação do algoritmo guloso (Welsh & Powell) para colorir o grafo acima
utilizando o menor número de cores possíveis. Como o grau máximo é 4 e o grafo não é completo,
195
temos garantia de que o número cromático é menor ou igual a 4. A execução desse passo é deixada
como exercício para o leitor.
O problema do aeroporto
Uma nova empresa aérea irá começar a operar com 7 aeronaves seguindo a programação de vôos
(de A a G) definida na tabela abaixo, sendo que todos os vôos partem de São Paulo e visitam cada
uma das cidades listadas nas rotas na sequência em que elas aparecem:
Vôo Rota
A Florianópolis – Rio de Janeiro – Natal – Fortaleza
B Curitiba – Campinas – Ribeirão Preto – Fortaleza
C Belo Horizonte – Natal – Fortaleza – Manaus
D Belo Horizonte – São José do Rio Preto – Rio de Janeiro
E Belo Horizonte – Recife – Natal
F Brasília – Ribeirão Preto – Fortaleza
G Brasília – Presidente Prudente – Campinas
Devido ao número limitado de aeronaves, o diretor da companhia não quer mais de um vôo por dia
visitando uma determinada cidade. Ou seja, se dois vôos passam pela mesma cidade X, eles devem
obrigatoriamente não estar alocados para o mesmo dia.
Modelando o problema com um grafo e utilizando coloração de vértices, determine o número
mínimo de dias necessários para que a empresa opere de acordo com sua política de funcionamento.
Definição 92. Para um grafo 𝐺 = (𝑉, 𝐸), seja 𝑃 (𝐺, 𝑘) o número de 𝑘-colorações válidas de 𝐺.
Pode-se mostrar que 𝑃 (𝐺, 𝑘) é um polinômio para todo grafo 𝐺.
Iremos iniciar com grafos simples e calcular os polinômios cromáticos fundamentais. Primeiro,
considere um grafo nulo com 3 vértices. Nesse caso, podemos utilizar 𝑘 cores em cada vértice, pois
não há arestas, e nenhum vértice é vizinho de outro:
196
𝑃 (𝐺1 , 𝑘) = 𝑘 3
𝑃 (𝐺2 , 𝑘) = 𝑘 2 (𝑘 − 1)
pois a cor do segundo vértice não pode ser utilizada para colorir o terceiro. Ao adicionarmos mais
uma aresta, o polinômio cromático fica:
É fácil notar que o grafo caminho de 𝑛 vértices, conhecido como 𝑃𝑛 (path), possui o seguinte
polinômio cromático:
197
𝑃 (𝐾𝑛 , 𝑘) = 𝑘(𝑘 − 1)(𝑘 − 2) . . . (𝑘 − (𝑛 − 1))
No caso de árvores, note que o polinômio cromático é idêntico ao do grafo caminho. Aliás, isso
já era esperado, uma vez que o grafo caminho é uma árvore:
Porém, surge a pergunta: como calcular o polinômio cromático para um grafo arbitrário? O
resultado a seguir é fundamental para responder a essa pergunta.
Teorema 68. Seja 𝐺 = (𝑉, 𝐸) um grafo simples e 𝑒 ∈ 𝐸 uma aresta de 𝐺. Então, o polinômio
cromático de 𝐺 satisfaz a seguinte relação de recorrência:
onde 𝐺 − 𝑒 denota o grafo obtido pela remoção da aresta 𝑒, e 𝐺/𝑒 representa o grafo obtido pela
contração da aresta 𝑒 em 𝐺.
Devido à complexidade matemática da demonstração, omitiremos aqui a prova formal deste re-
sultado. Um esboço intuitivo da prova é discutido a seguir.
Esboço intuitivo da prova. O polinômio cromático 𝑃 (𝐺, 𝑘) conta o número de 𝑘-colorações válidas
de um grafo 𝐺, isto é, atribuições de cores aos vértices de 𝐺 de modo que vértices adjacentes recebam
cores distintas. Seja 𝑒 = (𝑢, 𝑣) uma aresta de 𝐺.
198
2. As colorações inválidas para 𝐺 correspondem exatamente àquelas em que 𝑢 e 𝑣 recebem a
mesma cor. Nesse caso, podemos fundir os vértices 𝑢 e 𝑣 em um único vértice, obtendo o grafo
𝐺/𝑒 (contração da aresta 𝑒). O número dessas colorações é precisamente 𝑃 (𝐺/𝑒, 𝑘).
3. Portanto, para obter o número de colorações válidas de 𝐺, devemos subtrair do total 𝑃 (𝐺−𝑒, 𝑘)
aquelas que atribuem a mesma cor a 𝑢 e 𝑣. Assim:
Esse raciocínio mostra, de maneira intuitiva, porque o Teorema Fundamental da Redução é válido.
Para resolver, aplicamos o Teorema Fundamental da Redução a fim de gerar a árvore de decom-
posição do grafo. No primeiro estágio, devemos decompor os níveis da árvore até obter polinômios
cromáticos fundamentais. Em seguida, percorremos a árvore no sentido inverso, combinando os re-
sultados para calcular o polinômio cromático final de 𝐺.
Iniciamos pela aplicação do teorema fundamental da redução em 𝐺:
199
Como ambos são folhas, podemos voltar na árvore e computar o polinômio de 𝐶4 como:
Agora que temos o polinômio de 𝐶4 , podemos voltar e calcular o polinômio final de 𝐺 como:
𝑃 (𝐺, 5) = 5 × 4 × 32 = 20 × 9 = 180.
Exercício: Utilizando o teorema fundamental da redução, encontre o polinômio cromático dos grafos
200
a seguir. Mostre a árvore de decomposição.
201
Informações sobre o autor
Alexandre L. M. Levada é Bacharel em Ciência da Computação pela Universidade Estadual Pau-
lista (UNESP) em 2002. Concluiu seu Mestrado em Ciência da Computação pela Universidade Fe-
deral de São Carlos (UFSCar) em 2006 e seu Doutorado em Física Computacional pela Universidade
de São Paulo (USP) em 2010. No mesmo ano, ingressou no Departamento de Computação da Uni-
versidade Federal de São Carlos. De 2010 a 2024, foi professor assistente no Departamento de Com-
putação, onde lecionou diversas disciplinas de graduação e pós-graduação como lógica matemática,
teoria dos grafos, matemática discreta, processamento digital de imagens, análise de sinais e sistemas,
reconhecimento de padrões, visão computacional, algoritmos e estruturas de dados 1 e 2, projeto e
análise de algoritmos, programação científica e otimização matemática. Desde 2024 é professor as-
sociado do mesmo departamento. Seus principais temas de pesquisa incluem redução de ruído em
sinais e imagens, reconhecimento de padrões e aprendizado de máquina, com ênfase em algoritmos
de classificação baseados em grafos, métodos de redução de dimensionalidade baseados em teoria
da informação e aplicação da geometria da informação na análise da dinâmica de campos aleatórios.
É autor de um livro, 3 capítulos de livro, 28 artigos em periódicos e 56 artigos em conferências. É
bolsista produtividade nível C do CNPq.
“Se você tiver um pão e eu tiver um euro, e eu uso o meu euro para comprar o seu pão, no final
da troca eu terei o pão e você o euro. Parece um equilíbrio perfeito, não? A tem um euro, B
tem um pão; depois, A tem o pão e B o euro. É uma transação justa, mas meramente material.
Agora, imagine que você tem um soneto de Verlaine ou conhece o teorema de Pitágoras, e eu
não tenho nada. Se me ensinar, no final dessa troca, eu terei aprendido o soneto e o teorema,
mas você ainda os terá também. Nesse caso, não há apenas equilíbrio, mas crescimento. No
primeiro, trocamos mercadorias. No segundo, compartilhamos conhecimento. E enquanto a
mercadoria se consome, a cultura se expande infinitamente.”
202
Referências
Kenneth H. Rosen. Discrete Mathematics and its Applications, 8ª edição, McGraw Hill, 2019.
Susanna S. Epp. Discrete Mathematics with Applications, 4ªedição, Cengage Learning, 2011.
Anamaria Gomide; Jorge Stolfi. Elementos de Matemática Discreta para Computação, 2013. Dispo-
nível em: [Link]
[Link]
Clifford Stein; Robert L. Drysdale; Kenneth Bogart. Matemática discreta para ciências da computa-
ção, Pearson, 2013.
Paulo Blauth Menezes. Matemática Discreta Para Computação e Informática, 4ª Edição, Bookman,
2013.
Paulo Blauth Menezes; Laira Vieira Toscani; Javier García López. Aprendendo Matemática Discreta
com Exercícios, 1ª Edição, 2009.
Maria do Carmo Nicoletti; Estevam R. Hruschka Jr. Fundamentos da Teoria dos Grafos para Com-
putação, 2ª edição, Série Apontamentos, EdUFSCar, 2009.
Robin Wilson. Introduction to Graph Theory, 3ª edição, Longman Scientific & Technical, 1985.
John Clark; Derek Allan Holton. A First Look at Graph Theory. World Scientific, 1998.
203