Dúvida na terafa 8

Dúvida na terafa 8

por Luiz Alberto Hespanha -
Número de respostas: 1
Pessoal,

eu resolvi o exercício da Tarefa 8 de uma maneira diferente da mostrada em aula, e queria entender aonde eu errei.

Eu comecei citando a definição do teorema de Hall que diz que, em um grafo bipartido G = (V U(união) W, E) existe um emparelhamento que satura todo vértice de V, se e somente se |N(A)| >= |A| para todo A C(contido) V.

O enunciado fala que X é uma parte de U e Y é uma parte de W e existe um emparelhamento que satura X e um emparelhamento que satura Y.

Como existem tais emparelhamentos, a propriedade citada acima do teorema de Hall é verdade tanto para X quanto para Y. Com isso, eu conclui que existe um emparelhamento que satura X U Y, porque se não existisse tal emparelhamento, X ou Y não satisfariam a condição do teorema de Hall citada e não existiria o emparelhamento M ou N.

Bom, pela nota eu vi que eu errei! sorriso Se alguém pudesse me mostrar aonde tá a falha da minha prova.

Valeu pessoal!
Em resposta à Luiz Alberto Hespanha

Re: Dúvida na terafa 8

por Paulo Feofiloff -
> Eu comecei citando a definição do teorema de
> Hall que diz que, em um grafo bipartido
> G = (V U(união) W, E)

Deveria ser "U união W" e não "V união W".

> existe um emparelhamento que satura todo
> vértice de V, se e somente se |N(A)| >= |A|
> para todo A C(contido) V.

> O enunciado fala que X é uma parte de U

Observe que X é parte de UM DOS lados da
bipartição.

> e Y é uma parte de W e existe um
> emparelhamento que satura X e um
> emparelhamento que satura Y.

> Como existem tais emparelhamentos, a
> propriedade citada acima do teorema de Hall
> é verdade tanto para X quanto para Y.

O que não garante, nem de longe, que seja
verdade para X união Y.

> Com isso, eu conclui que existe um
> emparelhamento que satura X U Y, porque
> se não existisse tal emparelhamento,
> X ou Y não satisfariam a condição do teorema
> de Hall citada

Não é verdade, pois X união Y não está
de um só lado da bipartição.