MO405 - Ata de Exercícios - 2002-09-04
Modificada: --
Ata dos Exercícios - Resolvidos na aula do dia 2002-09-16
Gilberto Zonta Pastorello Junior ra992880
==> (3.1.1)
^^^^^^^
Considerando a seguinte numeração dos vértices: a partição de cima primeiro,
crescente da esquerda para a direita.
(a) CV = {3, 4, 7}
M = {(1,7), (3,5), (4,6)}
(b) CV = {4, 7, 8}
M = {(1,7), (2,8), (4,6)}
(c) CV = {2, 4, 7, 9}
M = {(1,7), (2,6), (3,9), (4,10)}
==> (3.1.2)
^^^^^^^
O tamanho mínimo de um emparelhamento maximal de um ciclo Cn é dado pela expressão:
TETO(n/3), n >= 3
onde n é o núm de vértices de Cn,
e TETO(z) é a função que dá o menor inteiro maior ou igual a z.
Para mostrar a validade da fórmula, basta pensar que todo n pode ser
escrito como (3x), ou (3x - 1) ou (3x - 2). E para um dado x, x >=1,
um ciclo Cn tem um emparelhamento maximal com x arestas (seja n=(3x),
ou n=(3x-1), ou n=(3x-2) ). Basta pegar as arestas tentando deixar
duas livres para cada uma escolhida.
==> (3.1.8)
^^^^^^^
Prova por indução de que, para toda árvore (T) :
(i) T tem no máximo um emparelhamento perfeito (MP).
Base: número de vértices é 1, e T não tem emparelhamento perfeito (ou 0
emparelhamentos, o que é menor que um!)
H.I.: (i) vale para árvores com n-1 ou menos vértices
P.I.: se o número de vértices é n:
Escolhe-se uma folha (f) e o pai (p) dessa folha (pode-se enxergar p
como uma "nova" raiz dessa árvore, para facilitar a visualização);
- se a aresta fp não está no emparelhamento, então ele não é
perfeito. (Já que não há outra forma de se cobrir f).
- se a aresta fp está no emparelhamento, removemos os nós f e p;
o que resta são as sub-árvores que eram filhas de p; e pela H.I.
elas obedecem a pripriedade (i).
O número de emparelhamentos perfeitos da árvore com n vértices
é igual ao produto do número de emparelhamentos perfeitos das
das sub-árvores filhas de p (exceto f). Como cada um deles vale
0 ou 1, o produto só pode ser 0 ou 1, provando (i) para toda árvore T.
==> (3.1.18)
^^^^^^^^
(i) se G tem MP:
(obs: se G tem MP, então o número de vértices é par)
Estratégia: J2 escolhe sempre u tal que uv pertence ao MP,
onde v foi o vertice escolhido na última jogada de J1.
(1) J1 escolhe um vértice v saturado (todos vértices são);
(2) J2 deve escolher u, tal que a aresta uv pertence ao MP;
(3) Se J1 não tem mais onde jogar, J2 foi o último a jogar, o número de
vértices escolhidos é par (J2 jogou em segundo, quarto, ...),
então J2 venceu;
(4) Se J1 pode jogar, tudo se passa como se o grafo agora
tivesse os vértices v e u removidos. Como uv estava no MP, a
novo grafo continua podendo usar o MP sem a aresta uv, e
volta-se ao passo 1.
(ii) se G não tem MP:
(1) J1 escolhe um emparelhamento máximo M;
(2) J1 escvolhe um vértice v não saturado por M;
(3) Se J2 não tem um vértice para escolher, perdeu. Se não, J2 escolhe,
obrigatoriamente, um vértice u saturado por M (se não fosse saturado
então a aresta vu poderia se adicionada a M, aumentando o conjunto,
contrariando a hipótese de que M é um emparelhamento máximo);
(4) J1 escolhe um vértice w, tal que a aresta uw faz parte de M
(5) Se não existe um vértice t conectado a w, J2 perde. Se t existe, então
t é saturado por M (pois, caso não fosse, o caminho vuwt seria aumentante,
e M não seria máximo).
(6) J1 volta a escolher um vértice s, tal que a aresta ts esteja em M (e tal
vértice existe pois é necessário para que t seja saturado).
(7) Volta-se ao passo (5), e como o que está se formando é um caminho alternante,
e ambas as extremidades desse caminho não podem ser insaturadas, o caminho
termina em um vértice saturado p vindo de outro vértice saturado q tais que
a arersta pq é a última do caminho.