Resumo Matematica Discreta P2 - PUC RIO

Prévia do material em texto

03/04/2012
Aula 1
Divisão Euclidiana
Sejam a e b inteiros, a = 0.
Nestas condições existem inteiros únicos, q e r, de modo que b=a q + r
Dividendo = divisor quociente + resto
Diz-se que um inteiro a = 0 divide um inteiro b se e so se existe um inteiro k tal que 
notação- a divide b
	 	 a não divide b
Máximo Divisor Comum (mdc)
Sejam a e b inteiros (a = 0 ou b = 0)
Diz-se que um inteiro d é o máximo divisor comum de a e b se e so se d a e d b 
e se existe um inteiro d tal que d a e d b então d d ou seja
	 mdc(a,b) =max{d d a e d be}
Teorema (algoritmo de euclides)
Sejam a e b inteiros (a = 0 ou b = 0)
se b= aq + r então mdc(a,b) = mdc(a,r)
PROVA
P2
Algoritmo de Euclides 
estendido
(x y ) é uma solução particular para a equação 20x + 12y = 4 encontrado 
com o algoritmo de Euclides estendido. Outras soluções?
Equação Diofantina: é uma equação do tipo ax + bx = c, com a, b e c inteiros e 
(x, y) também inteiros
Obs: uma equação diofantina ax + bx = c tem solução se e só se o mdc(a, b) 
= d dividir c
12/04/2012
Aula Double-Tap to Edit
12/04/2012
Aula 2
Números primos
Diz-se que p é um inteiro primo se p tem exatamente 2 divisores 
distintos: ele mesmo e 1
Se n não é primo, existem 2 inteiros r e s, ambos diferentes tais que 
r x s = n 
	 Obs. 1- Todo numero inteiro é primo ou pode ser escrito de forma 
unica como produto de fatores primos
	 	 2- Existem infinitos numeros primos
	 	 3- Se p é primo e p > k entao 
Convergência Modulo m ( m = 0)
Def: sejam a, b e m inteiros com m = 0, diz-se que a é congruente a b 
módulo n se e só se n | (a - b)
Notação : a b[m] ou a b(mod m)
A congruência móduo m é uma relação de equivalência no conjunto dos 
inteiros ( ) E tem as seguintes propriedades:
1. Reflexiva 
2. Simetria
3. Transitiva
3. Transitiva 
Classes de Equivalência 
Def 2. Se a. b[m] então os restos das divisões de a por m e de b por m são 
iguais.
Ex. 27 12[5]
Qualquer inteiro n é congruente a infinitos números módulo m = 0 mas n é 
congruente módulo m a apenas um inteiro enter 0 e m - 1.Este inteiro é 
exatamente o resto da divisão de n por m.
Outras Propriedades
ex. determine o resto da divisão de por
Ex. Determine o menor natural k de modo que 4 + k seja divisível por 5
Ex. Determine o algorismo das unidades de 2 7 + 3
17/04/2012
Aula 3
Ex 4. Determine o algorismo das unidades de
Inverso Multiplicativo
Sejam a e m inteiros, m = 0. Se existe um inteiro a' tal que a a' 1[m], diz-se que 
a' é o inverso multiplicativo de a modulo m.
Ex.
a. Determine o inverso multiplicativo de 3 modulo 7.
b. Determine o inv. múltiplo de 2 modulo 4
Sejam a = 0 e m = 0 .
Se a e m são primos enter si então existe o inverso multiplicativo de a 
modulo m
Teorema Binomial Fácil
Se p é primo então (a + b) a + b [p]
 PROVA
Pelo Binômio de Newton sabe-se que
Sabe-se que se p é primo então , ou seja é múltiplo de p. Logo
Pequeno Teorema de Fermat
Se p é primo então a a[p]
PROVA POR INDUÇÃO 
Se p é primo e a 0[p] então a 1[p]
PROVA
Pelo PTF, se p é primo então a a[p].
Como p é primo, o mdc(a,p)=1, logo existe a' tal que a a' 1[p].
Ex. Determine o resto da divisão de 7 por 11.
Teorema Chinês dos Restos - TCR
Sejam m e n inteiros primos enter si.
O sistema 
	 	 	 	 	 	 possui uma solução x = x. Além diso um outro inteiro 
x será também solução do sistema se e só se x x[m n]
Em outars palavras, se m e n são primos entre si, a solução do sistema
	 	 	 	 	 é da forma x = x k m n
19/04/2012
Aula 4
Apresente o conjunto de solução dos sistemas
a.
b.
eq. diofantina
Como mdc(3,4)=1 e 1|1 tem 
solução
Aplicação
	 Criptografia- Código RSA
-A quer receber uma mensagem criptografada em RSA
	 -A escolhe 2 números primos p e q bem grandes, N=p q
	 - A escolhe C tal que mdc(c, p-1) = mdc(c, q-1) = 1
	 - A divulga N e C (chave publica)
-B quer enviar uma mensagem pra A
	 - B conhece N e C
	 - B codifica mensagem x -- x codificado é y que é o resto da divisão de x 
por N. ou seja, x y[N]
	 - B envia y
- A quer decodificar y, ou seja, encontrar x tal que x y[N]
	 - A vai encontrar a chave de decodificação
	 	 Sabe-se que o mdc(c,p-1) = 1 e mdc(c,q-1) = 1, 
	 	 logo mdc(c,(p-1)(q-1)) = 1 -> existe o inverso multiplicativo de C 
modulo (p-1)(q-1), ou seja existe d tal que cd 1[(p-1)(q-1)]
mod
é uma eq. diofantina com solução - encontar d
Lista 2 , questão 34
Double-Tap to Edit
24/04/2012
Aula 5
Conceitos Básicos - Teoria dos GRAFOS
Um grafo G(V, E) é uma estrutura formaada por 2 conjuntos finitos V e 
E(ou A), onde V é um conjunto finito de pontos (chamados de vértices de 
G) e E é um conjunto de subconjuntos de V de 2 elementos cada 
(chamados de arestas de G)
	 	 
	 obs 1: Se os elementos de E forem pares ordenados, o grafo é 
	 orientado ou dígrafo e os elementos de E são chamados de arcos.
	 obs 2: Uma aresta que une um vértce a ele mesmo é chamado de laço.
Ex. a) G (V, E)
	 	 V = {A, B, C , D}
	 	 E = {{A,B}, {A,C}, {B,B},{B,D}, {C,D}}
obs. Um grafo pode ser representado pela sua matriz de adjacência 
definida da seguinte forma:
	 Seja G(V,E) com |V| = n. Se A é a matriz de adjacência de G não 
	 orientado, então A é quadrada de ordem n e:
	 Se G for orientado então: 
Ex. b) apresente uma configuração geométrica para o grafo cuja matriz de 
adjacência é:
Ex. c)Se {x, y} E, diz-se que os vértices x e y são vizinhos ou adjacentes.
O grau de um vértice, d(v), é o numero de vizinhos que possui contando 
os laços em dobro.
Ex. a)
Ex. b)
Quando G é orientado, conta-se o grau de entrada, d (v), e o grau de saída, 
d (v) de cada vértice.
	 Ex. c)
Ex. d) Represente 2 grafos distintos de 4 vértices, todos de grau 2
Ex. Represente um grafo de 5 vértices com a seguinte distribuição de 
graus: (2, 2, 3, 3, 3)
Idem, para (2, 2, 2, 3, 3)
Obs: não existem grafos com numero impar de vértices de grau impar
Se um grafo existe pelo menos um par de vértices unido por mais de 
uma aresta o grafo é dito multigrafo.
	 Ex.
Um grafo simples é um grafo sem laços e que não é um multigrafo 
	 Ex.
Um grafo é k-regular (ou regular de grau k) se todos os vértices tem 
grau k
	 Ex.
Um grafo completo é um grafo simples onde todo par de vértices é 
unido por uma aresta.
	 Ex
Um grafo bipartido é um grafo onde existe uma partição do 
conjunto V de vértices em 2 subconjuntos X e Y, ou seja:
Ex.
Uma seqüência de vértices (v , v ,..., v ), de modo que {v , v } E é um 
caminho e G de comprimento j - 1. 
Se o vértice final é igual ao inicial diz-se que o caminho é fechado.
Se o caminho não repete vértices, diz-se que o caminho é simples.
Se o caminho só repete o vértice final igual ao inicial, diz-se que o caminho é 
um ciclo.
(1, 2, 3, 2, 5) é um caminho de comprimento 4
(1, 2, 3, 2, 1) é um caminho fechado
(1, 2, 3, 4, 5) é um caminho simples
(2-3-4-5-2) é um ciclo
Um grafo é conexo se todo par de vértices é ligado por um caminho. Caso 
contrario é não conexo.
Uma árvore é um grafo conexo sem ciclos
	 Se G é arvore com n vértices então G tem n-1 arestas.
	 Acrescentando-se uma aresta em uma árvore obtem-se
	 um grafo com ciclo.
	 Retirando-se uma aresta de uma árvore, obtem-se 
	 um grafo não conexo.
	 Numa árvore, qualquer par de vértices está ligado por 
exatamente um caminho.
Uma floresta é um grafo não conexo onde cada componente conexa é uma 
árvore.
26/04/2012
Aula 6
Seja G(V, A) um grafo.
Diz-se que H(V', A') é um subgrafo de G se V' V e A' A
Se V' = V e A' = A diz-se queH(V', A') é um subgrafo gerador de G(V, AO)
Ex. G(V, A) 
Ex Mostre por indução que se G é um grafo então a soma dos graus de 
todos os seus vértices é um número par.
Indução sobre o número de arestas m do grafo
i) caso base (m=0)
Num grafo sem arestas, todos os vértices tem grau zero, assim, a soma 
dos graus de todos os seus vértices ee zero - que é par.
ii) passo indutivo
Hipótese da indução (HI) Suponha que num grafo com m arestas, a 
soma dos graus de todos os seus vértices seja par.
Seja G(V, A) um grafo com m + 1 arestas, e seja a = {u, v} uma aresta 
qualquer de G.
Seja G'(V', A') um subgrafo de G tal que V' = V e A' = A \ {a} 
Assim G' é um grafo com m arestas pela HI, a soma dos graus de todos os 
vértices de G' é um número par.
Acrescentando a aresta a em G', incrementa-se de 2 unidades a soma dos 
graus de seus vértices (uma para cada vértice extermo da aresta ao) 
obtendo-se um grafo G cuja soma dos graus de seus vértices é par.
Ex. Mostre por indução que se G é um grafo então a soma dos graus de 
todos seus vértices é um número par.
Indução sobre o número de arestas m do grafo.
i) caso base (m=0)
Num grafo sem arestas, todos os vértices tem grau zero, assim, a soma 
dos graus de todos seus vértices é zero - que é par.
ii)passo indutivo
Hipótese da indução (HI) - suponha que num grafo com m arestas, a 
soma dos graus de todos seus vértices seja par.
Seja G(V, A) um grafo com m + 1 arestas, seja a = {u, v} uma aresta 
qualquer de G.
Seja G'(V', A') um subgrafo de G tal que V = V' e A = A' \ {a}
Assim G' é um grafo com m arestas pela HI, a soma dos graus de 
todos os vertices de G' é um numero par.
Acrescentando a aresta a em G', incrementa-se 2 unidades a soma 
dos graus de seus vértices (uma para cada vértice extermo da 
aresta a) obtendo-se um grafo G cuja soma dos graus dos seus 
vértices é par.
Teorema de FESTINGER
Seja G(V, A) um grafo, A = (a ) sua matriz de adjacência e A = (a ) a 
K-ésima potência de A.
Nestas condições, o elemento a da matriz A indica o numero de 
caminhos de comprimento k que existem do vértice i ao j em G.
Indução sobre k
i) caso base
Para k = 1, o teorema vale já que a =1 indica que existe a aresta {i, j} em G 
que é um caminho de comprimento 1 do vértice i ao vértice j e a = indica 
que {i, j} A, ou seja, não existe caminho de comprimento 1 de i a j.
ii) HI - Suponha que a indica o numero de caminhos de comprimento k 
do vértice i ao j em G
Para cada valor de p onde 		 	 	 , tem-se uma aresta {i, p} que será 
adicionada, no início, a todos os caminhos de comprimento k existentes de 
p a j.
Logo, para cada valor de p tem-se todos os caminhos de i a j que passam 
pela aresta {i, p}.
O somatório desses caminhos para todo p determina então o total de 
caminhos de comprimento k + 1 entre i e j dado por a 
quantos caminhos de comprimento 3 
existem em G saindo do vértice 1 e 
chegando no vértice 4?
Questão 3 - lista 3
Q 4 - lista 3