MO405 - Atas - 2002-09-04

Modificada: --

Ata - Aula do dia 2002-09-04
Gilberto Zonta Pastorello Junior  ra992880

Nota do instrutor: concentrem-se nos PONTOS PRINCIPAIS

PONTOS PRINCIPAIS
^^^^^^ ^^^^^^^^^^ 

-->  Emparelhamento
	Def(livro): Um *emparelhamento* em um grafo em um grafo G é um 
	      	conjunto de arestas, que não são loops, e sem extremos
	      	em comum.

-->  Vértices saturados/insaturados: 
	Def:  	Dado um grafo G e um emparelhamento M em G, se um vértice 
              	pertence a M (é um vértice de uma das arestas de M), então
	      	v é *saturado*. Se v não pertence a M, então v é *insaturado*.

-->  Emparelhamento perfeito:
	Def:  	Um emparelhamento M em um grafo G é um *emparelhamento perfeito*
		se todos os vértice de G pertencem a M.

-->  Emparelhamento Maximal:
	Def: 	Um emparelhamento M em um grafo G é *maximal* se NÃO é possível 
		acrescentar nenhuma outra aresta de G em M, mantendo M um emparelhamento.

-->  Emparelhamento Máximo:
	Def:	Um emparelhamento M em um grafo G é *máximo* se NÃO há um emparelhamento
		M' em G que seja maior que M (ou seja, que tenha mais arestas que M).

-->  Diferença Simétrica:
	Def:	Dados os grafos G e H com o mesmo conjunto de vértices V, a 
		*diferença simétrica* GH é o grafo com conjunto de
		vértices V, e arestas que estão em E(G) XOR E(H), ou seja, estão
		em G ou H, mas não em ambos.
			
-->  Caminho M-alternante:
	Def:	Um caminho é *M-alternante* em um grafo G com emparelhamento M 
		se sua seqüência de arestas é um revesamento de arestas, uma em M e 
		uma não em M. 

-->  Caminho M-aumentante:
	Def:	Um caminho é *M-aumentante* em um grafo G com emparelhamento M se é
		um caminho M-alternante e seus dois extremos são insaturados.

-->  Teorema de Hall (Emparelhamento de Hall):
	Teo:	Um grafo bipartido com bipartições X e Y, tem um emparelhamento que 
		satura X se, e somente se, |N(S)| >= |S| para todo S contido em X.		

-->  Conto de Merlin e Rei Artur (i)
	Era uma vez, em um reino muito distante chamado Camelot... um rei chamado Artur
	que tinha como conselheiro o sábio Mago Merlin. Artur um dia se viu com um 
	problema grave, queria casar seu cavaleiros com a damas da corte para que todos 
	pudessem viver felizes para sempre em Camelot. Então Artur fez uma lista que dizia 
	qual cavaleiro era compatível com quais damas e vice-versa, de acordo com as 
	preferências de ambos os grupos. 
	
	Entregou essa lista a Merlin para que o Mago achasse um casamento para todos os
	cavaleiros e damas de Camelot. Como Merlin era sábio (e podia prever o futuro), ele
	conhecia o teorema de Hall. Então sabia que se ele achasse um subconjunto de cavaleiros
	(ou damas) cujo número de pretendentes fosse menor que o número de cavaleiros (ou damas)
	no subconjunto, não haveria um emparelhamento para esses dois conjuntos e nem para a dada 
	lista.

	E foi feito. Ele encontrou tal subconjunto e exibiu-o como contra-exemplo a Artur, que se
        convenceu. Merlin só conseguiu se safar dessa e convencer Artur porque o contra-exemplo
	era suficientemente pequeno (não era possível listar todas as possiblidades, por causa 
	do grande número de cavaleiros de Camelot). Ou seja, em linguagem menos arcaica, há
	um *certificado curto* originado do Teorema de Hall.

-->  Conto de Merlin e Rei Artur (ii)
	No mesmo reino e entre as mesmas pessoas, surgiu um novo problema. Alguns dos cavaleiros
	não se davam bem, e sempre havia brigas na hora do jantar. Artur, como um bom rei, queria
	acabar com tais brigas. 

	Propôs, então, a Merlin, o problema de encontrar uma disposição na mesa de tal forma
	que dois cavaleiros que não se dão bem não se sentem lado a lado na mesa. Merlin, novamente
	usando sua bola de crital para ver o futuro, percebeu que o problema era o mesmo de se 
	achar um Caminho Hamiltoniano em um grafo. E, como vamos ver logo em aulas próximas,
	se não há um Caminho Hamiltoniano em um grafo, não há como construir um certificado
	sucinto (ou curto) para mostrar que não há. Com isso Merlin foi jogado na masmorra até
	que conseguisse uma solução ou mostrar porque não havia solução...


--> Cobertura por Vértices:
	Def:	Uma *cobertura por vértices* (ou CV) de um grafo G, é um 
		subconjunto de V(G) tal que todas as arestas de G são 
		tocadas por um dos vértives da CV.

-->  Teorema Min-Max (ou Teorema de König-Egerváry)
	Teo:	Em grafos bipartidos, o tamanho do emparelhamento máximo é igual 
		ao tamanho da cobertura de vértices mínima.

-->  OBS: Em grafos genéricos o Teorema Min-Max não vale.


OUTROS PONTOS
^^^^^^ ^^^^^^

-->  Cobertura por Arestas:
	Def:	Uma *cobertura por arestas* em um grafo G, é um conjunto L tal que
		todo vértice de G é incidente a alguma aresta de L.

-->  Conjunto Independente:
	Def:	Um *conjunto independente* em um grafo G é um sobconjunto CI de V(G)
		tal que nenhum par de vértices desse tem uma aresta em comum.

-->  Definições de números úteis:

	- tamanho máximo de um conjunto independente:	alfa(G)
	- tamanho máximo de um emparelhamento:		alfa'(G)
	- tamanho mínimo de um cobertura de vértices:	beta(G)
	- tamanho mínimo de uma cobertura de arestas:	beta'(G)

-->  Corolário 3.1.13:
	Para k > 0, todo grafo bipartido k-regular tem um emparelhamento perfeito. 

-->  Lemma 3.1.21:
	Em um grafo G, S contido em V(G) é um conjunto independente se, e somente se,
 	o complemento de S em relação a V(G) é uma cobertura por vértices. E portanto
	alfa(G) + beta(G) = n(G).

-->  Teorema 3.1.22:
	Se G é um grafo sem vértices isolados, então alfa'(G) + beta'(G) = n(G).

-->  Corolário 3.1.24:
	Se G é u grafo bipartido sem vértices isolados, então alfa(G) = beta'(G).