Matematica Discreta: Resumo - P3

Prévia do material em texto

P3 10/05/2012
Aula 1
Grafos Eulerianos
Seja G(V,A) um grafo conexo. Diz-se que G é euleriano se é possível 
percorrer todas as arestas de G passando uma única vez por cada uma 
delas e retornando ao vértice inicial, nestas condições diz-se que G é um 
ciclo euleriano.
Quando G não tem um ciclo euleriano mas é possível percorrer todas as 
suas arestas passando uma única vez por cada uma delas mas começando 
em v e terminando em v (v = v ), diz-se que G admite um caminho 
euleriano.
Se G é um grafo conexo onde todos os vértices tem grau maior ou igual a 2, 
então G tem um ciclo
Teorema de Euler
Se G é conexo com todos os vértices de grau par então G é um grafo 
euleriano.
Se G é conexo com exatamente 2 vertices de grau impar u e v, então G 
admitem um caminho euleriano que começa em u e termina em v
Indução sobre o numero de arestas m de G
i) m = 1 Como G é conexo, então 
	 a. G tem 2 vértices, ambas de grau 1, é um caminho euleriano em G
	 b. ou G tem um vértice de grau 2, é um cico euleriano em G
ii) Hipótese Indutiva
Suponha que um grafo conexo tenha m arestas
	 Caso I- Se todos os vértices tem grau par, então existe um ciclo 
euleriano em G começando e terminando em qualquer vértice.
	 Caso II- Se exatamente 2 de seus vértices tem grau ímpar então 
existe um caminho euleriano em G que começa em um dos vértices e 
termina em outro
Seja Q um grafo com m+1 arestas
	 Caso I- Todos os vértices de G tem grau par, neste caso devemos 
mostrar que é possível formar um ciclo	 	 	 	 	 	 	 	 	 	 euleriano partindo de 
qualquer vértice de G. 
Seja v um vértice qualquer de G, e sea w um vizinho de v.
Seja G'(V', A') um subgrafo de G tal que A'=A \ {v, w}
	 	 	 	 	 	 	 	 	 V'=V
Note que em G' todos os vértices te o mesmo grau que tinham em G, 
exceto v e w. que tiveram seus graus diminuídos de uma unidade. 
Assim G' tem exatamente 2 vértices de grau ímpar e pela HI - caso II, G' 
admite caminho euleriano que começa em v e termina em w. Se 
considerarmos a aresta {v, w} em G', teremos um grafo com m+1 
arestas com um ciclo eueriano
d(A) = 2
d(B) = 2
d(C) = 6
d(D) = 4
d(E) = 4
d(F) = 4
d(G) = 4
Como todos os vertices tem Grau par o grafo é 
Euleriano 
Como achar ciclos eulerianos no grafo?
	 	 C = (A-G-C-B-A)
	 	 C = (G-F-E-D-C-G)
	 	 C = (F-E-D-C-F)
ciclo euleriano:
(A-G-F-E-D-C-F-E-D-C-G-C-B-A)
15/05/2012
Aula 2
Grafos Hamiltonianos
Um grafo G admite um ciclo hamiltoniano se existe em G um ciclo que 
passa uma única vez por todos os vértices de G (e retorna ao vértice 
inicial, claro). Neste caso, diz-se que G é um grafo hamiltoniano.
Se G não tem ciclo hamiltoniano mas admite um caminho que passa 
uma única vez por todos os vértices de G, diz-se que G tem um caminho 
hamiltoniano. 
Ex. 
Ex. Seja G(V, A) conexo com |V|= n |A|= m. Nestas condições:
-Um caminho hamiltoniano em G tem comprimento:
-Um ciclo hamiltoniano em G tem comprimento:
-Um caminho euliriano em G tem comprimento:
-Um ciclo euliriano em G tem comprimento:
obs. vértice de grau 1 
nunca terá um ciclo 
hamiltoniano, pois só tem 
uma porta de entrada/
saída
Ex. Decida, justificando, se os grafos a seguir são hamiltonianos:
G1 não é euleriano ( vértice de grau ímpar)
G2 é euleriano (todos os vértices tem grau par)
G1 é hamiltoniano (A-B-C-D-E-A)
G2 não é hamiltoniano, pois não é possivel 
completar um ciclo sem passar 2 vezes em 
um mesmo vértice.
Ex. Dê um exemplo de um grafo Hamiltoniano e Euleriano
Ex. Dê um exemplo de um grafo que não é Hamiltoniano nem Euleriano
**qualquer grafo que tenha um vértice grau 1**
(mas admite um ciclo hamiltoniano)
Exercicio
Seja G um grafo completo com 6 vértices
a. Determine o número de arestas de G
b. Determine o número de caminhos de comprimento 4 em G que não 
repetem vértices. E de comprimento 3?
c. Determine o número de caminhos de comprimento 4 em G que não 
repetem arestas.
seja A o primeiro vértice do caminho
seja B o segundo vértice do caminho
seja C o terceiro vértice do caminho
(agora posso ir pro A ou pra um D qualquer)
se o A for o quarto vértice do caminho, 
O quinto vértice será um D qualquer
se o D for o quarto vértice do caminho, 
O quinto vértice pode ser o A ou o B de novo, 
ou um C qualquer
d. G é Euleriano?
e. G é Hamiltoniano?
não, todos os vértices tem grau ímpar
sim, A-B-C-D-E-F-A
f, Moster por indução que se G é completo então G tem n(n-1) arestasf. Mostre
f. Mostre por indução que se G é completo então G tem n(n-1) arestas
Double-Tap to EditSuponha que um grafo G completo com n vértices tem n(n-1) 
vértices
Seja v um vértice qualquer de G, logo d(v) = n
Seja G' = (V', A') com V' = V\{v} e A' = A\{(v, v), } observe que |
V'| = n e |A'| = |A| - n
Assim G' é um grafo completo com n vértices e pela hipótese 
indutiva tem n(n-1) arestas.
Recolocando v em G' de modo a ter um grafo completo, 
acrescenta-se n arestas a G' e então
 m = n(n-1) + n = n(n-1) + 2n = n(n-1+2) = n(n-1)
22/05/2012
Aula 3
Uma árvore é um grafo conexo sem ciclos.
Se G(V,A) é uma árvore com n vértices então:
	 a) G tem m = n-1 arestas
	 
	 b) G'(V',A') com V'=V e A'=A - {a} é um grafo desconexo (logo não é 
	 árvore) com duas componentes conexas que são árvores
	 
	 c) G'(V',A') com V'=V e A'=A {a} é um grafo com ciclo (logo não é 
	 árvore)
	 
	 d) Existe um único caminho entre quaisquer 2 vértices de G
	 
	 e) G tem vértice de grau 1
Mostre por indução que se G é uma árvore com n vértices então G tem 
n-1 arestas
i) caso base n=1
	 m = 1 - 1 = 0 arestas OK
ii) Suponha que toda árvore com n k vértices e tenha n - 1 arestas
	 Seja G(V, A) uma árvore com n + 1
	 Seja G'(V', A') com V' = V e A' = A - {a} um subgrafo de G.
	 Observe que G' tem duas componentes conexas que são árvores 
cada uma delas com no máximo n vértices
(exceto a árvore de 1 vértice)
	 Sejam G e G essas componentes tais que G tem n vértices e G 
tem n vértices, n + n = n + 1. Pela hipótese indutiva, G' tem n -1 + n 
-1 = n + n -2 = n - 2 arestas
	 Acrescentando-se a aresta a, tem-se um grafo com n - 1 vértices e 
n - 2 + 1 = n - 1 arestas
+ 1 - 2 arestas
Grafos Valorados
Diz-se que um grafo G(V,A) é valorado se existe uma função f: A	que 
associa a cada aresta {i, j} de A um número real chamado de peso ou custo 
da aresta {i, j} e normalmente indicado por P ou P(i, j).
Sua matriz de adjacência é tal que
que
Seja G(V, A) um grafo conexo valorado.
Diz-se que H(V',A') é uma árvore gerada de peso mínimo de G se V' = V, A' 
A, H é árvore e a soma dos pesos de todas as arestas de A' é o menor 
possível
H é árvore geradora de G mas 
não é de peso mínimo P(H ) = 10
H é árvore geradora de peso
mínimo de G, P(H ) = 5
Os algoritmos de KRUSKAL e PRIM constróem árvores geradoras de 
peso mínimo a partir de um grafo G conexo valorado
Algoritmo de Kruskal
Entrada: grafo conexo valorado G(V, A), |A| = m
1) Construa uma floresta F onde cada componente é um vértice de G
2) Construa um conjunto S com as arestas de ordinadas pela ordem 
não decrescente de seus pesos. 
3) Para i variando de 1 a m
	 3a) Se a i-ésima aresta de S, conecta duas árvores distintas de F
	 então: retire-a de S acrescente-a em F
	 senão: retire-a de S descarte-a
Saída: árvore geradora de peso mínimo
Algoritmo de Prim
EntEntrada: Grafo conexo valorado G(V,A), |V|=n
1) Rotule o conjunto de vértices de G
2) Faça 
3) Faça
4)
 Para i variando de 1 a n-1
	 4a) Escolha uma aresta {i, j} de A de menor peso possível tal que 
i U e j U 
	 4b) Insira j em U; e insira {i, j} em S
Exemplo
KRUSKAL 
PRIM
24/05/2012
Aula 4
Proposição
Se F é uma floresta criada Se F é uma floresta criada pelo algoritmo de KRUSKAL em qualqueretapa 
então existe uma árvore geradora de peso mínimo (AGPM) T que contém F
PROVA
Indução sobre o número s de etapas do algoritmo
i) Etapa zero -> A proposição vale já que nesta etapa F é o conjunto de 
vértices de G, sem arestas, logo qualquer árvore geradora de G, minimal ou 
não, contem F.
ii) Hipotese Indutiva: Suponha que a proposição vale para a floresta F 
construida na etapa s do algoritmo, isto é, existe uma AGPM T, com P(T)=L, 
que contém F. (observe que se T é AGPM de G então qualquer outra árvore 
T' geradora de G tem peso maior ou igual a L).
Seja a próxima aresta escolhida pelo algoritmo na etapa s + 1
	 - Se T então T contém F + na etapa s + 1 FIM
	 - Se T então T + contém um ciclo C. Neste caso, existe uma outra 
aresta do ciclo C que não está em F. Observe que T - + é uma árvore 
geradora de G, e então
já que está em F e não. Assim
de (1) e (2) tem-se que 
então na 
etapa s 1 
existe 
uma 
floresta 
que 
contenha 
este 
com , com certeza T + terá um 
ciclo, então existe uma aresta que 
está no ciclo, mas não está em F, com 
isso T - + é uma árvore geradora de 
peso mínimo L
que
Algoritmo de DIJKSTRA
Seja G um grafo simples conexo dado.
Seja v um vértice pré-determinado de G.
O algoritmo de Dijkstra tem como saída uma árvore geradora de G 
que determina os 'menores' caminhos de v até todos os demais 
vértices de G.
	 obs- D(x) é a 'distância' de x a v
1. Faça H = {v}
2. Faça S = 
3. Para i de 1 a n - 1
	 3a. Escolha {i, j} com i H, j H, e D(v, j) menor possível
	 3b. Insira j em H
	 3c. Insira {i, j} em S
ex. Seja G tal que
Implemente o 
algoritmo de Dijkstra 
em G a partir do 
vértice 6
29/05/2012
Aula 5
DIJKSTRA em dígrafos
Ex. Implemente o algoritmo de Dijkstra a partir do vértice A do grafo dado, 
apresentando a árvore obtida e seu custo.
O problema do Carteiro Chinês
Seja G um grafo conexo valorado. O objetivo é percorrer todas as arestas 
do grafo e retornar ao vértice inicial. Se o grafo é euleriano, o problema 
está resolvido com custo igual a soma dos pesos de todas as arestas de G. 
Se G não é euleriano, então G tem um número par de vértices de grau 
ímpar. Deve-se então 'dobrar' algumas arestas de G. Pretende-se fazer isso 
com o objetivo de minimizar o custo total do grafo G' (euleriano) obtido.
Para tal, basta encontrar os melhores caminhos entre todos os pares de 
vértices de grau ímpar de G e escolher o(s) que tem menor custo total.
O custo de G' será o custo de acrescido dos pesos das arestas do(s) 
caminho(s) dobrado(s).
então tenho que achar o 
menor caminho do 
vértice A ao vértice E, 
pelo dijkstra, e depois 
dobra o valor.
Double-Tap to Editentão vou dobrar o caminho mínimo do A ao E, sendo ele A-M-C-D-E 
(linha pontilhada no desenho)
não foi necessário terminar o algoritmo, pois já achamos o caminho 
que queríamos
Ex. Implemente o problema do Carteiro Chinês no grafo a seguir 
determinando o custo do caminho obtido.
Seja G tal que 
e sabe-se que o menor caminho de 1 a 3 é 11, e de 1 a 6 é 9
31/05/2012
Aula 6
Fluxos em Grafos
	 Seja G um grafo conexo, orientado, valorado onde o peso é aqui 
chamado de capacidade do arco a=(i, j) e notado por C(i, j) ou c ou c .
	 Um grafo com fluxo é uma tripla G(V, E, f) com |V|= n, |E| = m e 									
f = (f , f , f ... f )
	 G deve possuir um único vértice fonte (s), de onde sai o fluxo, e um 
único vértice sumidouro (t), para onde o fluxo se dirige. (Não há perda, 
tudo que entra sai).
	 Todos os vértices de V devem poder ser atingidos a partir de s e 
todos os vértices de V podem atingir t.
	 Para efeito de simplificação, inclui-se no modelo arco (t, s), fictício, 
que acumula todo fluxo que chega em t (f ).
	 Logo, f é o total do fluxo que passa em G. Diz-se que um fluxo é viável 
em G quando satisfaz as seguintes restrições:
1. O fluxo em cada arco não excede a capacidade do arco.
2. Lei de Kirchhoff - Todo fluxo que entra num vértice sai dele.
obs. observe que 2 vale considerando o arco (t, s)
Convenciona-se 
	 O problema do fluxo máximo consiste em encontrar f maior possível, 
respeitando as restrições 1 e 2.
	 Assim, considere um grafo com fluxo dado, que pode inclusive ser 
igual a zero. Se for possível aumentar f , precisa-se encontar em G um 
caminho de s a t de modo que todos os arcos desse caminho não estejam 
'cheios' (diz-se não saturados).
	 Assim, existe um valor de fluxo que pode ser passado por este 
caminho que é exatamente a menor folga enter os arcos do caminho, 
aumentando f .
	 No Ex anterior, S-A-B-T é um caminho de aumento de fluxo com folga 
10.
Corte um Grafo
	 Seja G(V, E, f) um grafo de fluxo.
	 Seja X V tal que s X e t X.
	 Seja X = V - X, ou seja, X X = V e X X = 0
	 Um corte K(X, X) em G é o conjunto de arcos de E que tem 
extremidade inicial em X e extremidade final em X. A capacidade de um 
corte K, cap(K), é a soma das capacidades dos arcos de K.
é de se esperar que o fluxo máximo seja o corte mínimo (capacidade mínima)
Como todos os arcos do conjunto K começam em X (lado de s) e terminam 
em X (lado de t) pode-se concluir que toda unidade de fluxo que atravessa 
G de s a t deverá passar por algum dos arcos de K.
A retirada de todos os arcos de um corte impede o fluxo de ir de s a t. 
Assim, um corte de capacidade mínima é um 'gargalo' do grafo. Só vai 
passar pelo grafo, o fluxo que 'couber' neste corte. Dessa forma, o valor do 
fluxo máximo em G coincide com a capacidade do corte de capacidade 
mínima.
05/06/2012
Aula 5
Grafo de aumento de fluxos ou grafo de folga ou grafo residual
é um grafo G (V,E ) associado a um grafo de fluxo G(V, E, f).
Sua construção depende do fluxo encontrado até o momento e é feito da 
seguinte forma
	 Seja e=(v, w) um arco de G
	 Em G teremos o arco:
	 	 i) e=(v, w) se f < c O valor deste arco é c - f
	 ii) e=(w, v) se f > 0 O valor deste arco é f
Algoritmo de FORD-FULKERSON (obtem o fluxo máximo e o corte mínimo 
de um grafo de fluxo)
	 ENTRADAS: G(V, E, f)
	 	 	 	 c(e) e E
	 	 	 	 f inicial dado (f ) 
	 	 	 	 capacidade corte
	 Enquanto capcorte = f , faça
	 	 1. Construa G
	 	 2. Enquanto existir um caminho de aumento de fluxo de s a t em G
	 	 	 -estabeleça o caminho e sua folga
	 	 	 -introduza o fluxo de s a t
	 	 	 - f f +
	 	 	 -Construa G
3. X vértices atingíveis a partir de s sem G
	 se t X então volte para 2.
	 	 senão capcorte (X, X) f
7
no ex. da aula passada