Apostila de Aula Prof. Ruy Milidiu

Prévia do material em texto

Matema´tica Discreta
para Computac¸a˜o
versa˜o 11.0
Ruy Luiz Milidiu´
12 de agosto de 2013
Suma´rio
1 Introduc¸a˜o 1
1.1 Computadores . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 Programas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.3 Enfoque . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Noc¸o˜es Elementares 7
2.1 Conjuntos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Relac¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.3 Func¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
3 Argumentac¸a˜o 9
3.1 Bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.2 A´lgebra Booleana . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2.1 Axiomas . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2.2 Propriedades . . . . . . . . . . . . . . . . . . . . . . . 12
3.2.3 Dualidade . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.3 Implicac¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.3.1 Definic¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.3.2 Ordenac¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . 16
3.4 Racioc´ınio . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.4.1 Equac¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.4.2 Deduc¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4 Induc¸a˜o Fraca 21
4.1 Os Naturais . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2 O Princ´ıpio . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.3 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.3.1 Somas . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
i
ii SUMA´RIO
4.3.2 Divisibilidade Exata . . . . . . . . . . . . . . . . . . . 22
4.3.3 Combinato´ria . . . . . . . . . . . . . . . . . . . . . . . 24
4.4 Exerc´ıcios . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24
5 Induc¸a˜o Forte 25
5.1 O Princ´ıpio . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
5.2 Exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
6 Induc¸a˜o Estrutural 27
6.1 Sequencias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
6.2 O Princ´ıpio . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
6.3 Nu´meros de Fibonacci . . . . . . . . . . . . . . . . . . . . . . 28
6.4 Sequencias de Pareˆnteses . . . . . . . . . . . . . . . . . . . . . 30
7 A´rvores e Florestas Livres 35
7.1 A´rvores Livres . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
7.2 Representac¸a˜o Sequencial . . . . . . . . . . . . . . . . . . . . 37
7.3 Florestas Livres . . . . . . . . . . . . . . . . . . . . . . . . . . 38
8 A´rvores Bina´rias 39
8.1 A´rvores Bina´rias Estendidas . . . . . . . . . . . . . . . . . . . 39
8.2 A´rvores Estritamente Bina´rias . . . . . . . . . . . . . . . . . . 41
8.3 A´rvores Bina´rias Cheias . . . . . . . . . . . . . . . . . . . . . 42
8.4 A´rvores Bina´rias Balanceadas por Altura . . . . . . . . . . . . 42
8.5 A´rvores de Fibonacci . . . . . . . . . . . . . . . . . . . . . . . 43
8.6 A´rvores Bina´rias Posicionais . . . . . . . . . . . . . . . . . . . 44
9 Florestas de Unia˜o e Busca 45
10 O Algoritmo de Euclides 49
10.1 Ma´ximo Divisor Comum . . . . . . . . . . . . . . . . . . . . . 49
10.2 O Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
10.3 Corretude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
10.4 Eficieˆncia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
11 O Teorema de Stone 53
11.1 A´tomos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53
11.2 Decomposic¸a˜o Estrutural . . . . . . . . . . . . . . . . . . . . . 54
SUMA´RIO iii
12 Grafos 55
12.1 Conceitos Ba´sicos . . . . . . . . . . . . . . . . . . . . . . . . . 55
12.1.1 Ve´rtices . . . . . . . . . . . . . . . . . . . . . . . . . . 55
12.1.2 Arestas . . . . . . . . . . . . . . . . . . . . . . . . . . 55
12.1.3 Incideˆncia . . . . . . . . . . . . . . . . . . . . . . . . . 56
12.2 Grafos e Subgrafos . . . . . . . . . . . . . . . . . . . . . . . . 56
13 Grafos Simples 59
13.1 Representac¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
13.2 Grafos Derivados . . . . . . . . . . . . . . . . . . . . . . . . . 61
13.3 Passeios, Trilhas e Caminhos . . . . . . . . . . . . . . . . . . . 61
13.4 Circuitos e Ciclos . . . . . . . . . . . . . . . . . . . . . . . . . 63
13.5 Esparsidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
13.6 A´rvores Livres e Geradoras . . . . . . . . . . . . . . . . . . . . 63
13.7 Componentes Conexos . . . . . . . . . . . . . . . . . . . . . . 63
13.8 Grafos Bipartidos . . . . . . . . . . . . . . . . . . . . . . . . . 65
13.9 Articulac¸o˜es e Pontes . . . . . . . . . . . . . . . . . . . . . . . 65
13.10Componentes Biconexos . . . . . . . . . . . . . . . . . . . . . 66
14 Grafos Dirigidos 69
14.1 Representac¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
14.2 Grafos Derivados . . . . . . . . . . . . . . . . . . . . . . . . . 70
14.3 Passeios, Trilhas e Caminhos . . . . . . . . . . . . . . . . . . . 70
14.4 Circuitos e Ciclos . . . . . . . . . . . . . . . . . . . . . . . . . 71
14.5 Grafos Especiais . . . . . . . . . . . . . . . . . . . . . . . . . . 71
14.6 Grafos Ac´ıclicos . . . . . . . . . . . . . . . . . . . . . . . . . . 71
14.7 Ordenac¸a˜o Topolo´gica . . . . . . . . . . . . . . . . . . . . . . 72
14.8 Componentes Fortemente Conexos . . . . . . . . . . . . . . . 72
15 Otimizac¸a˜o em Grafos 73
15.1 Pareamentos Ma´ximos . . . . . . . . . . . . . . . . . . . . . . 73
15.2 Pareamentos Perfeitos . . . . . . . . . . . . . . . . . . . . . . 74
15.3 A´rvores Geradoras Mı´nimas . . . . . . . . . . . . . . . . . . . 75
15.3.1 Gerac¸a˜o de Arestas Candidatas . . . . . . . . . . . . . 76
15.3.2 Integrac¸a˜o de Arestas Candidatas . . . . . . . . . . . . 76
15.3.3 Algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . 76
15.4 A´rvores de Huffman . . . . . . . . . . . . . . . . . . . . . . . . 77
15.5 A´rvores de Busca Ponderadas Mı´nimas . . . . . . . . . . . . . 77
iv SUMA´RIO
16 Princ´ıpios Ba´sicos de Contagem 79
16.1 Adic¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
16.2 Multiplicac¸a˜o . . . . . . . . . . . . . . . . . . . . . . . . . . . 79
17 O Princ´ıpio do Pombal 81
17.1 O Princ´ıpio . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81
17.2 Aplicac¸o˜es . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82
18 Coeficientes Binomiais 83
18.1 Arranjos, permutac¸o˜es e combinac¸o˜es . . . . . . . . . . . . . . 83
18.2 Coeficientes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84
18.3 Triaˆngulo de Pascal . . . . . . . . . . . . . . . . . . . . . . . . 84
18.4 Binoˆmio de Newton . . . . . . . . . . . . . . . . . . . . . . . . 85
18.5 Propriedades . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
Cap´ıtulo 1
Introduc¸a˜o
1.1 Computadores
Os computadores esta˜o por toda parte. Sua versatilidade e´ fabulosa. Esta˜o
presentes no acionamento dos despertadores que tocam diariamente, no con-
trole das agendas de atividades, na apurac¸a˜o de saldos banca´rios, e no geren-
ciamento do tra´fego e das comunicac¸o˜es. Estas sa˜o apenas algumas de suas
inu´meras aplicac¸o˜es. Algumas delas, como a Internet e a World Wide Web,
revolucionam o nosso dia-a-dia.
A universalidade da computac¸a˜o repousa em princ´ıpios simples originados
na Lo´gica e na Matema´tica.
Os computadores sa˜o um artefato que mecaniza o racioc´ınio lo´gico com-
binado com operac¸o˜es matema´ticas. Esta concepc¸a˜o ta˜o abstrata permite
aplicar os computadores aos mais variados processos, da mesma forma que
os nu´meros inteiros sa˜o utilizados para equacionarmos os mais variadostipos
de grandezas de nosso interesse.
1.2 Programas
Os computadores sa˜o versa´teis porque atrave´s da programac¸a˜o adaptamos
seu uso para diferentes tarefas. E´ com os programas que tornarmos uma
ma´quina de uso gene´rico num artefato especializado para cada tarefa de
nosso interesse.
O exemplo cla´ssico utilizado na apresentac¸a˜o de qualquer linguagem de
programac¸a˜o e´ o popular Hello World!. O exemplo a seguir tem o mesmo
1
2 CAPI´TULO 1. INTRODUC¸A˜O
tipo de simplicidade, sendo utilizado para ilustrar as te´cnicas de prova de
corretude. Observe que ele inclue um loop de repetic¸a˜o!
Exemplo 1 (Soma de P.A.) O programa somaPA determina o valor da
soma dos n primeiros nu´meros inteiros, isto e´, o valor de 1 + 2 + · · ·+ n.
1. int somaPA (int n) {
2. int somaParcial;
3. somaParcial = 0;
4. for i= 1 to n {
5. somaParcial = somaParcial + i
6. }
7. return (somaParcial)
8. }
Os artefatos computacionais de boa qualidade devem executar correta-
mente as tarefas para as quais foram projetados. Ale´m disso, como todo
bem de natureza econoˆmica, devem ser parcimoniosos no consumo de recur-
sos humanos e materiais.
Para demonstrar a corretude do programa somaPA, vamos monitorar os
valores assumidos pela varia´vel somaParcial.
Na linha 3, somaParcial tem seu valor inicializado como 0. Assim, pode-
mos garantir esse valor nesse ponto do programa. Apo´s a linha 5, afirmamos
que o valor de somaParcial e´ 1 + 2 + ...+ i. Esta e´ uma afirmativa gene´rica,
que estamos fazendo para cada iterac¸a˜o do valor i no loop. Finalmente, ao
sair do loop, afirmamos que o valor de somaParcial e´ 1 + 2 + ...+ n.
Acrescentemos estas observac¸o˜es como comenta´rios em nosso programa.
1. int somaPA (int n) {
2. int somaParcial;
3. somaParcial = 0;
// neste ponto, somaParcial vale 0
4. for i= 1 to n {
5. somaParcial = somaParcial + i
// neste ponto, somaParcial vale 1+2+...+i
6. }
1.2. PROGRAMAS 3
// neste ponto, somaParcial vale 1+2+...+n
7. return (somaParcial)
8. }
Das treˆs afirmac¸o˜es anteriores, a segunda, por ser gene´rica, e´ a mais dif´ıcil
de ser demonstrada. Para demonstrar essa afirmativa vamos definir uma se-
quencia de valores s0, s1, s2, · · · , sn como sendo os n+1 valores sucessivamente
assumidos pela varia´vel somaParcial. Como ilustrac¸a˜o, computamos os oito
primeiros valores obtendo
0, 1, 3, 6, 10, 15, 21, 28, · · · .
A afirmativa gene´rica pode ser reformulada como
si tem valor igual a 1 + 2 + ...+ i
para i = 1, 2, · · · , n.
Observe que a linha 3 estabelece que
s0 = 0
e a linha 5 estabelece que
si = si−1 + i.
Assim, e´ fa´cil verificar que
s1 = s0 + 1 = 1.
Portanto, a afirmativa e´ va´lida na primeira passagem do loop. Se a afirmativa
e´ va´lida na iterac¸a˜o anterior, enta˜o na iterac¸a˜o atual temos que
si = si−1 + i = [1 + 2 + ...+ (i− 1)] + i,
donde
si = 1 + 2 + ...+ i
isto e´, a afirmativa tambe´m e´ va´lida na iterac¸a˜o atual.
Com a estrate´gia de argumentac¸a˜o apresentada, garantimos a corretude
de somaPA sem a necessidade de efetuar qualquer tipo de teste com entradas
para nosso programa.
4 CAPI´TULO 1. INTRODUC¸A˜O
1.3 Enfoque
O objetivo central deste texto e´ apresentar os fundamentos matema´ticos da
computac¸a˜o de forma intuitiva, sucinta e precisa.
Nossa eˆnfase e´ na apresentac¸a˜o das te´cnicas elementares de argumentac¸a˜o,
aplicadas as estruturas ba´sicas da computac¸a˜o. Assim, examinamos as questo˜es
de corretude, essenciais na construc¸a˜o de artefatos computationais de boa
qualidade. Nos cap´ıtulos 3 a 15, tratamos deste tema.
Adicionalmente, apresentamos as te´cnicas elementares de contagem, es-
senciais na ana´lise da eficieˆncia dos artefatos propostos. Os cap´ıtulos 17 a
18 constituem a segunda parte deste texto, cobrindo este tema.
No cap´ıtulo 2, apresentamos as noc¸o˜es elementares de conjuntos e suas
operac¸o˜es, relac¸o˜es e func¸o˜es.
No cap´ıtulo 3, apresentamos os fundamentos da Argumentac¸a˜o. Para
isso, introduzimos as a´lgebras Booleanas. Este formalismo permite explorar
as propriedades dos bits lo´gicos.
No cap´ıtulo 4, apresentamos o Princ´ıpio da Induc¸a˜o Matema´tica Fraca.
Com este princ´ıpio exploramos inicialmente as propriedades dos nu´meros
naturais.
No cap´ıtulo 5, apresentamos o Princ´ıpio da Induc¸a˜o Matema´tica Forte.
No cap´ıtulo 6, apresentamos o Princ´ıpio da Induc¸a˜o Estrutural. Para
ilustrar o uso deste princ´ıpio, examinamos os nu´meros de Fibonacci e as
Sequencias Bem Formadas de Pareˆnteses.
No cap´ıtulo 7, aplicamos a Induc¸a˜o Estrutural para demonstrar diversas
propriedades das a´rvores e florestas livres.
No cap´ıtulo 8, aplicamos a Induc¸a˜o Estrutural para demonstrar diversas
propriedades das A´rvores Bina´rias.
No cap´ıtulo 9, aplicamos a Induc¸a˜o Estrutural para demonstrar diversas
propriedades das Florestas de Unia˜o e Busca.
No cap´ıtulo 10, aplicamos a Induc¸a˜o Estrutural para demonstrar a cor-
retude e analisar a eficieˆncia do Algoritmo de Euclides.
No cap´ıtulo 11, aplicamos a Induc¸a˜o Estrutural para demonstrar a cor-
retude do Teorema de Stone.
No cap´ıtulo 12, introduzimos os conceitos e definic¸o˜es ba´sicos da Teoria
dos Grafos.
No cap´ıtulo 13, examinamos as propriedades elementares de conectividade
em Grafos Simples.
1.3. ENFOQUE 5
No cap´ıtulo 14, examinamos as propriedades elementares de conectividade
em Grafos Dirigidos.
No cap´ıtulo 15, apresentamos alguns problemas cla´ssicos em Otimizac¸a˜o
Combinato´ria.
No cap´ıtulo 17, introduzimos e ilustramos o Princ´ıpio do Pombal.
No cap´ıtulo 18, apresentamos os coeficientes binomiais e suas principais
propriedades.
6 CAPI´TULO 1. INTRODUC¸A˜O
Cap´ıtulo 2
Noc¸o˜es Elementares
2.1 Conjuntos
2.2 Relac¸o˜es
2.3 Func¸o˜es
7
8 CAPI´TULO 2. NOC¸O˜ES ELEMENTARES
Cap´ıtulo 3
Argumentac¸a˜o
Uma argumentac¸a˜o rigorosa esta´ fundamentada nos so´lidos princ´ıpios da
Lo´gica.
Um dos objetivos centrais da argumentac¸a˜o e´ estabelecer se uma deter-
minada afirmac¸a˜o e´ verdadeira ou falsa.
Esta dicotomia entre o verdadeiro e o falso pode ser representada de forma
bina´ria:
1. - o valor 1 representa verdadeiro;
2. - o valor 0 representa falso.
Usualmente, iniciamos com algumas proposic¸o˜es para as quais sabemos
seus valores-verdade. A partir das inter-relac¸o˜es entre essas proposic¸o˜es de-
terminamos os valores-verdade de novas proposic¸o˜es de interesse. Argumen-
tando desta forma, estabelecemos se as novas proposic¸o˜es sa˜o verdadeiras ou
falsas.
A a´lgebra Booleana e´ uma maneira elegante e concisa de representarmos
os conceitos e operac¸o˜es dos referidos processos de argumentac¸a˜o.
Neste cap´ıtulo, apresentamos dois fundamentos matema´ticos: o ca´lculo
proposicional e a a´lgebra de conjuntos. Para isto, utilizamos os bits.
3.1 Bits
O bit e´ a unidade de informac¸a˜o. Sua primeira aplicac¸a˜o e´ para representar
os valores-verdade utilizados em expresso˜es lo´gicas que controlam o fluxo
9
10 CAPI´TULO 3. ARGUMENTAC¸A˜O
das operac¸o˜es em nossos programas. Uma outra aplicac¸a˜o fundamental e´ a
representac¸a˜o de conjuntos atrave´s de vetores de bits.
Por exemplo, considere os seguintes conjuntos de pessoas:
A = {Guilherme, Paula, Pedro}
e
B = {Eraldo, Carlos,Guilherme,Benjamim}.
Associemos os elementos
Guilherme, Paula, Eraldo, Pedro, Carlos e Benjamim
as posic¸o˜es 1, 2, 3, 4, 5 e 6, respectivamente.
Neste caso, temos que os conjuntos A e B podem ser representados como
vetores de bits por
A = (1, 1, 0, 1, 0, 0) e B = (1, 0, 1, 0, 1, 1),
onde o bit ligado na posic¸a˜o k indica que o k−e´simo elemento pertence ao
correspondente conjunto.
3.2 A´lgebra Booleana
3.2.1 Axiomas
Uma a´lgebra Booleana (B, +, .,−) e´ uma estrutura alge´brica constituida por
quatro elementos, a saber:
B um conjunto finito;+ uma operac¸a˜o bina´ria de B ×B → B;
. uma operac¸a˜o bina´ria de B ×B → B;
− uma operac¸a˜o una´ria de B → B.
Ale´m disso, temos a seguinte ordem de precedeˆncia entre parentesis e
operac¸o˜es: ( ), −, ., +
Nesta estrutura alge´brica, valem quatro grupos de axiomas descritos a
seguir.
Para todo x, y, z ∈ B temos:
3.2. A´LGEBRA BOOLEANA 11
Axioma 1 (Identidade) existem dois elementos 0, 1 ∈ B tais que
0 + x = x + 0 = x
1 . x = x . 1 = x
Axioma 2 (Complemento)
x + x¯ = 1
x . x¯ = 0
Axioma 3 (Comutatividade)
x + y = y + x
x . y = y . x
Axioma 4 (Distributividade)
x . (y + z) = x . y + x . z
x + (y . z) = (x + y) . (x + z)
Exemplo 2 (Lo´gica Booleana) Consideremos o caso em que B = {0, 1}
e as treˆs operac¸o˜es sa˜o definidas pelas tabelas a seguir.
+ 0 1 . 0 1 x x
0 0 1 0 0 0 0 1
1 1 1 1 0 1 1 0
Exemplo 3 Consideremos o caso em que B = {F, T} e as treˆs operac¸o˜es
sa˜o definidas pelas tabelas a seguir.
+ F T . F T x x
F F T F F F F T
T T T T F T T F
Exemplo 4 Consideremos o caso em que B = {a, b} e as treˆs operac¸o˜es sa˜o
definidas pelas tabelas a seguir.
+ a b . a b x x
a a b a a a a b
b b b b a b b a
12 CAPI´TULO 3. ARGUMENTAC¸A˜O
Exemplo 5 (Vetores de Bits) Consideremos o caso em que B = {00, 01, 10, 11}
e as treˆs operac¸o˜es sa˜o definidas pelas tabelas a seguir.
+ 00 01 10 11 . 00 01 10 11 x x
00 00 01 10 11 00 00 00 00 00 00 11
01 01 01 11 11 01 00 01 00 01 01 10
10 10 11 10 11 10 00 00 10 10 10 01
11 11 11 11 11 11 00 01 10 11 11 00
Exemplo 6 (a´lgebra de Conjuntos) Consideremos o caso em que B =
{X|X ⊆ U} e as treˆs operac¸o˜es sa˜o definidas como
X + Y = X
⋃
Y X.Y = X
⋂
Y X = U −X.
Exemplo 7 (Divisores de 30) Seja B o conjunto dos divisores de 30, isto
e´, B = {1, 2, 3, 5, 6, 10, 15, 30} Para x, y ∈ B as treˆs operac¸o˜es sa˜o definidas
como
x+ y = mmc(x, y) x.y = mdc(x, y) x = 30/x.
Exerc´ıcio 1 Mostre que as estruturas definidas nos exemplos 2 a 7 sa˜o
a´lgebras Booleanas.
3.2.2 Propriedades
Seja (B, +, .,−) uma a´lgebra Booleana. A seguir, enumeramos uma se´rie de
propriedades va´lidas nesta estrutura.
AB 1 (Unicidade dos Neutros) O neutro aditivo e´ u´nico. O neutro mul-
tiplicativo e´ u´nico.
AB 2 (Idempoteˆncia)
x = x.x x = x+ x
AB 3 (Unicidade do Complemento) Se x+y = 1 e x.y = 0 enta˜o y = x.
AB 4 (Involuc¸a˜o)
x = x
3.2. A´LGEBRA BOOLEANA 13
AB 5
0 = 1 1 = 0
AB 6 (Dominac¸a˜o)
x.0 = 0 x+ 1 = 1
AB 7 (Absorc¸a˜o)
x+ x.y = x x.(x+ y) = x
AB 8 (Absorc¸a˜o Generalizada)
x.(y + (x+ z)) = x x+ (y.(x.z)) = x
AB 9 (Associatividade)
x+ (y + z) = (x+ y) + z x.(y.z) = (x.y).z
AB 10 (Leis de DeMorgan)
x+ y = x.y x.y = x+ y
Exerc´ıcio 2 Demonstre a validade das dez propriedades anteriores.
Exerc´ıcio 3 Mostre que se 0 = 1 enta˜o |B| = 1.
Exerc´ıcio 4 Mostre que se existe um elemento b ∈ B tal que b¯ = b enta˜o
|B| = 1.
Exerc´ıcio 5 Mostre que |B| 6= 3.
Exerc´ıcio 6 Mostre que se |B| > 1 enta˜o |B| e´ par.
No cap´ıtulo 11, mostraremos que existe k = 0, 1, 2, . . . tal que |B| = 2k.
Este resultado e´ o chamado Teorema de Stone.
14 CAPI´TULO 3. ARGUMENTAC¸A˜O
3.2.3 Dualidade
Os axiomas que definem uma a´lgebra Booleana foram apresentados aos pares.
Uma consequencia disso e´ que as propriedades decorrentes tambe´m ocorrem
aos pares.
Nesta sec¸a˜o, vamos introduzir o conceito de dualidade que sistematiza
essas observac¸o˜es.
Definic¸a˜o 1 (Expressa˜o Dual) Seja F (x1, · · · , xn) uma expressa˜o boole-
ana nas variaveis x1, · · · , xn. Definimos FD como a expressa˜o dual de F
atrave´s da seguinte relac¸a˜o
FD(x1, · · · , xn) = F (x1, · · · , xn)
Exemplo 8 Seja F (x, y, z) = (x+ y).z.
Neste caso, temos que a expressa˜o dual FD e´ dada por
FD(x, y, z) = (x+ y).z (definic¸a˜o de dual)
= (x+ y) + z (de Morgan)
= (x.y) + z (de Morgan)
= (x.y) + z (involuc¸a˜o)
As seguintes propriedades da dualidade sa˜o facilmente demonstraveis.
DUAL 1 (FD)
D
= F
DUAL 2 (0)D = 1
DUAL 3 (1)D = 0
DUAL 4 (x)D = x
DUAL 5 (x)D = x
DUAL 6 (x+ y)D = x.y
DUAL 7 (x.y)D = x+ y
DUAL 8 (E1(x1, · · · , xn) + E2(x1, · · · , xn))D = ED1 (x1, · · · , xn).ED2 (x1, · · · , xn)
3.2. A´LGEBRA BOOLEANA 15
DUAL 9 (E1(x1, · · · , xn).E2(x1, · · · , xn))D = ED1 (x1, · · · , xn)+ED2 (x1, · · · , xn)
DUAL 10 Se para todo x1, · · · , xn ∈ B temos que E1(x1, · · · , xn) = E2(x1, · · · , xn)
enta˜o para todo x1, · · · , xn ∈ B temos tambe´m que ED1 (x1, · · · , xn) = ED2 (x1, · · · , xn).
Agora, podemos revisitar o exemplo 8 com o aux´ılio das propriedades da
dualidade.
Exemplo 9 Seja F (x, y, z) = (x+ y).z.
Utilizando a dualidade, obtemos a expressa˜o dual FD por
FD(x, y, z) = ((x+ y).z)D
= (x+ y)D + z
= (x.y) + z
Exerc´ıcio 7 Demonstre a validade das nove propriedades da dualidade.
Como consequencia da dualidade, podemos formular a seguinte regra
pra´tica.
REGRA 1 (Dualizac¸a˜o) Para determinar a expressa˜o dual, substitua
+ por . . por +
0 por 1 1 por 0
e a expressa˜o resultante e´ a dual.
Exemplo 10 Seja F (x, y, z) = (x+ y).z.
Pela regra de dualizac¸a˜o, obtemos a expressa˜o dual FD como
FD(x, y, z) = ((x + y) . z)D
= (x . y) + z
Exerc´ıcio 8 Determine a expressa˜o dual de (x+ y.z) + w.(z + y.x).
Exerc´ıcio 9 Determine a propriedade dual de x.(x+ y) = x.
Exerc´ıcio 10 Determine a propriedade dual de x.0 = 0.
16 CAPI´TULO 3. ARGUMENTAC¸A˜O
3.3 Implicac¸a˜o
3.3.1 Definic¸a˜o
A partir das operac¸o˜es ba´sicas de uma a´lgebra booleana podemos definir
operac¸o˜es auxiliares. Estas operac¸o˜es reunem combinac¸o˜es interessantes e
convenientes dos operadores ba´sicos. Por sua alta frequencia de uso, recebem
um novo s´ımbolo especial que as identifica.
A mais importante delas e´ a implicac¸a˜o, que definimos a seguir. O seu
s´ımbolo e´ a seta para a direita mostrada abaixo
→
Definic¸a˜o 2 (Implicac¸a˜o) Numa a´lgebra booleana, definimos a operac¸a˜o
bina´ria a→ b por
a→ b = a+ b
IMPL 1 (Contraposic¸a˜o)
a→ b = b→ a
IMPL 2
a.(a→ b) = a.b
IMPL 3 a→ b = 1 se e somente se a.b = a
Exerc´ıcio 11 Demonstre a validade das treˆs propriedades da implicac¸a˜o.
3.3.2 Ordenac¸a˜o
Numa a´lgebra booleana, uma relac¸a˜o muito especial ocorre entre dois ele-
mentos a e b quando temos que
a.b = a
Neste caso, dizemos que a e´ menor ou igual a b e denotamos por
a ≤ b
OBL 1 a ≤ b se e somente se a→ b = 1
3.4. RACIOCI´NIO 17
OBL 2 a ≤ b se e somente se a+ b = b
OBL 3 (Extremos) 0 ≤ a ≤ 1
OBL 4 (Ordem Parcial)
reflexiva a ≤ a
anti-sime´trica se a ≤ b e b ≤ a enta˜o a = b
transitiva se a ≤ b e b ≤ c enta˜o a ≤ c
OBL 5 a.b ≤ a ≤ a+ b
OBL 6 a ≤ b se e somente se b ≤ a
OBL 7 se a ≤ b enta˜o a+ c ≤ b+ c.
OBL 8 se a ≤ b enta˜o c.a ≤ c.b.
OBL 9 se a ≤ b e c ≤ d enta˜o a+ c ≤ b+ d.
OBL 10 se a ≤ b e c ≤ d enta˜o a.c ≤ b.d.
OBL 11 a ≤ b e a ≤ c se e somente se a ≤ b.c.
OBL 12 a ≤ b e a ≤ b se e somente se a = 0.
OBL 13 b ≤ a e b ≤ a se e somente se a = 1.
Exerc´ıcio 12 Demonstre a validade das treze propriedades da ordenac¸a˜o
booleana.
3.4 Racioc´ınio
As a´lgebras Booleanas traduzem num formato alge´brico diferentes concei-
tos estruturais. Dentre eles destacamos aqueles necessa´rios a uma boa ar-
gumentac¸a˜o, bem como os envolvidos no tratamento de conjuntos e seus
elementos.
18 CAPI´TULO 3. ARGUMENTAC¸A˜O
3.4.1 Equac¸o˜es
A partir de expresso˜es envolvendo variaveis e operadores de uma a´lgebra
Booleana podemos estabelecer interessantes equac¸o˜es. Estas sa˜o as chamadas
equac¸o˜es booleanas.
A seguir, examinamos algumas equac¸o˜es extremamente simples apresen-
tando suas respectivas soluc¸o˜es.
EQN 1 x+ y = 0
Neste caso,
x+ y = 0
(x+ y).x = 0.x
(x+ y).x = 0
x = 0
Pela comutatividade da adic¸a˜o segue que
y = 0
Exerc´ıcio 13 Resolva a equac¸a˜o x + y = 0 utilizandoas propriedades da
ordem parcial ≤ definida na a´lgebra Booleana.
EQN 2 x.y = 1
Neste caso,
x.y = 1
(x.y) + x = 1 + x
(x.y) + x = 1
x = 1
Pela comutatividade da adic¸a˜o segue que
y = 1
Exerc´ıcio 14 Resolva a equac¸a˜o x.y = 1 utilizando as propriedades da or-
dem parcial ≤ definida na a´lgebra Booleana.
3.4. RACIOCI´NIO 19
Como para os neutros temos obviamente que 0 + 0 = 0 e 1 + 1 = 1,
podemos concluir enta˜o que
x+ y = 0⇔ x = 0 , y = 0
e
x.y = 1⇔ x = 1 , y = 1
Uma consequencia imediata do resultado anterior e´ que um sistema de
equac¸o˜es booleanas do tipo
expression1 = 1
expression2 = 1
...
expressionn = 1
e´ equivalente a uma u´nica equac¸a˜o dada por
expression1.expression2. · · · .expressionn = 1
Exemplo 11 O sistema de equac¸o˜es booleanas dado por
(x+ y).(z + w) = 1
w + y = 1
z.y = 1
equivale a
[(x+ y).(z + w)].(w + y).(z.y) = 1
3.4.2 Deduc¸a˜o
Aqui vamos mostrar como diversas regras de deduc¸a˜o podem ser obtidas via
a manipulac¸a˜o alge´brica de alguns sistemas simples de relac¸o˜es booleanas.
RD 1 (Modus Ponens) Para o sistema de relac¸o˜es booleanas{
x = 1
x ≤ y
temos que y = 1.
20 CAPI´TULO 3. ARGUMENTAC¸A˜O
RD 2 (Silogismo Hipote´tico) Para o sistema de relac¸o˜es booleanas{
x ≤ y
y ≤ z
temos que x ≤ z.
RD 3 Para o sistema de relac¸o˜es booleanas
x1 ≤ x2
x2 ≤ x3
...
xn−1 ≤ xn
temos que x1 ≤ xn.
RD 4 (Contraposic¸a˜o) y ≤ x se e so´ se x ≤ y
RD 5 (Modus Tolens) Para o sistema de relac¸o˜es booleanas{
x = 1
y ≤ x
temos que y = 1.
RD 6 (Reduc¸a˜o a Casos) Para o sistema de relac¸o˜es booleanas{
c ≤ x
c ≤ x
temos que x = 1.
RD 7 (Resoluc¸a˜o) Para o sistema de relac¸o˜es booleanas{
c ≤ x
c ≤ y
temos que x+ y = 1.
RD 8 (Reduc¸a˜o ao Absurdo) x.y ≤ 0 se e so´ se x ≤ y
Exerc´ıcio 15 Demonstre a validade das oito regras de deduc¸a˜o apresenta-
das.
Cap´ıtulo 4
Induc¸a˜o Fraca
4.1 Os Naturais
4.2 O Princ´ıpio
Para o sistema de relac¸o˜es booleanas
x1 = 1
x1 ≤ x2
x2 ≤ x3
...
xn−1 ≤ xn
...
temos que xn = 1 para n = 1, 2, ....
Reformulando, se pudermos mostrar que{
x1 = 1 (passo ba´sico)
xn ≤ xn+1 para n = 1, 2, · · · (passo indutivo)
enta˜o temos que
xn = 1 para n = 1, 2, · · ·
Assim, basta mostrar a validade do passo ba´sico e do passo indutivo.
Como consequeˆncia temos xn = 1 para n = 1, 2, · · ·.
21
22 CAPI´TULO 4. INDUC¸A˜O FRACA
4.3 Exemplos
4.3.1 Somas
Exemplo 12 (Soma de Inteiros) Para n = 1, 2, ... temos que
n∑
i=1
i = n.(n+ 1)/2
Exemplo 13 (Soma de ı´mpares) Para n = 1, 2, ... temos que
n∑
i=1
(2.i− 1) = n2
Exemplo 14 (Soma de Quadrados) Para n = 1, 2, ... temos que
n∑
i=1
i2 = n.(n+ 1).(2n+ 1)/6
Exemplo 15 Para n = 1, 2, ... temos que
n∑
i=1
i.(i+ 1) = n.(n+ 1).(n+ 2)/3
Exemplo 16 (Soma de Cubos) Para n = 1, 2, ... temos que
n∑
i=1
i3 = n2.(n+ 1)2/4
Exemplo 17 (Soma da P.G.) Para n = 1, 2, ... temos que
n∑
i=0
2i = 2n+1 − 1
4.3.2 Divisibilidade Exata
Definic¸a˜o 3 (Mu´ltiplo) Sejam a e b dois inteiros. Dizemos que a e´ mu´ltiplo
de b quando existe um inteiro c tal que
a = c.b .
4.3. EXEMPLOS 23
Exemplo 18 Para n = 1, 2, ... temos que
n.(n+ 1) e´ mu´ltiplo de 2.
Exemplo 19 Para n = 1, 2, ... temos que
n.(n+ 1).(n+ 2) e´ mu´ltiplo de 3.
Exemplo 20 Seja k um inteiro maior que 1. Para n = 1, 2, ... temos que
n.(n+ 1). · · · .(n+ k − 1) e´ mu´ltiplo de k.
Exemplo 21 Para n = 1, 2, ... temos que
n3 − n e´ mu´ltiplo de 3.
Exemplo 22 Seja b um natural fixo. Para n = 1, 2, ... temos que
bn − 1 e´ mu´ltiplo de b− 1.
Exemplo 23 Seja b um natural fixo. Para n = 1, 2, ... temos que
bn − 1 = (b− 1).
n−1∑
i=0
bi.
Exemplo 24 Para n = 0, 1, ... temos que
10n − 1 e´ mu´ltiplo de 9.
Exemplo 25 Para n = 0, 1, ... temos que
11n+2 + 122n+1 e´ mu´ltiplo de 133.
Exemplo 26 Para n = 0, 1, ... temos que
5n+1 + 2.3n + 1 e´ mu´ltiplo de 8.
24 CAPI´TULO 4. INDUC¸A˜O FRACA
4.3.3 Combinato´ria
Exemplo 27 (Cobertura com Triomino´s) Considere um tabuleiro T com
2n× 2n casas. Um triomino´ e´ um conjunto de treˆs casas adjacentes no tabu-
leiro, no formato de um L. Uma cobertura de T por triomino´s e´ um conjunto
de triomino´s com as seguintes propriedades:
1. os triomino´s sa˜o disjuntos dois a dois;
2. apenas uma u´nica casa de T na˜o pertence a algum dos triomino´s.
Seja c ∈ T . Mostre que existe uma cobertura de T por triomino´s cuja
casa na˜o coberta e´ exatamente a casa c.
Exemplo 28 (Princ´ıpio do Pombal) Para n = 1, 2, ... temos que
Se n+1 pombos entram num pombal com n casas, ent~ao pelo
menos dois pombos compartilham uma mesma casa.
Exemplo 29 (Combinato´ria) Para n = 1, 2, ... temos que
Se S ⊂ {1, 2, · · · , 2n} e |S| = n + 1 ent~ao existem a, b ∈ S
tais que b e´ mu´ltiplo de a.
4.4 Exerc´ıcios
Para cada um dos exerc´ıcios a seguir, demonstre por induc¸a˜o fraca a validade
da correspondente propriedade enunciada.
Exerc´ıcio 16 Para n = 1, 2, ... temos que
n∑
i=1
i.(i+ 1).(i+ 2) = n.(n+ 1).(n+ 2).(n+ 3)/4
Cap´ıtulo 5
Induc¸a˜o Forte
5.1 O Princ´ıpio
Para o sistema de relac¸o˜es booleanas
x1 = 1
x1 ≤ x2
x1.x2 ≤ x3
...
x1.x2. · · · .xn−1 ≤ xn
...
temos que xn = 1 para n = 1, 2, ....
5.2 Exemplos
Exemplo 30 (Selos Postais) Para cada inteiro n ≥ 12 temos que existem
a e b tais que
n = a.4 + b.5 .
Exemplo 31 Uma barra retangular de chocolate e´ constituida por n qua-
drados de igual dimensa˜o. Vamos quebrar a barra de chocolate, ao longo
das linhas que delimitam os quadrados, ate´ separarmos a barra em seus n
quadrados. Para n = 1,2,3,... temos que o nu´mero necessa´rio de quebras e´
sempre n-1.
25
26 CAPI´TULO 5. INDUC¸A˜O FORTE
Exemplo 32 (Divisa˜o por 3) Para cada natural n considere a sua repre-
sentac¸a˜o decimal dada por
n = dk . . . d0
onde di ∈ {0, 1, 2, . . . , 9} para i = 0, 1, . . . , k, dk 6= 0 e n = ∑ki=0 di.10i.
Assim, temos que
n e´ mu´ltiplo de 3 se e so´ se dk + . . .+ d0 e´ mu´ltiplo de 3.
Exemplo 33 (Teorema Fundamental da Aritme´tica) Para cada inteiro
n ≥ 2 temos que existem k primos p1, p2, · · · , pk tais que
n = p1.p2. · · · .pk .
Cap´ıtulo 6
Induc¸a˜o Estrutural
Ate´ aqui, trabalhamos apenas com treˆs tipos elementares de dados, a saber:
bits com as operac¸o˜es lo´gicas de e, ou e na˜o;
conjuntos com as operac¸o˜es de intersec¸a˜o, unia˜o e complemento; e,
naturais com as operac¸o˜es de soma, subtrac¸a˜o, mutiplicac¸a˜o e divisa˜o.
Agora, vamos criar tipos especiais, mais interessantes para nossas aplicac¸o˜es.
Os novos tipos sa˜o criados a partir de combinac¸o˜es dos tipos elementares.
Dentre eles, examinaremos os seguintes: sequencias, expresso˜es bem forma-
das, a´rvores e grafos.
Com estes tipos vamos ilustrar o uso da induc¸a˜o estrutural.
6.1 Sequencias
Exemplo 34 (Nu´meros Primos) Considere a sequencia de nu´meros na-
turais
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, . . . .
Enfatizemos os nu´meros que so´ tem divisores triviais, isto e´, apenas o
pro´prio nu´mero e 1 sa˜o os seus divisores. Assim, temos
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, . . . .
Eliminando os na˜o enfatizados, obtemos a sequencia de interesse
2, 3, 5, 7, 11, 13, . . . .
27
28 CAPI´TULO 6. INDUC¸A˜O ESTRUTURAL
Esta e´ a sequencia dos nu´meros primos.
Os nu´meros primos tem propriedades muito poderosas, exaustivamente
estudadas por alguns dos mais brilhantes matema´ticos. Algumas delas sa˜o a
base para a elaborac¸a˜o do conhecido Sistema RSA de criptografia por chaves-
pu´blicas.
Na sec¸a˜o 6.3, vamos examinar um caso especial: os nu´meros de Fibonacci.
Este e´ o caso mais simples onde usamos a Induc¸a˜o Estrutural para demonstrar
diversas propriedades dacorrespondente sequencia.
6.2 O Princ´ıpio
6.3 Nu´meros de Fibonacci
Seja R um retaˆngulo com lados de tamanho a e a + 1, onde 1 < a < 2. e´
claro que este retaˆngulo conte´m um quadrado Q de lado a. Se retirarmos Q
de R, sobra um retaˆngulo menor R′. O lado menor de R′ mede 1 e o maior
mede a.
Vamos escolher o valor de a de tal forma que os retaˆngulos R e R′ sejam
semelhantes. Para isto, devemos ter
a+ 1
a
=
a
1
.
Consequentemente,
a+ 1 = a2
a2 − a− 1 = 0.
As ra´ızes dessa equac¸a˜o sa˜o 1+
√
5
2
e 1−
√
5
2
. Como a > 1, segue-se enta˜o
que a = 1+
√
5
2
≈ 1.618.
A raza˜o entre os lados maiores de R e R′ e´ igual a a. Portanto, quando
escolhemos a = 1+
√
5
2
, obtemos a chamada raza˜o a´urea, cujo valor e´ aproxi-
madamente igual a
1.6180339887.
Exerc´ıcio 17 A partir de uma busca na web para a expressa˜o golden ratio,
identifique quatro manifestac¸o˜es naturais e este´ticas apresentadas para a
raza˜o a´urea.
6.3. NU´MEROS DE FIBONACCI 29
Definic¸a˜o 4 A sequencia de nu´meros de Fibonacci e´ definida recursivamente
por {
f0 = 0 f1 = 1 (caso base)
fn = fn−1 + fn−2 para n = 2, 3, · · · (relac¸a˜o estrutural)
Observe as similaridades e diferenc¸as com a definic¸a˜o recursiva dos nu´meros
naturais apresentada abaixo.
Definic¸a˜o 5 A sequencia dos nu´meros naturais e´ definida recursivamente
por {
a0 = 0 (caso base)
an = an−1 + 1 para n = 1, 2, · · · (relac¸a˜o estrutural)
A seguir, enumeramos diversas propriedades dos nu´meros de Fibonacci.
Todas elas podem ser facilmente demonstradas utilizando induc¸a˜o estrutural.
FIBO 1 Para n = 3, 4, · · · temos que
fn ≥ (
√
2)n−1
FIBO 2 Para n = 2, 3, · · · temos que
fn ≥ φn−2
onde φ = 1+
√
5
2
.
FIBO 3 Para n = 2, 3, · · · temos que
n−2∑
i=0
fi = fn − 1
FIBO 4 Para n = 0, 1, · · · temos que
n∑
i=0
f 2i = fn.fn+1
FIBO 5 Para n = 1, 2, · · · temos que
n−1∑
i=0
f2i+1 = f2n
30 CAPI´TULO 6. INDUC¸A˜O ESTRUTURAL
FIBO 6 Para n = 1, 2, · · · temos que
2n∑
i=0
(−1)i.fi = f2n−1 − 1
FIBO 7 Para n = 1, 2, · · · temos que
fn−1.fn+1 − f 2n = (−1)n
FIBO 8 Para n = 1, 2, · · · temos que
2n−1∑
i=0
fi.fi+1 = f
2
2n
FIBO 9 Para n = 0, 1, · · · temos que
fn =
1√
5
[φn − (1− φ)n]
onde φ = 1+
√
5
2
.
6.4 Sequencias de Pareˆnteses
Em expresso˜es aritme´ticas, usamos pareˆnteses para indicar a ordem de pre-
cedeˆncia entre as diversas operac¸o˜es. A expressa˜o
((5 + 7).(4− 1))/(14− (3.4)),
cujo resultado e´ 18, ilustra claramente esse uso dos pareˆnteses. Eliminando
os pareˆnteses, obtemos a expressa˜o
5 + 7.4− 1/14− 3.4,
cujo resultado e´ 293/14, evidentemente diferente de 18.
Usamos tambe´m pareˆnteses para indicar a decomposic¸a˜o de uma frase
nas suas orac¸o˜es. Na maioria dessas aplicac¸o˜es, os pareˆnteses formam uma
estrutura aninhada.
O tamanho de uma sequencia S = s1s2 · · · sk e´ k. Usamos |S| para denotar
o tamanho de S.
6.4. SEQUENCIAS DE PAREˆNTESES 31
Definic¸a˜o 6 (Concatenac¸a˜o) Sejam S = s1s2 · · · sk e T = t1t2 · · · tl duas
sequencias quaisquer de s´ımbolos abre-pareˆnteses e fecha-pareˆnteses. Defini-
mos a concatenac¸a˜o ST de S e T por
ST = s1s2 · · · skt1t2 · · · tl.
Definic¸a˜o 7 Uma Sequencia Bem Formada de Pareˆnteses (SBFP) S e´ de-
finida recursivamente por
S = ( ) (caso base)
S = AB A e B sa˜o SBFP (relac¸a˜o estrutural)
S = (A) A e´ SBFP (relac¸a˜o estrutural)
A seguir, enumeramos diversas propriedades das SBFP. Todas elas podem
ser facilmente demonstradas utilizando induc¸a˜o estrutural.
SBFP 1 Toda sequencia bem formada de pareˆnteses tem como primeiro
s´ımbolo um abre-pareˆnteses.
SBFP 2 Toda sequencia bem formada de pareˆnteses tem como u´ltimo s´ımbolo
um fecha-pareˆnteses.
SBFP 3 Toda sequencia bem formada de pareˆnteses e´ constituida por um
nu´mero par de s´ımbolos.
SBFP 4 Toda sequencia bem formada de pareˆnteses tem o nu´mero total de
abre-pareˆnteses igual ao nu´mero total de fecha-pareˆnteses.
Existe um teste muito simples e eficiente para verificar se uma sequencia
de pareˆnteses e´ ou na˜o e´ uma SBFP. Esse teste esta´ baseado em percorrer a
sequencia mantendo dois contadores: um para o nu´mero acumulado de abre-
pareˆnteses, e outro para o nu´mero acumulado de fecha-pareˆnteses. Para
formalizar este processo vamos definir esses contadores.
Definic¸a˜o 8 (Indicadoras) Seja s um abre-pareˆnteses ou um fecha-pareˆnteses.
Definimos as varia´veis indicadoras Iabre(s) e Ifecha(s) por
Iabre(s) =
{
1 se s e´ um abre pareˆnteses
0 caso contra´rio
e por
Ifecha(s) =
{
1 se s e´ um fecha pareˆnteses
0 caso contra´rio
32 CAPI´TULO 6. INDUC¸A˜O ESTRUTURAL
Definic¸a˜o 9 (Contadores) Seja S = s1s2 · · · sk uma sequencia qualquer de
s´ımbolos abre-pareˆnteses e fecha-pareˆnteses. Para i = 1, · · · , k definimos os
contadores nabre(S, i) e nfecha(S, i) por
nabre(S, i) =
∑i
j=1 Iabre(sj)
nfecha(S, i) =
∑i
j=1 Ifecha(sj).
SBFP 5 Seja S = s1s2 · · · sk uma sequencia qualquer de s´ımbolos abre-
pareˆnteses e fecha-pareˆnteses. Para i = 1, · · · , k, temos que
nabre(S, i) = i− nfecha(S, i).
SBFP 6 Seja S = s1s2 · · · sk uma sequencia qualquer de s´ımbolos abre-
pareˆnteses e fecha-pareˆnteses. Para i = 1, · · · , k, as treˆs afirmac¸o˜es abaixo
sa˜o equivalentes:
(i) nabre(S, i) ≥ nfecha(S, i)
(ii) 2.nabre(S, i) ≥ i
(iii) 2.nfecha(S, i) ≤ i.
SBFP 7 Seja S = XY uma sequencia qualquer de s´ımbolos abre-pareˆnteses
e fecha-pareˆnteses. Para i = 1, · · · , |S|, temos que
nabre(S, i) =
{
nabre(X, i) se i ≤ |X|
nabre(X, |X|) + nabre(Y, i− |X|) se i > |X|.
SBFP 8 Seja S = s1s2 · · · sk uma sequencia bem formada de pareˆnteses.
Neste caso, temos que
nabre(S, k) = nfecha(S, k).
SBFP 9 Seja S = s1s2 · · · sk uma sequencia bem formada de pareˆnteses.
Para i = 1, · · · , k, temos que
nabre(S, i) ≥ nfecha(S, i).
SBFP 10 Seja S = s1s2 · · · sk uma sequencia bem formada de pareˆnteses.
Neste caso, temos que
2.nabre(S, k) = k.
6.4. SEQUENCIAS DE PAREˆNTESES 33
SBFP 11 Seja S = s1s2 · · · sk uma sequencia bem formada de pareˆnteses.
Para i = 1, · · · , k, temos que
2.nabre(S, i) ≥ i.
SBFP 12 (Caracterizac¸a˜o I) Seja S = s1s2 · · · sk uma sequencia qualquer
de s´ımbolos abre-pareˆnteses e fecha-pareˆnteses, com k ≥ 2.
A sequencia S e´ uma SBFP se e somente se
(i) nabre(S, i) ≥ nfecha(S, i) para i = 1, · · · , k
(ii) nabre(S, k) = nfecha(S, k).
A propriedade a seguir permite construir um verificador de SBFP’s tes-
tando apenas o contador de abre-pareˆnteses.
SBFP 13 (Caracterizac¸a˜o II) Seja S = s1s2 · · · sk uma sequencia qual-
quer de s´ımbolos abre-pareˆnteses e fecha-pareˆnteses, com k ≥ 2.
A sequencia S e´ uma SBFP se e somente se
(i) 2.nabre(S, i) ≥ i para i = 1, · · · , k
(ii) 2.nabre(S, k) = k.
A propriedade a seguir permite construir um verificador de SBFP’s tes-
tando apenas o contador de fecha-pareˆnteses.
SBFP 14 (Caracterizac¸a˜o III) Seja S = s1s2 · · · sk uma sequencia qual-
quer de s´ımbolos abre-pareˆnteses e fecha-pareˆnteses, com k ≥ 2.
A sequencia S e´ uma SBFP se e somente se
(i) 2.nfecha(S, i) ≤ i para i = 1, · · · , k
(ii) 2.nfecha(S, k) = k.
Exerc´ıcio 18 Formule um algoritmo que, em apenas uma passada numa
sequencia de pareˆnteses, determine se a mesma e´ ou na˜o e´ uma SBPF.
34 CAPI´TULO 6. INDUC¸A˜O ESTRUTURAL
Cap´ıtulo 7
A´rvores e Florestas Livres
7.1 A´rvores Livres
Definic¸a˜o 10 Uma A´rvore Livre T = (V,A) e´ definida recursivamente por{
T = ({v}, {}) (caso base)
T = (V1 ∪ {v}, A1 ∪ {{v, u}}) (relac¸a˜o estrutural)
onde v /∈ V1, u ∈ V1, e T1 = (V1, A1) e´ uma a´rvore livre.
AL 1 Seja T = (V,A) uma a´rvore livre. Para toda aresta a ∈ A, temos que
(i) a ⊆ V
(ii) |a| = 2 .
AL 2 Seja T = (V,A) uma a´rvore livre com n ve´rtices e m arestas. Neste
caso, temos que
m = n−1.
Definic¸a˜o 11 (Indicadoras) Seja T = (V,A) uma a´rvore livre e W um
conjunto tal que V ⊆ W . Para cada par w ∈ W e a ∈ A definimos a varia´vel
indicadora Ia(w) por
Ia(w) =
{
1 se w ∈ a
0 caso contra´rio
Quando Ia(w) = 1, dizemos que a aresta a e´ incidente no ve´rtice w.
35
36 CAPI´TULO 7. A´RVORES E FLORESTAS LIVRES
AL 3 Seja T = (V,A) uma a´rvore livre. Neste caso, se a ∈ A e w /∈ V
enta˜o Ia(w) = 0.
Definic¸a˜o 12 Seja T = (V,A) uma a´rvore livre. Para todo ve´rtice v ∈ V
definimos o grau(v) por
grau(v) =
∑
a∈A
Ia(v).
E´ fa´cil ver que o grau(v) e´ o nu´mero total de arestas incidentes em v.
AL 4 Seja T1 = (V1, A1) uma a´rvore livre e T = (V1 ∪ {v}, A1 ∪ {{v, u}}),
com v /∈ V1 e u ∈ V1. Neste caso, para todo ve´rtice x ∈ V temos que
grauT (x) = grauT1(x) + I{v,u}(x).
AL 5 Seja T = (V,A) uma a´rvore livre com |V | ≥ 2. Para todo ve´rtice
v ∈ V temos que
grau(v) ≥ 1.
Exerc´ıcio 19 Seja T = (V,A) uma a´rvore livre. Para v ∈ V , formule uma
definic¸a˜o recursiva para o grau(v).
AL 6 (Teorema do Aperto de Ma˜o) Seja T = (V,A) uma a´rvore livre.
Para |A| = m temos que ∑
v∈V
grau(v) = 2.m .
Definic¸a˜o 13 Seja T = (V,A) uma a´rvore livre. Dizemos que um ve´rtice
v ∈ V e´ uma folha se e so´ se
grau(v) ≤ 1.
AL 7 Seja T = (V,A) uma a´rvore livre com |V | ≥ 2. Neste caso, temos que
T tem pelo menos duas folhas.
AL 8 Seja T = (V,A) uma a´rvore livre com |V | ≥ 3. Neste caso, temos que
T tem pelo menos um ve´rtice v ∈ V tal que
grau(v) > 1.
7.2. REPRESENTAC¸A˜O SEQUENCIAL 37
AL 9 Seja T = (V,A) uma a´rvore livre com |V | ≥ 2. Se f ∈ V , {f, w} ∈ A
e grau(f) = 1 enta˜o T ′ = (V −{f}, A−{f, w}) tambe´m e´ uma a´rvore livre.
AL 10 Seja T = (V,A) uma a´rvore livre com |V | ≥ 2. Seja ainda T ′ =
(V − {f}, A− {f, w}) com f ∈ V , {f, w} ∈ A e grauT (f) = 1. Enta˜o
(i) grauT (f) = 1
(ii) grauT (w) = 1 + grauT ′(w)
(iii) grauT (v) = grauT ′(v) v ∈ V − {f, w}
7.2 Representac¸a˜o Sequencial
Definic¸a˜o 14 Seja T = (V,A) uma a´rvore livre com |V | ≥ 2, sendo V um
subconjunto dos naturais. Definimos recursivamente a representac¸a˜o sequen-
cial S(T ) de T por{
S(T ) = (V, �) se |V | = 2 (caso base)
S(T ) = (V,w W ′) se |V | ≥ 3 (relac¸a˜o estrutural)
onde � e´ a sequencia vazia, T ′ = (V − {f}, A − {{f, w}}, S(T ′) = (V −
{f},W ′), f = min{v ∈ V |grau(v) = 1} e {f, w} ∈ A.
Exemplo 35 Considere T = ({1, 2, 3, 4, 5}, {{1, 4}, {2, 4}, {2, 3}, {2, 5}}). Neste
caso, temos que a representac¸a˜o sequencial e´ dada por S(T ) = ({1, 2, 3, 4, 5}, (4 2 2).
AL 11 Seja T = (V,A) uma a´rvore livre com n ve´rtices. Se S(T ) =
(V,w1w2 · · ·wk) e´ a representac¸a˜o sequencial de T enta˜o
k = n− 2.
AL 12 Seja T = (V,A) uma A´rvore livre com n ve´rtices. Se S(T ) =
(V,w1w2 · · ·wn−2) e´ a representac¸a˜o sequencial de T enta˜o, para todo v ∈ V ,
temos que
v e´ folha de T se e so se v 6= wi para i = 1, · · · , n− 2.
AL 13 Seja T = (V,A) uma a´rvore livre com n ve´rtices. Se S(T ) =
(V,w1w2 · · ·wn−2) e´ a representac¸a˜o sequencial de T enta˜o para todo v ∈ V
temos que
grau(v) = 1 +
n−2∑
i=1
Iv(wi),
38 CAPI´TULO 7. A´RVORES E FLORESTAS LIVRES
onde
Iv(w) =
{
1 se w = v
0 caso contra´rio.
AL 14 Seja V um conjunto com n nu´meros naturais. Seja W = w1w2 · · ·wn−2
uma sequencia tal que wi ∈ V para i = 1 · · ·n− 2. Neste caso, existe exata-
mente uma u´nica a´rvore livre T = (V,A) tal que
S(T ) = (V,W ).
AL 15 (Cayley) Seja V um conjunto com n elementos. Existem exata-
mente nn−2 a´rvores livres cujo conjunto de ve´rtices e´ V .
7.3 Florestas Livres
Definic¸a˜o 15 Uma Floresta Livre F = (V,A) e´ definida recursivamente por
F = ({v}, {}) (caso base)
F = (V1 ∪ {v}, A1) (relac¸a˜o estrutural)
F = (V1 ∪ {v}, A1 ∪ {{v, u}}) (relac¸a˜o estrutural)
onde v /∈ V1, u ∈ V1, e F1 = (V1, A1) e´ uma floresta livre.
FL 1 Seja F = (V,A) uma floresta livre com n ve´rtices e m arestas. Neste
caso, existem k a´rvores livres T1, · · · , Tk tais que
(i) Ti = (Vi, Ai) i = 1, · · · , k
(ii) V = ∪ki=1Vi
(iii) A = ∪ki=1Ai
(iv) Vi ∩ Vj = ∅ 1 ≤ i < j ≤ k
Neste caso, dizemos que as k a´rvores livres compo˜em F .
FL 2 Seja F = (V,A) uma floresta livre com n ve´rtices e m arestas. Neste
caso, temos que
m = n− k
onde k e´ o nu´mero total de a´rvores livres que compo˜em F .
Cap´ıtulo 8
A´rvores Bina´rias
As a´rvores bina´rias mais usadas na computac¸a˜o sa˜o as posicionais. Numa
a´rvore posicional, cada ve´rtice pode ter um filho a esquerda e outro a direita.
Nas a´rvores bina´rias na˜o posicionais, cada ve´rtice pode ter ate´ dois filhos,
sendo irrelevante a noc¸a˜o de posic¸a˜o desses filhos.
Neste cap´ıtulo, apresentamos inicialmente as a´rvores bina´rias na˜o posi-
cionais, aqui denominadas resumidamente de a´rvores bina´rias. Dentre elas,
destacamos diferentes tipos de a´rvores bina´rias: estendidas, estritas, cheias,
balanceadas por altura e de Fibonacci.
Na sec¸a˜o 8.6, apresentamos enta˜o as a´rvores bina´rias posicionais.
8.1 A´rvores Bina´rias Estendidas
Definic¸a˜o 16 Uma a´rvore Bina´ria Estendida T = (V,A) de ra´ız r e´ definida
recursivamente por
T = ({r}, {}) (caso base)
T = ({r} ∪ V1, {(r, r1)} ∪ A1) (relac¸a˜o estrutural)
T = ({r} ∪ V1 ∪ V2, {(r, r1), (r, r2)} ∪ A1 ∪ A2) (relac¸a˜o estrutural)
onde T1 = (V1, A1) e T2 = (V2, A2) sa˜o a´rvores bina´rias estendidas de ra´ızes
r1 e r2 respectivamente, V1 ∩ V2 = ∅ e r /∈ V1 ∪ V2.
As a´rvores T1 e T2 sa˜o denominadas de componentes de T .
Para uma a´rvore bina´ria estendida T , definimos adicionalmente o seu
nu´mero total de ve´rtices n(T ) e o seu nu´mero total de arestas m(T ) por
n(T ) = |V | m(T ) = |A|.
39
40 CAPI´TULO 8. A´RVORES BINA´RIAS
A sua altura h(T ) e´ definida recursivamente por
h(({r}, {})) = 0 (caso base)
h(T ) = 1 + h(T1) (T com uma componente)
h(T ) = 1 +max{h(T1), h(T2)} (T com duas componentes)
Exerc´ıcio 20 Formule as definic¸o˜es recursivas de n(T ) e m(T ).
AB 1 Seja T uma a´rvore bina´ria estendida com n(T ) ve´rtices e m(T ) ares-
tas. Neste caso,
m(T ) = n(T )− 1
AB 2 Seja T uma a´rvore bina´ria com n(T ) no´s e de altura h(T ). Neste
caso,
n(T ) ≤ 2h(T )+1 − 1
Definic¸a˜o 17 (Indicadoras) Seja T = (V,A) uma a´rvore bina´ria esten-
dida. Para cada v ∈ V e a ∈ A definimos as varia´veis indicadoras I ina (v) e
Iouta (v) por
I ina (v) =
{
1 se a = (w, v)
0 caso contra´rio
e
Iouta (v) =
{
1 se a = (v, w)
0 caso contra´rio
Quando I ina (v) = 1, dizemos que a aresta a entra no ve´rtice v. Analoga-
mente, quando Iouta (v) = 1, dizemos que a aresta a sai no ve´rtice v.
Definic¸a˜o 18 Seja T = (V,A) uma a´rvore bina´ria estendida. Para todo
ve´rtice v ∈ V definimos grauin(v) e grauout(v) por
grauinT (v) =
∑
a∈A I ina (v)
grauoutT (v) =
∑
a∈A Iouta (v).
AB 3 Seja T = (V,A) uma a´rvore bina´ria estendida. Neste caso, a ra´ız r e´
o u´nico ve´rtice v ∈ V tal que
grauinT (v) = 0.
8.2. A´RVORES ESTRITAMENTE BINA´RIAS 41
AB 4 Seja T = (V,A) uma a´rvore bina´ria estendida de ra´ız r. Neste caso,
para todo ve´rtice v ∈ V − {r} temos que
grauinT (v) = 1.
AB 5 Seja T = (V,A) uma a´rvore bina´ria estendida. Neste caso, para todo
ve´rtice v ∈ V − {r} temos que
grauoutT (v) = grau
out
T1
(v) + grauoutT2 (v).
AB 6 Seja T = (V,A) uma a´rvore bina´ria estendida. Neste caso, para todo
ve´rtice v ∈ V temos que
grauoutT (v) ≤ 2.
Definic¸a˜o 19 Seja T = (V,A) uma a´rvore bina´ria estendida. Dizemos que
v ∈ V e´ uma folha de T se e so´ se
grauoutT (v) = 0.
Definic¸a˜o 20 Seja T = (V,A) uma a´rvore bina´ria estendida. Dizemos que
v ∈ V e´ um ve´rtice interno de T se e so´ se
grauoutT (v) > 0.
8.2 A´rvores Estritamente Bina´rias
Definic¸a˜o 21 Uma a´rvore Estritamente Bina´ria T = (V,A) de ra´ız r e´
definida recursivamente por{
T = ({r}, {}) (caso base)
T = ({r} ∪ V1 ∪ V2, {(r, r1), (r, r2)} ∪ A1 ∪ A2) (relac¸a˜oestrutural)
onde T1 = (V1, A1) e T2 = (V2, A2) sa˜o a´rvores estritamente bina´rias de
ra´ızes r1 e r2 respectivamente, V1 ∩ V2 = ∅, e r /∈ V1 ∪ V2.
AB 7 Toda a´rvore estritamente bina´ria tambe´m e´ uma a´rvore bina´ria es-
tendida.
AB 8 O nu´mero total de ve´rtices de uma a´rvore estritamente bina´ria e´ sem-
pre ı´mpar.
42 CAPI´TULO 8. A´RVORES BINA´RIAS
AB 9 Seja T = (V,A) uma a´rvore estritamente bina´ria. Neste caso, para
todo ve´rtice v ∈ V temos que
grauoutT (v) ∈ {0, 2}.
AB 10 Numa a´rvore estritamente bina´ria com nf folhas e ni ve´rtices inter-
nos, temos que
ni = nf − 1.
8.3 A´rvores Bina´rias Cheias
Definic¸a˜o 22 Uma a´rvore Bina´ria Cheia T = (V,A) de ra´ız r e´ definida
recursivamente por{
T = ({r}, {}) (caso base)
T = ({r} ∪ V1 ∪ V2, {(r, r1), (r, r2)} ∪ A1 ∪ A2) (relac¸a˜o estrutural)
onde T1 = (V1, A1) e T2 = (V2, A2) sa˜o a´rvores bina´rias cheias de ra´ızes r1 e
r2 respectivamente, V1 ∩ V2 = ∅, r /∈ V1 ∪ V2 e, ale´m disso,
n(T1) = n(T2).
ABC 1 Seja T uma a´rvore bina´ria cheia de ra´ız r, com suba´rvores T1 e T2,
n(T ) ve´rtices, nF (T ) folhas e altura h(T ). Neste caso, temos que
(i) h(T1) = h(T2) para T = (r, T1, T2)
(ii) n(T ) = 2h(T )+1 − 1
(iii) nF (T ) = 2
h(T )
8.4 A´rvores Bina´rias Balanceadas por Altura
Definic¸a˜o 23 Uma a´rvore Bina´ria T Balanceada por Altura com ra´ız r e´
definida recursivamente por
T = ({r}, {}) (caso base)
T = ({r, f}, {(r, f)}) (caso base)
T = ({r} ∪ V1 ∪ V2, {(r, r1), (r, r2)} ∪ A1 ∪ A2) (relac¸a˜o estrutural)
8.5. A´RVORES DE FIBONACCI 43
onde T1 = (V1, A1) e T2 = (V2, A2) sa˜o a´rvores bina´rias balanceadas por
altura de ra´ızes r1 e r2 respectivamente, V1 ∩ V2 = ∅, r /∈ V1 ∪ V2 e, ale´m
disso,
|h(T1)− h(T2)| ≤ 1.
ABBA 1 Seja T uma a´rvore bina´ria balanceada por altura com n(T ) ve´rtices
e altura h(T ). Neste caso, temos que
n(T ) ≥ fh(T )+3 − 1.
onde fi e´ o i−e´simo nu´mero de Fibonacci.
ABBA 2 Seja T uma a´rvore bina´ria balanceada por altura com n(T ) ve´rtices
e altura h(T ). Neste caso, temos que
n(T ) ≥ φh(T )+1 − 1
onde φ = 1+
√
5
2
.
ABBA 3 Seja T uma a´rvore bina´ria balanceada por altura com n(T ) ve´rtices
e altura h(T ). Neste caso, temos que
h(T ) < C. lg (n(T ) + 1)
onde C = 1
lg(φ)
.
8.5 A´rvores de Fibonacci
Definic¸a˜o 24 Uma a´rvore de Fibonacci T com ra´ız r e conjunto de ve´rtices
V e´ definida recursivamente por
T = ({r}, {}) (caso base)
T = ({r, f}, {(r, f)}) (caso base)
T = ({r} ∪ V1 ∪ V2, {(r, r1), (r, r2)} ∪ A1 ∪ A2) (relac¸a˜o estrutural)
onde T1 = (V1, A1) e T2 = (V2, A2) sa˜o a´rvores bina´rias balanceadas por
altura de ra´ızes r1 e r2 respectivamente, V1 ∩ V2 = ∅, r /∈ V1 ∪ V2 e, ale´m
disso,
|h(T1)− h(T2)| = 1.
AF 1 Seja T uma a´rvore de Fibonacci com n(T ) ve´rtices e altura h(T ).
Neste caso, temos que
n(T ) = fh(T )+3 − 1.
onde fi e´ o i−e´simo nu´mero de Fibonacci.
44 CAPI´TULO 8. A´RVORES BINA´RIAS
8.6 A´rvores Bina´rias Posicionais
Numa a´rvore bina´ria na˜o posicional, um arco que vai do ve´rtice pai para o
ve´rtice filho e´ identificado por
(pai, filho).
Numa a´rvore bina´ria posicional, um arco que vai do ve´rtice pai para o ve´rtice
filho pode ser esquerdo ou direito. Assim, esse arco e´ representado por
(pai, filho,0)
ou por
(pai, filho,1)
onde 0 indica esquerdo e 1 indica direito.
Definic¸a˜o 25 Uma a´rvore Posicional Bina´ria Estendida T = (V,A) de ra´ız
r e´ definida recursivamente por
T = ({r}, {}) (caso base)
T = ({r} ∪ V1, {(r, r1,0)} ∪ A1) (relac¸a˜o estrutural)
T = ({r} ∪ V2, {(r, r2,1)} ∪ A2) (relac¸a˜o estrutural)
T = ({r} ∪ V1 ∪ V2, {(r, r1,0), (r, r2,1)} ∪ A1 ∪ A2) (relac¸a˜o estrutural)
onde T1 = (V1, A1) e T2 = (V2, A2) sa˜o a´rvores posicionais bina´rias estendi-
das de ra´ızes r1 e r2 respectivamente, V1 ∩ V2 = ∅, e r /∈ V1 ∪ V2.
A a´rvore T1 e´ a suba´rvore a esquerda de r, enquanto que a a´rvore T2 e´ a
suba´rvore a direita de r.
Definic¸a˜o 26 Uma a´rvore Posicional Estritamente Bina´ria T = (V,A) de
ra´ız r e´ definida recursivamente por{
T = ({r}, {}) (caso base)
T = ({r} ∪ V1 ∪ V2, {(r, r1,0), (r, r2,1)} ∪ A1 ∪ A2) (relac¸a˜o estrutural)
onde T1 = (V1, A1) e T2 = (V2, A2) sa˜o a´rvores posicionais estritamente
bina´rias de ra´ızes r1 e r2 respectivamente, V1 ∩ V2 = ∅, e r /∈ V1 ∪ V2.
Exerc´ıcio 21 Para as a´rvores posicionais, formule propriedades similares as
das a´rvores na˜o posicionais. Ale´m disso, demonstre que essas propriedades
sa˜o verdadeiras.
Cap´ıtulo 9
Florestas de Unia˜o e Busca
Definic¸a˜o 27 Seja S um conjunto finito. Uma (FUB) Floresta de Unia˜o e
Busca F = (V,A) em S e´ definida recursivamente por{
F = ({(s, 0, 1)|s ∈ S}, {}), (caso base)
F = (V1 − {(s2, h2, l2)} ∪ {(s2, h′, l′)}, A1 ∪ {(s1, s2)}) (relac¸a˜o estrutural)
onde F1 = (V1, A1) e´ uma FUB, com
(i) (s1, h1, l1), (s2, h2, l2) ∈ V1 s1 6= s2 h1 ≤ h2
(ii) grauoutF1 (s1) = 0 grau
out
F1
(s2) = 0
(iii) l′ = l1 + l2 h′ = h2 + Ih1(h2)
Se (s, h, l) ∈ V dizemos que este ve´rtice e´ rotulado por s, tem altura h e
l descendentes.
Definic¸a˜o 28 (Indicadoras) Seja F = (V,A) uma FUB em S. Para cada
v ∈ S e a ∈ A definimos as varia´veis indicadoras I ina (v) e Iouta (v) por
I ina (v) =
{
1 se a = (w, v)
0 caso contra´rio
e
Iouta (v) =
{
1 se a = (v, w)
0 caso contra´rio
Quando I ina (v) = 1, dizemos que a aresta a entra no ve´rtice v. Analoga-
mente, quando Iouta (v) = 1, dizemos que a aresta a sai no ve´rtice v.
45
46 CAPI´TULO 9. FLORESTAS DE UNIA˜O E BUSCA
Definic¸a˜o 29 Seja F = (V,A) uma FUB em S. Para todo ve´rtice (s, h, l) ∈
V definimos grauoutF (s) por
grauoutF (s) =
∑
a∈A
Iouta (v).
FUB 1 Seja F = (V,A) uma FUB sobre o conjunto S. Sejam (s, h, l), (s, h∗, l∗) ∈
V . Neste caso, temos que
h = h∗ e l = l∗ .
FUB 2 Seja F = (V,A) uma FUB sobre o conjunto S. Neste caso, temos
que
|V | = |S| .
FUB 3 Seja F = (V,A) uma FUB. Neste caso, temos que
grauoutF (s) ∈ {0, 1}
para todo (s, h, l) ∈ V .
Definic¸a˜o 30 (Representantes) Seja F = (V,A) uma FUB sobre o con-
junto S. Dizemos que s ∈ S e´ um representante em F se e so´ se
grauoutF (s) = 0 .
Denotamos por R o conjunto constituido pelos representantes em F , isto e´,
R = {s ∈ S | grauoutF (s) = 0} .
FUB 4 Seja F = (V,A) uma FUB sobre S, com |V | = n e cujo conjunto de
representantes e´. Neste caso, temos que∑
s∈R, (s,h,l)∈V
l = n .
FUB 5 Seja F = (V,A) uma FUB, com |V | = n. Neste caso, temos que
n ≥ l
para todo (s, h, l) ∈ V .
47
FUB 6 Seja F = (V,A) uma FUB. Neste caso, temos que
l ≥ 2h
para todo (s, h, l) ∈ V .
FUB 7 Seja F = (V,A) uma FUB. Neste caso, temos que
h ≤ lg(n)
para todo (s, h, l) ∈ V .
48 CAPI´TULO 9. FLORESTAS DE UNIA˜O E BUSCA
Cap´ıtulo 10
O Algoritmo de Euclides
10.1 Ma´ximo Divisor Comum
Definic¸a˜o 31 Sejam a e b dois nu´meros naturais. O ma´ximo divisor comum
de a e b e´ dado por
mdc(a, b) = max {d ∈ N | d\a, d\b} .
MDC 1 Seja a um inteiro positivo. Enta˜o mdc(a, 0) = a.
MDC 2 Sejam a e b dois inteiros positivos, com b 6= 0. Enta˜o mdc(a, b) =
mdc(b, a mod(b)).
10.2 O Algoritmo
O Algoritmo 1, apresentado a seguir, determina o mdc(a, b). Observe que o
esforc¸o total deste algoritmo e´ O(min(a, b)) sempre.
Ja´ o Algoritmo 2, resolve o mesmo problema com esforc¸o totalO(min(a, b))
no pior caso.
Finalmente, apresentamos o Algoritmo 3, que tambe´m determina omdc(a, b).
Posteriormente, vamos demonstrar que o esforc¸o total deste terceiro algo-
ritmo e´ O(log(min(a, b))) no pior caso.
49
50 CAPI´TULO 10. O ALGORITMO DE EUCLIDES
Algorithm 1 Forc¸a Bruta.
maiorCandidato ← min(a,b)
for candidato = 1 to maiorCandidato do
if (candidato \ a and candidato \ b) then
mdc ← candidato
end if
end for
return mdc
Algorithm 2 Forc¸a Bruta melhorado.
maiorCandidato ← min(a,b)
for candidato = maiorCandidatodownto 1 do
if (candidato \ a and candidato \ b) then
return candidato
end if
end for
Algorithm 3 Algoritmo de Euclides.
primeiro ← max(a,b)
segundo ← min(a,b)
while segundo > 0 do
resto ← primeiro mod segundo
primeiro ← segundo
segundo ← resto
end while
return primeiro
10.3. CORRETUDE 51
10.3 Corretude
Na˜o e´ o´bvio que o Algoritmo de Euclides calcula corretamente o valor do
mdc. Vamos usar da Induc¸a˜o Estrutural para provar este fato. Para isto,
considere a sequeˆncia
resto1, . . . , reston
de valores atribuidos a varia´vel resto durante a execuc¸a˜o do algoritmo. Ob-
serve que restoi e´ o resto da i-e´sima divisa˜o efetuada pelo algoritmo.
Por exemplo, ao calcular o mdc(783, 534) obtemos a sequeˆncia de restos
249, 36, 33, 3, 0
concluindo que mdc(783, 534) = 3.
Para i = 3, 4, . . . , n temos que
restoi = primeiroi mod segundoi.
e
segundoi+1 = restoi primeiroi+1 = segundoi.
donde,
primeiroi = segundoi−1 = restoi−2.
Portanto, temos a seguinte equac¸a˜o recursiva
restoi = restoi−2 mod restoi−1
para i = 3, 4, . . . , n.
E´ fa´cil ver que, definindo resto0 = min(a, b) e resto−1 = max(a, b), obte-
mos a sequeˆncia expandida
resto−1, resto0, resto1, . . . , reston
que satisfaz a equac¸a˜o recursiva
restoi = restoi−2 mod restoi−1
para i = 1, 2, . . . , n.
No ca´lculo do mdc(783, 534) a sequeˆncia expandida de restos e´
783, 534, 249, 36, 33, 3, 0.
Seja n o nu´mero total de diviso˜es efetuadas pelo Algoritmo de Euclides.
As seguintes propriedades demonstram a corretude deste algoritmo.
52 CAPI´TULO 10. O ALGORITMO DE EUCLIDES
EUC 1 Se n = 0 enta˜o mdc(a, b) = max(a, b).
EUC 2 Se n > 0 enta˜o, para i = 0, 1, . . . , n, temos que
(i) restoi−1 > restoi;
(ii) reston = 0;
(iii) mdc(a, b) = mdc(restoi−1, restoi);
(iv) mdc(a, b) = reston−1.
10.4 Eficieˆncia
Seja n o nu´mero total de diviso˜es efetuadas pelo Algoritmo de Euclides. A
sequeˆncia de valores de restos gerada no ca´lculo do mdc(a, b) pelo Algoritmo
de Euclides obedece as seguintes equac¸o˜es
resto−1 = max(a, b) (caso base)
resto0 = min(a, b) (caso base)
restoi = restoi−2 mod restoi−1 (relac¸a˜o estrutural)
onde i = 1, 2, · · · , n.
As seguintes propriedades estabelecem a eficieˆncia deste algoritmo.
EUC 3 Se n > 0 enta˜o, para i = 0, 1, . . . , n− 2, temos que
(i) reston = 0;
(i) reston−1 ≥ 1 reston−2 ≥ 2;
(ii) restoi ≥ restoi+1 + restoi+2;
(iii) restoi ≥ 2.restoi+2;
(iii) restoi ≥ (
√
2)n−1−i;
(iv) resto0 ≥ (
√
2)n−1.
EUC 4 Seja n o nu´mero total de diviso˜es efetuadas pelo Algoritmo de Eu-
clides no ca´lculo do mdc(a, b). Temos que
n ≤ 1 + 2. lg2(min(a, b)).
Cap´ıtulo 11
O Teorema de Stone
Neste cap´ıtulo, mostramos que toda a´lgebra booleana finita (B, +, .,−) e´
isomorfa a uma a´lgebra de conjuntos. Este e´ o Teorema de Stone.
Para |B| = 1, a demonstrac¸a˜o e´ trivial. Apresentamos uma demonstrac¸a˜o
por induc¸a˜o estrutural para o caso em que |B| ≥ 2.
Uma consequeˆncia imediata deste teorema e´ que para toda a´lgebra boo-
leana finita (B, +, .,−) existe um nu´mero natural k tal que |B| = 2k.
11.1 A´tomos
Definic¸a˜o 32 Seja (B, +, ., −) uma a´lgebra booleana. Dizemos que um ele-
mento a ∈ B e´ um a´tomo se e so´ se para todo x ≤ a temos que x ∈ {0, a}.
Diversas propriedades da ordenac¸a˜o booleana esta˜o fortemente associadas
a noc¸a˜o de a´tomo. A seguir, apresentamos algumas destas.
OBL 14 a ≤ b e a ≤ c e b.c = 0 enta˜o a = 0.
OBL 15 a ≤ b.c enta˜o a ≤ b+ c.
OBL 16 a ≤ b enta˜o b = a+ b.a.
OBL 17 a+ b = a.b+ b.a+ a.b.
OBL 18 (a.b).(a.b) = (a.b).(b.a) = (a.b).(b.a).
OBL 19 c = a+ b e a, b /∈ {0, c} enta˜o a 6= b.
ATM 1 Sejam a1 e a2 dois a´tomos distintos de uma a´lgebra booleana (B, +, .,
−).
Neste caso, temos que a1.a2 = 0.
53
54 CAPI´TULO 11. O TEOREMA DE STONE
11.2 Decomposic¸a˜o Estrutural
Definic¸a˜o 33 Dizemos que b < a se e so´ se b ≤ a e b 6= a.
STN 1 Se b na˜o e´ um a´tomo, enta˜o existe c ∈ B tal que
0 < c < b.
STN 2 Se b ∈ B na˜o e´ um a´tomo, enta˜o existem x, y ∈ B tais que
(i) x, y 6= 0
(ii) x.y = 0
(iii) x, y < b
(iv) b = x+ y.
STN 3 Para todo b ∈ B existem um inteiro k e a1, · · · , ak ∈ B tais que
(i) ai 6= 0
(ii) ai.aj = 0 para i 6= j
(iii) ai e´ a´tomo
(iv) b = a1 + · · ·+ ak.
para i, j = 1, · · · , k. Ale´m disso, essa decomposic¸a˜o e´ u´nica.
STN 4 Seja b = a1 + · · ·+ak a decomposic¸a˜o de b em a´tomos. Seja tambe´m
a um a´tomo tal que a ≤ b. Neste caso, temos que existe 1 ≤ i ≤ k tal que
a = ai.
STN 5 Sejam b =
∑k
i=1 ai e b
′ =
∑k′
i=1 a
′
i as respectivas decomposic¸o˜es de b
e b′ em a´tomos. Sejam s = b+ b′ e p = b.b′. Neste caso, temos que
(i) s =
∑j
i=1 xi
(ii) p =
∑l
i=1 yi
onde {x1, · · · , xj} = {a1, · · · , ak}∪{a′1, · · · , a′k′} e {y1, · · · , yl} = {a1, · · · , ak}∩
{a′1, · · · , a′k′}.
Cap´ıtulo 12
Grafos
12.1 Conceitos Ba´sicos
Os elementos atoˆmicos empregados na construc¸a˜o de grafos sa˜o os ve´rtices e
as arestas.
Primeiramente, vamos definir esses elementos. A partir deles, vamos
enta˜o construir os grafos.
12.1.1 Ve´rtices
Um conjunto na˜o vazio V com n ve´rtices e´ simplesmente um conjunto com
n elementos distintos, isto e´,
V = {v1, · · · , vn}
onde n ≥ 1.
12.1.2 Arestas
Um conjunto A com m arestas e´ simplesmente um conjunto com m elementos
distintos, isto e´,
A = {a1, · · · , am}
onde m ≥ 0.
55
56 CAPI´TULO 12. GRAFOS
12.1.3 Incideˆncia
A cada aresta a ∈ A esta˜o associados dois ve´rtices u, v ∈ V nos quais dizemos
que a aresta a incide. Desta forma, fazemos as arestas incidirem nos ve´rtices.
Definimos dois tipos diferentes de incideˆncia: a dirigida e a na˜o dirigida.
Na incideˆncia dirigida, a aresta a e´ associada a um par ordenado (u, v) ∈
V × V . Neste caso, a e´ dita dirigida de u para v.
Na incideˆncia na˜o dirigida, a aresta a e´ associada a um conjunto {u, v}.
Neste caso, a e´ dita na˜o dirigida entre u e v.
Formalmente, a incideˆncia dirigida e´ uma func¸a˜o f : A→ V × V .
Analogamente, a incideˆncia na˜o dirigida e´ uma func¸a˜o f : A→ V (2), onde
V (2) = {{u, v}|u, v ∈ V }.
Observe que para u ∈ V temos que os elementos do tipo {u} ∈ V (2), pois
{u} = {u, u}.
12.2 Grafos e Subgrafos
Definic¸a˜o 34 (Grafo) Um grafo G e´ uma estrutura composta de treˆs ele-
mentos, isto e´,
G = (V,A, f)
onde V e´ um conjunto de ve´rtices, A e´ um conjunto de arestas e f e´ uma
func¸a˜o de incideˆncia.
Quando as arestas deG esta˜o dirigidas, dizemos queG e´ um grafo dirigido.
Se f(a) = (u, u), dizemos que a aresta a e´ um lacete dirigido.
Quando as arestas de G esta˜o na˜o dirigidas,, dizemos que G e´ um grafo
na˜o dirigido. Se f(a) = {u}, dizemos que a aresta a e´ um lacete na˜o dirigido.
Duas arestas distintas a1 e a2 de um grafo G sa˜o ditas paralelas quando
f(a1) = f(a2).
Exemplo 36 Seja G = (V,A, f), com V = {1, 2, 3, 4}, A = {1, 2, 3, 4, 5, 6, 7}
e f = {(1, {4, 3}), (2, {1, 4}), (3, {2, 4}), (4, {1, 2}), (5, {1, 2}), (6, {3, 2}), (7, {2, 3})}.
O grafo G do exemplo 36 tem cinco ve´rtices e sete arestas na˜o dirigidas.
Observe que as arestas 3, 4, 5, 6 e 7 sa˜o incidentes no ve´rtice 2. Nesse grafo,
as arestas 6 e 7 sa˜o paralelas entre si, bem como as arestas 4 e 5.
12.2. GRAFOS E SUBGRAFOS 57
Os grafos sa˜o classificados segundo va´rios crite´rios, como por exemplo os
seguintes: o direcionamento ou na˜o das arestas, a presenc¸a ou na˜o de lacetes,
e a presenc¸a ou na˜o de arestas paralelas.
Grafos na˜o dirigidos, sem lacetes nem arestas paralelas, sa˜o denominados
Grafos Simples.
Grafos com arestas na˜o dirigidas, sem lacetes mas com arestas paralelas,
sa˜o denominados Multigrafos.
Grafos com arestas na˜o dirigidas, com lacetes e com arestas paralelas, sa˜o
denominados Pseudografos.
Grafos com arestas dirigidas, com lacetes e sem arestas paralelas, sa˜o
denominadosGrafos Dirigidos.
Grafos com arestas dirigidas, com lacetes e com arestas paralelas, sa˜o
denominados Multigrafos Dirigidos.
Definic¸a˜o 35 Seja G = (V,A, f) um grafo na˜o dirigido. Dizemos que o
grafo H = (V ′, A′, f ′) e´ um subgrafo de G se e somente se
(i) V ′ ⊆ V ;
(ii) A′ ⊆ A;
(iii) a ∈ A′ enta˜o f ′(a) = f(a) ⊆ V ′.
Um subgrafo de um grafo dirigido e´ definido de maneira ana´loga. Quando
H e´ um subgrafo de G, denotamos por H ≤ G. Adicionalmente, se H ≤ G
e H 6= G, denotamos por H < G.
Definic¸a˜o 36 Seja α uma famı´lia de grafos. Seja G um grafo. Dizemos que
H e´ um componente-α de G se e somente se
(i) H ≤ G;
(ii) H ∈ α;
(iii) na˜o existe H ′ ∈ α tal que H < H ′ ≤ G.
58 CAPI´TULO 12. GRAFOS
Cap´ıtulo 13
Grafos Simples
13.1 Representac¸a˜o
Seja G = (V,A, f) um grafo simples. Para a ∈ A e f(a) = {u, v} temos
que na˜o existe outra a′ ∈ A com f(a′) = {u, v}. Portanto, o par de ve´rtices
{u, v} identifica a aresta A. Assim, podemos representar G por
G = (V, f(A))
onde f(A) = {{u, v}|∃a ∈ A, f(a) = {u, v}}.
Observe que f(A) ⊆ V (2).
Identificando A com f(A), obtemos a seguinte definic¸a˜o simplificada para
os Grafos Simples.
Definic¸a˜o 37 Dizemos que G = (V,A) e´ um grafo simples se e somente se
(i) A ⊆ V (2);
(ii) para todo v ∈ V temos que {v} /∈ A,
onde V (2) = {{u, v}|u, v ∈ V }.
SIM 1 Seja G = (V,A) um grafo simples. Para |V | = n e |A| = m temos
que
m ≤ n.(n− 1)
2
.
SIM 2 Seja T = (V,A) uma a´rvore livre. Neste caso, T e´ tambe´m um grafo
simples.
59
60 CAPI´TULO 13. GRAFOS SIMPLES
Alternativamente, podemos definir um grafo simples recursivamente.
Definic¸a˜o 38 Um Grafo Simples G = (V,A) e´ definido recursivamente por
T = ({v}, {}) (caso base)
T = (V1 ∪ {v}, A1) (relac¸a˜o estrutural)
T = (V1, A1 ∪ {{u,w}}) (relac¸a˜o estrutural)
onde v /∈ V1, u,w ∈ V1, {u,w} /∈ A1, e G1 = (V1, A1) e´ um grafo simples.
Definic¸a˜o 39 (Indicadoras) Seja G = (V,A) um grafo simples. Para v ∈
V e a ∈ A, definimos a varia´vel indicadora Ia(v) por
Ia(v) =
{
1 se v ∈ a
0 se v /∈ a
Definic¸a˜o 40 Seja G = (V,A) um grafo simples. Para todo ve´rtice v ∈ V
definimos o grau(v) por
grau(v) =
∑
a∈A
Ia(v)
SIM 3 (Teorema do Aperto de Ma˜o) Seja G = (V,A) um grafo sim-
ples. Para |A| = m temos que∑
v∈V
grau(v) = 2.m .
SIM 4 Seja G = (V,A) um grafo simples, com |V | = n e |A| = m. Se
grau(v) = 2 para todo v ∈ V enta˜o temos que m = n.
Exerc´ıcio 22 Seja T o nu´mero total de ve´rtices de grau ı´mpar em G. Mostre
que T e´ par.
Exerc´ıcio 23 Generalize o Teorema do Aperto de Ma˜o para o caso em que
G e´ um multigrafo.
Definic¸a˜o 41 Se grau(v) = 0 dizemos que v e´ um ve´rtice isolado de G.
Definic¸a˜o 42 Se grau(v) = 1 dizemos que v e´ uma folha de G.
A seguir, relembramos uma propriedade relativa a folhas em uma A´rvore
Livre.
SIM 5 Seja T = (V,A) uma a´rvore livre com n ≥ 2, onde n = |V |. Neste
caso, temos que T tem pelo menos duas folhas.
13.2. GRAFOS DERIVADOS 61
13.2 Grafos Derivados
Definic¸a˜o 43 Seja G = (V,A) um grafo simples. Seja tambe´m A¯ = {(u, v)|(u, v) /∈
A}. Definimos o grafo complemento Gc por
Gc = (V, A¯)
CPL 1 (Gc)c = G.
13.3 Passeios, Trilhas e Caminhos
Seja G = (V,A) um grafo simples.
Definic¸a˜o 44 (Passeio) Dizemos que p e´ um passeio de tamanho k em G
se somente se
(i) p = (v0, v1, · · · , vk)
(ii) vi ∈ V i = 0, · · · , k
(iii) {vi−1, vi} ∈ A i = 1, · · · , k.
onde k ≥ 0.
Neste caso, dizemos que p vai de v0 a vk. Ale´m disso, os ve´rtices v0 e vk
sa˜o denominados terminais do passeio p. O ve´rtice v0 e´ a origem do passeio,
enquanto o ve´rtice vk e´ o destino do passeio. Usamos ‖p‖ para denotar o
tamanho de p.
Para u ∈ V , temos que (u) e´ um passeio de tamanho 0 em G de u a u.
PSS 1 Se p = (v0, v1, · · · , vk) e´ um passeio em G, enta˜o p′ = (vk, vk−1, · · · , v0)
tambe´m e´ um passeio em G.
Observe que p vai de v0 a vk, enquanto p
′ vai de vk a v0.
PSS 2 Se p1 = (v0, v1, · · · , vk) e p2 = (u0, u1, · · · , ul) sa˜o dois passeios em
G e vk = u0, enta˜o p3 = (v0, v1, · · · , vk, u1, · · · , ul) tambe´m e´ um passeio em
G e ‖p3‖ = k + l.
Definic¸a˜o 45 (Trilha) Dizemos que um passeio p = (v0, v1, · · · , vk) e´ uma
trilha em G se somente se {vi−1, vi} 6= {vj−1, vj} para 1 ≤ i < j ≤ k.
62 CAPI´TULO 13. GRAFOS SIMPLES
Definic¸a˜o 46 (Caminho) Dizemos que um passeio p = (v0, v1, · · · , vk) e´
um caminho em G se somente se
(i) vi 6= vj 1 ≤ i < j < k
(ii) vi 6= vj 1 < i < j ≤ k
CAM 1 Todo caminho de tamanho ≥ 3 em G e´ tambe´m uma trilha em G.
CAM 2 Seja p = (v0, · · · , vk) um caminho em G, com k ≥ 3. Neste caso,
para i = 1, · · · , k − 1 temos que
grau(vi) ≥ 2.
Definic¸a˜o 47 (Conexo) Um grafo simples G = (V,A) e´ dito conexo se e
so´ se para todo par de ve´rtices u, v ∈ V temos que existe um caminho em G
de u a v.
CAM 3 Seja T = (V,A) uma a´rvore livre. Sejam u, v ∈ V . Neste caso,
existe um u´nico caminho de u a v em T .
CAM 4 Toda a´rvore livre e´ um grafo conexo.
CAM 5 Seja T = (V,A) uma a´rvore livre com n ≥ 2, onde n = |V |. Neste
caso, u e v sa˜o as u´nicas folhas de T se e so´ se existe um caminho de tamanho
n− 1 em T de u a v.
CAM 6 Sejam T = (V,A) uma a´rvore livre e S ⊂ V . Sejam ainda u ∈ S e
v ∈ V − S. Neste caso, existe um caminho de u a v em T que conte´m pelo
menos uma aresta a tal que
|a ∩ S| = |a ∩ (V − S)| = 1.
Definic¸a˜o 48 Dizemos que um passeio ou trilha p = (v0, v1, · · · , vk) e´ fe-
chado em G se somente se
v0 = vk.
Caso contra´rio, p e´ aberto em G.
PSS 3 Seja p um passeio fechado em G. Neste caso,
‖p‖ 6= 1.
13.4. CIRCUITOS E CICLOS 63
13.4 Circuitos e Ciclos
Definic¸a˜o 49 (Circuito) Uma trilha fechada em G e´ denominada circuito.
Definic¸a˜o 50 (Ciclo) Um caminho fechado de tamanho k ≥ 3 em G e´
denominado ciclo.
CIC 1 Se p e´ um passeio fechado de tamanho treˆs enta˜o p e´ um ciclo.
CIC 2 Se G conte´m um passeio fechado de tamanho ı´mpar enta˜o G conte´m
um ciclo de tamanho ı´mpar.
CIC 3 Se G conte´m dois passeios distintos de u a v enta˜o G conte´m um
passeio fechado iniciando por u e passando por v.
CIC 4 Se G na˜o tem ciclos nem ve´rtices isolados enta˜o G tem pelo menos
duas folhas.
CIC 5 Sejam T = (V,A) uma a´rvore livre, u, v ∈ V e {u, v} /∈ A. Neste
caso, o grafo G = (V,A ∪ {{u, v}}) tem um u´nico ciclo.
CIC 6 Sejam G = (V,A) um grafo conexo, onde grau(v) = 2 para todo
v ∈ V . Neste caso, o grafo G e´ um ciclo.
13.5 Esparsidade
13.6 A´rvores Livres e Geradoras
13.7 Componentes Conexos
Seja G = (V,A) um grafo simples com n ve´rtices e m arestas.
Definic¸a˜o 51 Dizemos que H e´ um componente conexo de G se e somente
se
(i) H ≤ G
(ii) H e´ conexo
(iii) na˜o existe H ′ conexo, com H < H ′ ≤ G
CMP 1 Se G e´ conexo enta˜o G e´ seu u´nico componente conexo.
64 CAPI´TULO 13. GRAFOS SIMPLES
CMP 2 Se G tem c componentes conexos enta˜o n− c ≤ m.
CMP 3 Se G e´ conexo enta˜o n− 1 ≤ m.
Definic¸a˜o 52 Sejam u e v dois ve´rtices quaisquer em V . Dizemos que u _ v
se e somente se existe um caminho de u a v em G.
CMP 4 A relac¸a˜o _ e´ uma relac¸a˜o de equivalencia em V , isto e´,
(i) reflexiva;
(ii) sime´trica;
(iii) transitiva.
Definic¸a˜o 53 Seja u um ve´rtice qualquer em V . Definimos o subgrafo Hu =
(Vu, Au) por
Vu = {v ∈ V |u _ v}
Au = {a ∈ A| a ⊂ V }.
CMP 5 Se x _ y enta˜o Vx = Vy.
CMP 6 Se x _ y enta˜o Ax = Ay.
CMP 7 Se x _ y enta˜o Hx = Hy.
CMP 8 Se x ∈ V enta˜o Hx e´ conexo maximal.
CMP 9 (Caracterizac¸a˜o) H e´ um componente conexo de G se e somente
se existe um u ∈ V tal que H = Hu.
CMP 10 (Graus Pequenos) Se para todo v ∈ V temos grau(v) ≤ 2 enta˜o
os componentes conexos de G sa˜o
(i) ou ve´rtices isolados;
(ii) ou ciclos;
(iii) ou caminhos.
13.8. GRAFOS BIPARTIDOS 65
13.8 Grafos Bipartidos
Definic¸a˜o 54 Seja G = (V,A) um grafo simples. Dizemosque G e´ um grafo
bipartido em S e T se e somente se
(i) V = S ∪ T S ∩ T = φ
(ii) a ∈ A ⇒ |a ∩ S| = |a ∩ T | = 1
Quando isto ocorre, denotamos por G = (S, T ;A).
BIP 1 Seja G um grafo bipartido. Se H ≤ G enta˜o H e´ um grafo bipartido.
BIP 2 G e´ um grafo bipartido se e somente se todos os componentes conexos
de G sa˜o grafos bipartidos.
BIP 3 Seja G um grafo bipartido em S e T e (v0, v1, · · · , vk) um passeio em
G. Se v0 ∈ S enta˜o
(i) v2i ∈ S para i = 0, 1, · · · , k/2;
(ii) v2i+1 ∈ T para i = 0, 1, · · · , (k − 1)/2.
BIP 4 Se G e´ um grafo bipartido enta˜o todo ciclo de G tem tamanho par.
BIP 5 Se G e´ conexo e todo ciclo de G tem tamanho par enta˜o G e´ um
grafo bipartido.
BIP 6 (Caracterizac¸a˜o - Ko¨nig, 1936) G e´ um grafo bipartido se e so-
mente se todo ciclo de G tem tamanho par.
13.9 Articulac¸o˜es e Pontes
Seja G = (V,A) um grafo simples.
Definic¸a˜o 55 Dizemos que v ∈ V e´ um ponto de articulac¸a˜o de G se e
somente se existem x, y ∈ V tais que
(i) x _ y
(ii) todo caminho de x a y passa por v
66 CAPI´TULO 13. GRAFOS SIMPLES
ART 1 (Caracterizac¸a˜o) O ve´rtice v ∈ V e´ um ponto de articulac¸a˜o de
G se e somente se existem arcos {r, v}, {v, s} ∈ A tais que todo caminho de
r a s passa por v.
Definic¸a˜o 56 Dizemos que a ∈ A e´ uma ponte em G se e somente se existem
x, y ∈ V tais que
(i) x _ y
(ii) todo caminho de x a y conte´m a
PNT 1 Se {u, v} ∈ A e v e´ uma folha de G enta˜o {u, v} e´ uma ponte em
G.
PNT 2 Se {u, v} ∈ A e u e v sa˜o pontos de articulac¸a˜o de G enta˜o {u, v}
e´ uma ponte em G.
PNT 3 (Caracterizac¸a˜o) O arco {u, v} ∈ A e´ uma ponte em G se e so-
mente se ocorre exatamente uma das seguintes alternativas
(i) u e v sa˜o pontos de articulac¸a˜o
(ii) u ou v sa˜o folhas.
13.10 Componentes Biconexos
Seja G = (V,A) um grafo simples.
Definic¸a˜o 57 Dizemos que G e´ biconexo se e somente se
(i) G e´ conexo
(ii) G na˜o tem pontos de articulac¸a˜o.
BCX 1 G e´ biconexo e |V | ≥ 3 se e somente se para todo par u, v ∈ V
existem dois caminhos ve´rtices disjuntos de u a v.
BCX 2 G e´ biconexo e |V | ≥ 3 se e somente se para todo par u, v ∈ V existe
um ciclo contendo u e v.
BCX 3 G e´ biconexo e |V | ≥ 3 se e somente se para toda tripla u, v, w ∈ V
existe um ciclo contendo u, v e w.
13.10. COMPONENTES BICONEXOS 67
Definic¸a˜o 58 Dizemos que H e´ um componente biconexo de G se e somente
se
(i) H ≤ G
(ii) H e´ biconexo
(iii) na˜o existe H ′ biconexo, com H < H ′ ≤ G
Definic¸a˜o 59 Sejam a, a′ ∈ A. Dizemos que a ≡ a′ se e somente se ocorre
exatamente uma das seguintes alternativas
(i) a = a′
(ii) existe um ciclo em G que conte´m a e a′.
BCX 4 A relac¸a˜o ≡ e´ uma relac¸a˜o de equivalencia em A, isto e´,
(i) reflexiva;
(ii) sime´trica;
(iii) transitiva.
Definic¸a˜o 60 Seja a uma aresta qualquer em V . Definimos o subgrafo Ha =
(Va, Aa) por
Aa = {a′ ∈ A|a′ ≡ a}.
Va = {v ∈ V |v ∈ a′ ∈ Aa}
BCX 5 Se a ≡ b enta˜o Aa = Ab.
BCX 6 Se a ≡ b enta˜o Ha = Hb.
BCX 7 Para todo a ∈ A, Ha e´ biconexo.
BCX 8 Se Aa ∩ Ab = φ enta˜o |Va ∩ Vb| ≤ 1.
BCX 9 Se Aa ∩Ab = φ e v ∈ Va ∩ Vb enta˜o v e´ um ponto de articulac¸a˜o de
G.
BCX 10 H e´ um componente biconexo de G se e somente se existe um
a ∈ A tal que H = Ha.
BCX 11 Os componentes biconexos formam uma estrutura de arboresceˆncia.
68 CAPI´TULO 13. GRAFOS SIMPLES
Cap´ıtulo 14
Grafos Dirigidos
14.1 Representac¸a˜o
Por na˜o terem arestas paralelas, os grafos dirigidos tambe´m tem uma de-
finic¸a˜o simplificada.
Definic¸a˜o 61 Dizemos que G = (V,A) e´ um grafo dirigido se e somente se
A ⊆ V × V .
Definic¸a˜o 62 (Indicadoras) Para cada v, w ∈ V e a ∈ A definimos a
varia´vel indicadora Ia(v, w) por
Ia(v, w) =
{
1 se a = (v, w)
0 caso contra´rio
Definic¸a˜o 63 Para todo ve´rtice v ∈ V definimos o grauin(v) e o grauout(v)
respectivamente por
grauin(v) =
∑
a∈A
∑
w∈V Ia(w, v)
grauout(v) =
∑
a∈A
∑
w∈V Ia(v, w).
Definic¸a˜o 64 Se grauin(v) = 0 dizemos que v e´ uma fonte em G.
Definic¸a˜o 65 Se grauout(v) = 0 dizemos que v e´ um sumidouro em G.
69
70 CAPI´TULO 14. GRAFOS DIRIGIDOS
14.2 Grafos Derivados
Definic¸a˜o 66 Seja G = (V,A) um grafo dirigido. Seja tambe´m A′ = {(v, u)|(u, v) ∈
A}. Definimos o grafo transposto GT por
GT = (V,A′)
TRP 1 (GT )T = G.
TRP 2 O ve´rtice v e´ uma fonte em G se e somente se o ve´rtice v e´ um
sumidouro em GT .
TRP 3 O ve´rtice v e´ um sumidouro em G se e somente se o ve´rtice v e´ uma
fonte em GT .
14.3 Passeios, Trilhas e Caminhos
Seja G = (V,A) um grafo dirigido.
Definic¸a˜o 67 (Passeio) Dizemos que p e´ um passeio de tamanho k em G
se somente se
(i) p = (v0, v1, · · · , vk)
(ii) vi ∈ V i = 0, · · · , k
(iii) (vi−1, vi) ∈ A i = 1, · · · , k.
onde k ≥ 0.
Neste caso, dizemos que p vai de v0 a vk. Ale´m disso, os ve´rtices v0 e vk
sa˜o denominados terminais do passeio p. O ve´rtice v0 e´ a origem do passeio,
enquanto o ve´rtice vk e´ o destino do passeio. Usamos ‖p‖ para denotar o
tamanho de p.
Para u ∈ V , temos que (u) e´ um passeio de tamanho 0 em G de u a u.
PSS 4 Se p1 = (v0, v1, · · · , vk) e p2 = (u0, u1, · · · , ul) sa˜o dois passeios em
G e vk = u0, enta˜o p3 = (v0, v1, · · · , vk, u1, · · · , ul) tambe´m e´ um passeio em
G e ‖p3‖ = k + l.
Definic¸a˜o 68 (Trilha) Dizemos que um passeio p = (v0, v1, · · · , vk) e´ uma
trilha em G se somente se (vi−1, vi) 6= (vj−1, vj) para 1 ≤ i < j ≤ k.
14.4. CIRCUITOS E CICLOS 71
Definic¸a˜o 69 (Caminho) Dizemos que um passeio p = (v0, v1, · · · , vk) e´
um caminho em G se somente se vi 6= vj para 1 ≤ i < j ≤ k
CAM 7 Todo caminho em G e´ tambe´m uma trilha em G.
Definic¸a˜o 70 Dizemos que um passeio ou trilha p = (v0, v1, · · · , vk) e´ fe-
chado em G se somente se
v0 = vk.
Caso contra´rio, p e´ aberto em G.
14.4 Circuitos e Ciclos
Definic¸a˜o 71 (Circuito) Uma trilha fechada em G e´ denominada circuito.
Definic¸a˜o 72 (Ciclo) Dizemos que um passeio p = (v0, v1, · · · , vk) e´ um
ciclo em G se somente se
(i) 3 ≤ k;
(ii) p = (v0, v1, · · · , vk−1) e´ um caminho;
(iii) v0 = vk.
CIC 7 Se G conte´m um passeio fechado de tamanho ı´mpar enta˜o G conte´m
um ciclo de tamanho ı´mpar.
14.5 Grafos Especiais
14.6 Grafos Ac´ıclicos
Definic¸a˜o 73 Seja G = (V,A) um grafo dirigido. Dizemos que G e´ um
grafo dirigido ac´ıclico se e somente se na˜o existem ciclos dirigidos em G.
GDA 1 G e´ um grafo dirigido ac´ıclico se e somente se todo subgrafo de G
e´ dirigido ac´ıclico.
GDA 2 G e´ um grafo dirigido ac´ıclico se e somente se GT e´ um grafo diri-
gido ac´ıclico.
GDA 3 Todo grafo dirigido ac´ıclico G tem pelo menos uma fonte.
72 CAPI´TULO 14. GRAFOS DIRIGIDOS
GDA 4 Todo grafo dirigido ac´ıclico G tem pelo menos um sumidouro.
GDA 5 (Caracterizac¸a˜o) G e´ um grafo dirigido ac´ıclico se e somente se
todo subgrafo de G tem pelo menos uma fonte.
Exerc´ıcio 24 Projete um algoritmo para testar se um grafo e´ ac´ıclico, uti-
lizando a caracterizac¸a˜o anterior.
GDA 6 G e´ um grafo dirigido ac´ıclico se e somente se todo subgrafo de G
tem pelo menos um sumidouro.
14.7 Ordenac¸a˜o Topolo´gica
Seja G = (V,A) um grafo dirigido com |V | = n.
Definic¸a˜o 74 Dizemos que uma bijec¸a˜o f : V −→ {1, · · · , n} e´ uma or-
denac¸a˜o topolo´gica de G se e somente se
f(u) < f(v) para (u, v) ∈ A.
OTP 1 (Caracterizac¸a˜o) G e´ um grafo dirigido ac´ıclico se e somente se
G tem uma ordenac¸a˜o topolo´gica.
Exerc´ıcio 25 Projete um algoritmo para testar se um grafo e´ ac´ıclico, uti-
lizando a caracterizac¸a˜o anterior.
14.8 Componentes Fortemente Conexos
FCX 1 Os componentes fortemente conexos formam uma estrutura dirigida
ac´ıclica.
Cap´ıtulo 15
Otimizac¸a˜o em Grafos
15.1 Pareamentos Ma´ximos
Seja G = (V,A) um grafo bipartido.
Definic¸a˜o 75 Seja P ⊆ A. Dizemos que P e´ um pareamento em G se e
somente se