Upload
dinhhanh
View
222
Download
1
Embed Size (px)
Citation preview
Teoria dos Grafos e Análise CombinatóriaApresentação da disciplina e revisão de Matemática Discreta
Rodrigo [email protected]
Instituto de InformáticaUniversidade Federal do Rio Grande do SulPorto Alegre, Brasilhttp://www.inf.ufrgs.br
Conteúdo
Apresentação da disciplina
Revisão de matemática discreta
2/45
Conteúdo
Apresentação da disciplina
Revisão de matemática discreta
3/45
Sobre a disciplina
INF05512 – Teoria dos Grafos e Análise Combinatória
Sobre o que trata:• matemática discreta• resolução de problemas de contagem e enumeração• grafos e resolução de problemas envolvendo grafos
4/45
Sobre o conteúdo
A disciplina possui duas etapas bem caracterizadas: inicia com análisecombinatória e conclui com teoria dos grafos.
Cronograma aproximado:• ± 4 semanas: princípios de contagem e aplicações.• ± 4 semanas: funções geradoras e resolução de recorrências.• ± 4 semanas: grafos simples e problemas associados.• ± 4 semanas: grafos valorados e problemas associados, planaridade e
coloração de grafos simples.
5/45
Sobre a bibliografia
Análise combinatória• Introdução à Análise Combinatória
(José Plínio O. Santos, Margarida P.Mello, Idani T. C. Murari)
• Enumerative Combinatorics (RichardStanley)
• Enumerative Combinatorics(Charalambos A. Charalambides)
• A Walk Through Combinatorics: AnIntroduction to Enumeration and Graph
Theory (Miklós Bóna)Teoria dos Grafos• Introduction to Graph Theory (Douglas
B. West)
• Introduction to Graph Theory (RichardJ. Trudeau)
• Graph Theory (Frank Harary)
• Grafos: Teoria, Modelos, Algoritmos(Paulo Oswaldo Boaventura Netto)
Nota: os exercícios numerados apresentados nestes slides referem-se aosexemplos desenvolvidos no livro Introdução à Análise Combinatória, de JoséPlínio Santos et al.
6/45
Sobre o professor
Rodrigo Machado
• Interesses: programação funcional, reescrita algébrica de grafos, lógica esemântica de programas.
• Página pessoal: http://www.inf.ufrgs.br/∼rma
Contato:• Pessoalmente: sala 217, prédio 72 (a caminho das impressoras)
• Por email: [email protected]
• Via Moodle: ele envia automaticamente um email para mim, e fica registrado(forma preferencial).
• Em caso de dúvidas/sugestões/críticas: entrem em contato!!!
7/45
Sobre a metodologia
O que está na súmula:• 60 h teóricas (em sala de aula)
• 0 h práticas (em laboratório). Nota: na verdade serão várias horas bem práticasresolvendo exercícios extra-classe.
É uma disciplina matemática: o que significa• assistir passivamente: não adianta muito para absorver o conteúdo.
• melhor forma de estudar = mão na massa (resolver problemas).
• vamos ver uma série de tipos de problemas e técnicas de resolução.
• listas de exercício
• possível implementação (grafos)
8/45
Sobre a metodologia (2)
Exemplos de problemas que aprenderemos a resolver:• De quantas formas podemos distribuir 10 bolas idênticas entre 4 caixas numeradas de
forma que cada caixa não esteja vazia?
• Qual o número mínimo de pessoas que precisamos ter em um grupo para garantir que aomenos 3 delas façam aniversário no mesmo dia da semana?
• Quantos anagramas distintos possui a palavra ASSASSINOS?
• A população de sapos de um lago quadruplica a cada ano. No primeiro dia de cada ano,100 sapos são removidos do lago e transferidos para outro local. Assumindo queinicialmente havia 50 sapos no lago, quantos sapos o lago terá após 20 anos? Há umafórmula que nos diga o número de sapos em X anos?
• Considerando o mapa rodoviário de uma dada localidade:
◦ Como verificar eficientemente se exista um trajeto que passe exatamente uma vezpor cada trecho de rodovia?
◦ Como calcular eficientemente a distância mínima entre duas cidades?
9/45
Sobre a metodologia (3)
Plataforma de acompanhamento do curso: Moodle da UFRGS (não é o doINF).
http://moodle.ufrgs.br
Acesso pelo usuário e senha institucionais (Cartão UFRGS)
Toda a comunicação oficial do professor com a turma se dará atravésdo Moodle! Ex:• marcação e possível troca de data de prova• disponibilização de slides e listas de exercício• determinação de trabalhos práticos
10/45
Sobre a avaliação
Atividades de avaliação:• M1 = Prova 1 (análise combinatória)• M2 = Prova 2 (teoria dos grafos, peso 0.8) + Trabalhos (peso 0.2)
Ao longo do semestre serão definidos o número total de trabalhos (tipicamente2) e o seu respectivo tipo (lista de exercício e/ou implementação).
Cálculo da média final:M = (M1 + M2)/2
Aprovação: frequência (≥ 75%) + nota mínima (M ≥ 6).
11/45
Sobre o conceito final
Frequência menor que 75%: FF
Frequencia maior que 75%, com média M:
M < 6 D6 ≤ M < 7.5 C7.5 ≤ M < 9 B9 ≤ M A
12/45
Sobre a recuperação
Se o aluno tiver frequência mínima porém não tiver nota mínima, estaráhabilitado à um exame de recuperação R.
Sobre o exame:• versa sobre todo o conteúdo do semestre• a nota do exame é utilizada para substituir a menor nota entre prova 1 e
prova 2, sendo recalculada uma média de recuperação MR utilizando amesma fórmula anterior.
Se MR for maior que 6, o aluno estará aprovado.
Alunos que queiram realizar exame para aumento de conceito deverãomanifestar interesse até 48h da realização do mesmo.
13/45
Conteúdo
Apresentação da disciplina
Revisão de matemática discreta
14/45
Conjuntos
• Coleções de elementos◦ Sem ordem◦ Sem repetição
• Descritos por extensão ou compreensão:
◦ Extensão: Enumeração dos elementos entre chaves
{4, 5} {a, b, c} {}
◦ Compreensão: Propriedade que caracteriza os elementosEx.: Conjunto dos números inteiros maiores que 42
{x | x ∈ Z ∧ x > 42}
• Conjunto vazio: ∅ ou {}. Importante: note que {∅} 6= ∅
15/45
Operações sobre conjuntos
• x ∈ A (pertinência): Relaciona um elemento x a um conjunto A, sendoválida se x pertencer a A.
4 ∈ N {4} 6∈ N
• A ⊆ B (continência): Relaciona um conjunto A a um conjunto B, sendoválida se todo elemento de A for também elemento de B.
4 6⊆ N {4} ⊆ NN ⊆ Z ∅ ⊆ {1, 2, 3, 4}
16/45
Operações sobre conjuntos (cont.)
• A ∪ B (união): Conjunto contendo todos os elementos que ocorrem em Aou em B.
{1, 2, 3} ∪ {5} = {1, 2, 3, 5} {a, b} ∪ {a} = {a, b}
• A ] B (união disjunta): Conjunto contendo todos os elementos queocorrem em A ou em B, diferenciando ocorrências do mesmo elemento emcada conjunto de origem. Intuição: introdução de anotações nos elementospara diferenciar origem.
{1, 2, 3} ] {5} = {11, 21, 31, 52} {a, b} ] {a} = {a1, b1, a2}
17/45
Operações sobre conjuntos (cont.)
• A ∩ B (interseção): Conjunto contendo todos os elementos que ocorremem A e em B.
{1, 2, 3} ∩ {5} = ∅ {a, b} ∩ {a} = {a}
• A × B (conjunto dos pares): Conjunto de todos os pares ordenados(a, b), onde a ∈ A e b ∈ B.
A = {a, b} B = {1, 2}
A × B = { (a, 1), (a, 2), (b, 1), (b, 2) }
18/45
Operações sobre conjuntos (cont.)
• P(A) ou 2A (conjunto potência): Conjunto de todos os subconjuntos deA.
P({a, b}) = { {}, {a}, {b}, {a, b} }
Exercício: Escreva o conjunto potência P(A × B), onde A = {1, 2} eB = {x, y}.
19/45
Principais conjuntos numéricos
Naturais N = {0, 1, 2, 3, 4, . . .}
Naturais positivos N+ = {1, 2, 3, 4, . . .}
Inteiros Z = {. . . – 3, –2, –1, 0, 1, 2, 3, . . . , }
Racionais (frações) Q = {– 12 , –1, 0, 1
2 , 1, . . .}
Irracionais I = {–√
2,√
2,√
3,π, e, . . .}
Reais R = Q ∪ I = {–π, –1, 0, 1,√
2, 12 , e, 2, . . .}
20/45
Relações
• Uma relação binária R ⊆ A × B é uma associação entre elementos de umconjunto A e elementos de um conjunto B.
Exemplo:
A = {a, b} B = {1, 2} R = { (a, 1), (a, 2), (b, 2) }
R :
a 1
b 2
21/45
Relações: propriedades
Uma relação R ⊆ U × U pode ser (para todo a, b, c ∈ U)• reflexiva: aRa• transitiva: aRb ∧ bRc ⇒ aRc• simétrica: aRb ⇒ bRa• anti-simétrica: aRb ∧ bRa ⇒ a = b• total: para todo a existe b tal que aRb• sobrejetora: para todo b existe a tal que aRb• funcional: aRb ∧ aRc ⇒ b = c• injetora: aRc ∧ bRc ⇒ a = b
22/45
Relações: tipos importantes
• função parcial (funcional)
Ex: (x 7→ x – 1) ⊆ N × N
• função (funcional e total)
Ex: (x 7→ x + 1) ⊆ N × N
• ordem parcial (reflexiva, transitiva e anti-simétrica)
Ex: (≤) ⊆ N × N
• equivalência (reflexiva, transitiva e simétrica)
Ex: (≡) ⊆ N × N onde x ≡ y sss (x e y pares) ou (x e y ímpares)
23/45
Funções
• Uma função f : A → B é um mapeamento de elementos de A paraelementos de B
◦ A é o domínio (ou origem) de f. Escrito dom(f).◦ B é o contradomínio (ou destino) de f. Escrito cod(f).◦ O conjunto de todos os elementos de B aos quais algum a ∈ A está associado
é chamado de imagem de f. Escrito img(f).
a 1b 2c 3
4
A f B
dom(f) = {a, b, c}cod(f) = {1, 2, 3, 4}img(f) = {1, 2}
24/45
Funções parciais
• Funções parciais são aquelas onde é possível (mas não necessário) que umelemento do domínio não tenha associação no contradomínio.
Exemplo:a 1b 2c 3
• f(c) = ⊥ denota que f é indefinida para o elemento c.• Utiliza-se f : A ⇀ B para denotar que f é parcial e f : A → B para denotar
que f é totalmente definida.• Funções totais são casos especiais de funções parciais.
25/45
Composição de funções parciais
• Considere f : A → B e g : B → C.
a 1 xb 2 yc 3 z
A f B g C
• A função g ◦ f : A → C é denominada a composição de f e g, ondeg ◦ f(x) = g(f(x)).
a xb yc z
A g ◦ f C
26/45
Cardinalidade
• Cardinalidade = tamanho de um conjunto.• |X|, #(X) ou n(X) denotam a cardinalidade de X.• Exemplo:
|∅| = 0|{7}| = 1
|{a, b, {c, d}}| = 3|N| = infinito contável|R| = infinito incontável
• Nesta disciplina: essencialmente conjuntos finitos.
27/45
Cardinalidade e funções totais
Uma função total f : A → B pode ser
Injetora:x 6= y ⇒ f(x) 6= f(y)
Exemplo:
a 1b 2
3
Nota: |A| ≤ |B|
Sobrejetora:cod(f) = img(f)
Exemplo:
a 1b 2c
Nota: |A| ≥ |B|
Bijetora:injetora e sobrejetora
Exemplo:
a 1b 2c 3
Nota: |A| = |B|
Dois conjuntos A e B possuem a mesma cardinalidade sss existe uma funçãobijetora f : A → B.
28/45
Cardinalidade e operações de conjuntos
Cardinalidade do resultado de operações sobre conjuntos finitos:
|A ∪ B| = |A| + |B| – |A ∩ B|
|A ] B| = |A| + |B|
|A ∩ B| = |A| + |B| – |A ∪ B|
|A × B| = |A| × |B|
|P(A)| ou |2A| = 2|A|
29/45
SomatórioSomatório: maneira compacta de descrever somas de termos que possuamum padrão de formação.• faixa de valores em inteiros:
5∑i=1
xi = x1 + x2 + x3 + x4 + x5
• faixa de valores em conjuntos: seja A = {1, 3, 7}∑i∈A
xi
i = x1
1 + x3
3 + x7
7
• faixa de valores como soluções para certas equações/inequações:∑i,j∈N,1≤i<j≤4
ij = 1
2 + 13 + 1
4 + 23 + 2
4 + 34
30/45
Produtório
Produtório: maneira compacta de descrever produtos que possuam padrão deformação.
Exemplo: ∏i∈N,i<12 e i é primo
i2 = 22 × 32 × 52 × 72 × 112
Nota:
• Somatório 0-ário = 0 (elemento neutro da adição).• Produtório 0-ário = 1 (elemento neutro da multiplicação)
31/45
Multiconjuntos
• Coleções de elementos◦ Sem ordem◦ Com possível repetição (finita)
• Notação: B = Hd, a, b, d, c, a, dI• Um multiconjunto B de elementos tirados de um conjunto X é uma função
do tipo X → N+ que associa um número finito de ocorrências para cadaelemento de X
Exemplo: B : {a, b, c, d} → N+, onde B = {a 7→ 2, b 7→ 1, c 7→ 1, d 7→ 3}
• Nota: um multiconjunto m onde img(m) = {1} representa um conjunto!
32/45
Multiconjuntos: cardinalidade
A cardinalidade de um multiconjunto é o número de elementos que estepossui, contando repetições.
Exemplo: se A = Ha, a, a, b, b, c, dI, então |A| = 7
Como A é uma função do tipo {a, b, c, d} → N+, ondea 7→ 3, b 7→ 2, c 7→ 1, d 7→ 1 temos que |A| = 3 + 2 + 1 + 1.
Definição: seja A um multiconjunto do tipo X → N+. Então
|A| =∑x∈X
A(x)
33/45
Tuplas ou sequências• Coleções de elementos
◦ Finitas◦ Com ordem◦ Com possível repetição◦ Generalização do produto cartesiano (pares ordenados)
• Notação: (): tupla vazia, (a): produto unário, (a, b): dupla, (a, b, c):tripla, (a, b, c, d): quádrupla, . . .
• Uma n-tupla sobre um conjunto U é um elemento do produto
n︷ ︸︸ ︷U × U × · · · × U
• Nota: apesar de multiplicação de conjuntos não ser concretamenteassociativa, isto é, U × (U × U) 6= (U × U) × U, há uma bijeção entre oselementos das duas multiplicações (a, (b, c)) 7→ ((a, b), c), portanto aordem das multiplicações é habitualmente ignorada.
34/45
Coleções de elementos
Conjuntos vs Multiconjuntos vs Tuplas
Ordem\Repetição Sim NãoSim Tupla (a, b, a) Tupla (a, b, c)Não Multiconjunto Ha, b, aI Conjunto {a, b, c}
Exercício: dados os elementos a, b, c, gere todas as coleções abaixo:1. conjuntos com no máximo 3 elementos2. multiconjuntos com no máximo 3 elementos3. pares (com repetição e sem repetição)4. triplas (com repetição e sem repetição)
35/45
Função fatorial
A função fatorial : N → N ocorre frequentemente na resolução de problemasde análise combinatória.
Notação: fact(n) ou n!
Definição:
n! ={
1 se n = 0∏1≤i≤n i se n > 0
Exemplo:
5! = 1 × 2 × 3 × 4 × 5 = 120
36/45
Sequência de Fibonacci
A sequência de Fibonacci é famosa por possuir relação com diversosprocessos naturais.
Definição:
F1 = 1F2 = 1Fn = Fn–1 + Fn–2 para n > 2
Primeiros termos:
n Fn1 12 13 24 35 56 87 138 21...
...
37/45
Indução matemática
Indução matemática é uma importante técnica de prova de propriedadessatisfeitas por todos os elementos de um conjunto infinito.
Aplicável quando os elementos do conjunto são construídos de forma indutiva,como por exemplo:
• Números naturais:0 : N esucc : N → N
• Listas:empty : Lista(A) econs : A × Lista(A) → Lista(A)
38/45
Indução matemática (cont.)
• Para provar que propriedade P vale para todos os elementos de umconjunto A, devemos demonstrar que:1. P vale no caso base (para os naturais, 0)2. supondo que P valha para um elemento qualquer n (hipótese indutiva), deve
continuar valendo após aplicarmos um construtor sobre n (para os naturais,succ(n)).
Em outras palavras, a propriedade é preservada pela construção doselementos de A.
39/45
Indução matemática: exemplo
Exemplo: prove por indução que a seguinte igualdade vale para todo n ∈ N+:
n∑i=1
2i – 1 = n2
Nota:1 = 11 + 3 = 41 + 3 + 5 = 91 + 3 + 5 + 7 = 16 · · ·
40/45
Indução matemática forte
Na indução matemática, justificamos a validade de um propriedade P para n apartir da hipótese que P vale para n – 1.
Algumas estruturas (como árvores binárias) podem ter construção maiscomplexa e que não necessariamente referenciar o elemento imediatamenteinferior.
Exemplo: construção de árvore com 8 folhas baseada em duas árvores de 4folhas.
Para provar propriedades de tais estruturas, utilizamos uma descriçãoalternativa do princípio da indução matemática (chamado de indução forte).
41/45
Indução matemática forte (cont.)
Ao utilizarmos a indução matemática forte:• provamos que P vale para o caso base (0 para N)• provamos que P vale para n ∈ N a partir da hipótese indutiva que P vale
para todo k ∈ N tal que k < n.
Nota: indução matemática (fraca) e indução matemática forte são princípiosequivalentes.
42/45
Indução matemática forte: exemplo
Exemplo: Demonstre que, para todo n ∈ N+,
Fn <(
74
)n
Nota:
n Fn(
74
)n
1 1 1, 752 1 3, 063 2 5, 354 3 9, 375 5 16, 416 8 28, 727 13 50, 26...
......
43/45
Indução matemática: exercício 1
Exercício:
Demonstre que, para todo n ∈ N+,
Fn = 1√5
(φn – φn)
ondeφ = 1 +
√5
2e
φ = 1 –√
52
44/45
Indução matemática: exercício 2
Exercício:
Considere a seguinte definição de Sm
Sm =m∑
i=1i2
Demonstre que, para todo m ∈ N+,
Sm = 16m(m + 1)(2m + 1)
45/45