Introdução

I Conceitos e Resultados Gerais

1 Linguagem Matemática e Lógica Informal1.1 Sistemas matemáticos ..1.2 Noção de conjunto .....1.3 Linguagem proposicional . .1.4 Operações sobre conjuntos.1.5 União e intersecção generalizadas e quantificadores1.6 Relações .

1.6.1 Relações de ordem .1.6.2 Relações de equivalência.1.6.3 Funções .

1.7 Cardinalidade.......1.8 Algumas notas históricas.1.9 Exercícios .

2 Contextos e Estratégias de Demonstração2.1 Estratégias de demonstração da implicação

2.1.1 Prova directa .2.1.2 Demonstração por contraposição ..2.1.3 Demonstração por redução ao absurdo

2.2 Princípio de indução .2.3 Princípio da gaiola dos pombos2.4 Exercícios .

11 Combinatória

3 Princípios de Enumeração Combinatória3.1 Princípio da bijecção . . . . . . . . . . .3.2 Princípios da adição e da multiplicação.3.3 Princípio de inclusão-exclusão3.4 Exercícios .

Conteúdo

ix

1

3367

111416192022263133

3737373940414951

55

5757606468

iv Conteúdo

4 Agrupamentos e Identidades Combinatórias4.1 Arranjos com repetição .4.2 Arranjos e combinações simples .4.3 Combinações e permutações com repetição.4.4 Permutações .4.5 Identidades combinatórias4.6 Exercícios .

71717277818590

5 Recorrência e Funções Geradoras5.1 Dependências recursivas simples .5.2 Equações de recorrência homogéneas .5.3 Equações de recorrência lineares não homogéneas5.4 Equações de recorrência não lineares5.5 Funções geradoras ... . . . . . . . . . . . . . .

5.5.1 Séries formais de potências .5.5.2' Funções geradoras ordinária e exponencial .

5.6 Equações de recorrência e funções geradoras .5.7 Funções geradoras de várias variáveis.5.8 Exércícios......... .

939395

102106109110115118123124

6 Números Combinatórios6.1 Factoriais e números binomiais .6.2 Números de Fibonacci e o número de ouro.6.3 Números de Stirling6.4 úmeros de Euler6.5 úmeros de Bell ..6.6 úmeros de Catalan6.7 Exercícios . . . . . .

127127130136141144145150

111 Abordagens Algébricas da Combinatória 153

7 Conjuntos Parcialmente Ordenados e Reticulados7.1 Conjuntos ordenados - definições básicas .....7.2 Funções entre conjuntos parcialmente ordenados7.3 Reticulados .

7.3.1 Definições e conceitos básicos .7.3.2 Subreticulados e isomorfismos .7.3.3 Reticulados distributivos ....7.3.4 Representação de reticulados distributivos7.3.5 Topologias finitas e reticulados .

7.4 Cadeias e anticadeias . . . . . . . . . . . . . . . .7.5 Relações de ordem fraca, intervalar e semi-transitivas .7.6 Teorema da inversão de Môbius7.7 Conjuntos extremais7.8 Exercícios .

155155158161162164167170171180185189194197

Conteúdo v

8 Divisibilidade e Aritmética Modular8.1 AIgoritmo de Euclides .8.2 Funções de Euler e de Mõbíus .8.3 Relações ,de congruência . . . . . . .8.4 Equações e polinómios em corpos finitos8.5 Corpos de Galois . . . . . . . . . . . . .8.6 Quadrados latinos e quadrados mágicos8.7 Exercícios.................

201202204208212216225233

9 Designs Combinatórios e Geometrias Finitas9.1 Designs combinatórios .9.2 Planos projectivos e afins .9.3 Quadrados latinos e planos afins e projectivos9.4 Espaços projectivos ..9.5 Matrizes de Hadamard9.6 Exercícios ...

237237244254259263267

10 Álgebras de Boole10.1 Definições e resultados básicos .....10.2 Cálculo proposicional e circuitos lógicos10.3 Átomos e isomorfismos .10.4 Funções booleanas .10.5 Mapas de Karnaugh10.6 Exercícios .

271271277285289293300

11 Grupos Finitos e Enumeração de Pólya11.1 Introdução aos grupos finitos11.2 Lema de Burnside11.3 Teorema de Pólya.11.4 Grupo diedral .11.5 Exercícios .

305305310314319321

IV Teoria dos Grafos e Algoritmos 327

12 Conceitos e Resultados Fundamentais12.1 Grafos orientados e não orientados .12.2 Representações de grafos em computador .12.3 Isomorfismos, grafos etiquetados e não etiquetados12.4 Conceitos métricos .12.5 Grafos e subgrafos particulares .12.6 Exemplos de enumeração de grafos simples12.7 Sequências de graus de vértices ..12.8 Algoritrnos de pesquisa em grafos .12.9 Exercícios .

329 ,329333335336338341343347350

13 Conexidade13.1 Grafos Conexos . . . . . . . . . . . . . .13.2 Determinação de componentes conexas .13.3 AIgoritmo de fusão de vértices .....13.4 Grafos orientados fortemente conexos ..

357357361362369

vi Conteúdo

13.5 Algoritmo de Leifman13.6 Exercícios .

371375

14 Caminhos14.1 Relações entre diâmetro, cintura e número de vértices14.2 Pesquisa em largura em grafos sem custos nas arestas14.3 Custos não negativos - algoritmo de Dijkstra .14.4 Custos arbitrários - algoritmo de Bellman-Ford14.5 Algoritmo de Floyd .14.6 Exercícios .

379379385387392394397

15 Árvores15.1 Árvores e florestas . . . . . . . . . . . . .15.2 Número de árvores abrangentes .15.3 Geração de todas as árvores abrangentes .15.4 Código de Prüfer .15.5 Árvores abrangentes de custo mínimo

15.5.1 Algoritmo de Kruskal15.5.2 Algoritmo de Prim

15.6 Exercícios .

401401403406410413413416418

16 Fluxos em Redes16.1 Fluxo máximo em redes .

16.1.1 Teorema de Ford e Fulkerson .16.1.2 Algoritmo para o fluxo máximo

16.2 Fluxo de custo mínimo .16.2.1 Soluções básicas admissíveis .16.2.2 Método simplex para redes

16.3 Exercícios .

423423425428432433437444

17 Emparelhamentos17.1 Emparelhamentos máximos e perfeitos17.2 Emparelhamentos em grafos bipartidos ...

17.2.1 Sistemas de representantes distintos17.2.2 Uma aplicação à partição mínima de cpos em cadeias17.2.3 Problema de afectação de tarefas .....17.2.4 Problema de afectação óptima de tarefas ..

17.3 Emparelhamentos em grafos arbitrários .17.4 Emparelhamentos em grafos com pesos nas arestas17.5 Exercícios .

449449452454457460463468473476

18 Grafos de Euler e Grafos de Hamilton18.1 Grafos de Euler .

18.1.1 Algoritmos de Hierholtzer e de Fleury18.1.2 Problema do carteiro chinês

18.2 Grafos de Hamilton .18.2.1 Código de Gray .18.2.2 Problema do caixeiro viajante.

18.3 Exercícios .

479480483485489493496502

Conteúdo vii

19 Independentes, Cliques e Colorações19.1 Conjuntos independentes e diques .19.2 Coloração de vértices .

19.2.1 Uma aplicação das funções booleanas19.2.2 Polinómios cromáticos ....19.2.3 Colorações parciais e Sudoku .

19.3 Coloração de arestas .19.3.1 Números de Ramsey para grafos simples

19.4 Exercícios .

507507511518522526533536541

20 Grafos Planares e Generalizações20.1 O ponto de vista topológico .

20.1.1 Realização de grafos em superfícies orientáveis20.1.2 Menores e menores topológicos .

20.2 Grafos planares .20.2.1 Propriedades dos grafos planares20.2.2 Teorema de Kuratowski .....20.2.3 Dualidade em grafos e digrafos planares20.2.4 Grafos platónicos .

20.3 Grafos com genus positivo . . . . . . .20.3.1 Fórmula de Euler generalizada20.3.2 Grafos g-platónicos .

20.4 Mapas e colorações .20.4.1 Teorema das quatro cores .20.4.2 Colorações em superfícies de genus positivo20.4.3 Conjecturas de Hadwiger e Hajós .

20.5 Exercícios . . . . . . . . . . . . . . . . . . . . . . .

547547548550553554556559562564565567568569575576579

Apêndices 583

A Notação AssimptóticaA.l Notação "O-grande" ((9) ....A.2 A notação "o-pequeno" (o)A.3 Outras notações assimptóticas .A.4 Teorema da recorrência universalA.5 Exercícios .

585585588589591593

B Notação 597Bibliografia 601

Índice 607