Hey Gabriel, tudo bem por ai?
Pergunta: Tem como a gente marcar uma monitoria extra na segunda-feira anterior à prova? Não sei como estão os seus horários, mas se fosse possível, acho que seria legal uma reunião na segunda de manhã. Tenho alguns exercícios que queria que você desse uma olhada pra ver se estão certos.
Se der tudo certo, mais pessoas podem aparecer pra fazer isso também. Aposto que os exercícios mais cabeludos são dúvidas comuns pra bastante gente.
Podemos adiantar a monitoria de terça para segunda.
Segunda eu tenho uma aula das 8-10, mas depois disso estou a disposição.
Vocês preferem de manhã ou à tarde?
Segunda eu tenho uma aula das 8-10, mas depois disso estou a disposição.
Vocês preferem de manhã ou à tarde?
De manhã, a tarde eu tenho aulas... A gente pode fazer das 10h15 ~ 12h15
acho que não fica pesado pra ninguém, e talvez a gente até termine antes.
acho que não fica pesado pra ninguém, e talvez a gente até termine antes.
Bom, como ninguém se manifestou por outro horário, acho que marcamos.
Assim que eu sair da minha aula, eu vou para a sala das estações de trabalho. Se muita gente aparecer, procuramos uma sala de aula livre.
Assim que eu sair da minha aula, eu vou para a sala das estações de trabalho. Se muita gente aparecer, procuramos uma sala de aula livre.
Combinado.
Sala das estações no bloco A ou B?
Sala das estações no bloco A ou B?
Tem uma no bloco B?! Não sabia...
Na do bloco A mesmo.
Na do bloco A mesmo.
Me perguntaram hoje alguns exercícios que eu não consegui fazer na hora. Pensei um pouco depois e eles sairam. Vou deixar uma resolução aqui.
E 26.15 Suponha que n(G) é ímpar e m(G) >= \Delta(G) (n(G) - 1) / 2. Calcule \chi^{\prime} (G).
Para simplificar a notação, vou denotar n(G) por n, m(G) por m e \Delta(G) por k.
Do teorema de Vizing (E 26.27), temos que k <= \chi^{\prime} (G) <= k+1, assim se mostrarmos que \chi^{\prime} (G) != k, concluíremos que \chi^{\prime} (G) = k+1.
Por absurdo, suponha que \chi^{\prime} (G) = k. Tome {M_1, ..., M_k} uma coloração mínima das arestas de G, formada por emparelhamentos 2 a 2 disjuntos. Afirmamos que existe i, com i \in {1, ..., k} tal que |M_i| > (n-1)/2. Com efeito, se |M_j| <= (n-1)/2 para todo j em {1, ..., k}, teremos que m = \sum_{j = 1}^k |M_j| <= k (n-1) / 2, o que constradiz a condição do enunciado que diz que m > k (n-1) / 2.
Tome i tal que |M_i| > (n-1)/2. Adote V(M_i) como o conjunto dos vértices saturados por M_i. Assim teremos que |V(M_i)| = 2|M_i| > n-1. Portanto |V(M_i)| >= n. Dessa forma M_i é um emparelhamento perfeito em G, de onde tiramos que n é par, o que contradiz o enunciado do exercício.
E 26.12 Seja H um grafo r-regular, r >= 1, com um número ímpar de vértices. Seja G um grafo obtido de H pela remoção de no máximo (r-1)/2 arestas. Mostre que \chi^{\prime} (G) = \Delta(G) + 1.
Esse sai quase que como corolário do anterior. Observe (mostre!) que:
m(H) = n r / 2
m(G) >= m(H) - (r-1)/2 = r(n-1)/2 + 1/2 > r(n-1)/2
\Delta(G) = r
n(G) é ímpar
Assim, G satisfaz todas as condições do exercício 26.15, portanto \chi^{\prime} (G) = \Delta(G) + 1.
Um último que me perguntaram e eu não consegui fazer foi esse:
E 23.15 Seja G um grafo (U,W)-bipartido. Suponha que |U| = |W| e m(G) > (k - 1) |U| para algum k inteiro positivo. Prove que G tem um emparelhamento de cardinalidade k.
Esse eu ainda não consegui fazer, se alguém tiver alguma idéia, poste aí!
Eu imagino que uma demonstração por indução em k ou em |U| deva funcionar. Mas não consegui chegar em lugar nenhum.
E 26.15 Suponha que n(G) é ímpar e m(G) >= \Delta(G) (n(G) - 1) / 2. Calcule \chi^{\prime} (G).
Para simplificar a notação, vou denotar n(G) por n, m(G) por m e \Delta(G) por k.
Do teorema de Vizing (E 26.27), temos que k <= \chi^{\prime} (G) <= k+1, assim se mostrarmos que \chi^{\prime} (G) != k, concluíremos que \chi^{\prime} (G) = k+1.
Por absurdo, suponha que \chi^{\prime} (G) = k. Tome {M_1, ..., M_k} uma coloração mínima das arestas de G, formada por emparelhamentos 2 a 2 disjuntos. Afirmamos que existe i, com i \in {1, ..., k} tal que |M_i| > (n-1)/2. Com efeito, se |M_j| <= (n-1)/2 para todo j em {1, ..., k}, teremos que m = \sum_{j = 1}^k |M_j| <= k (n-1) / 2, o que constradiz a condição do enunciado que diz que m > k (n-1) / 2.
Tome i tal que |M_i| > (n-1)/2. Adote V(M_i) como o conjunto dos vértices saturados por M_i. Assim teremos que |V(M_i)| = 2|M_i| > n-1. Portanto |V(M_i)| >= n. Dessa forma M_i é um emparelhamento perfeito em G, de onde tiramos que n é par, o que contradiz o enunciado do exercício.
E 26.12 Seja H um grafo r-regular, r >= 1, com um número ímpar de vértices. Seja G um grafo obtido de H pela remoção de no máximo (r-1)/2 arestas. Mostre que \chi^{\prime} (G) = \Delta(G) + 1.
Esse sai quase que como corolário do anterior. Observe (mostre!) que:
m(H) = n r / 2
m(G) >= m(H) - (r-1)/2 = r(n-1)/2 + 1/2 > r(n-1)/2
\Delta(G) = r
n(G) é ímpar
Assim, G satisfaz todas as condições do exercício 26.15, portanto \chi^{\prime} (G) = \Delta(G) + 1.
Um último que me perguntaram e eu não consegui fazer foi esse:
E 23.15 Seja G um grafo (U,W)-bipartido. Suponha que |U| = |W| e m(G) > (k - 1) |U| para algum k inteiro positivo. Prove que G tem um emparelhamento de cardinalidade k.
Esse eu ainda não consegui fazer, se alguém tiver alguma idéia, poste aí!
Eu imagino que uma demonstração por indução em k ou em |U| deva funcionar. Mas não consegui chegar em lugar nenhum.
Ficou um pouco estranho, o enunciado do exercício ficou com um pequeno erro, o correto é m(G) estritamente maior do que (Delta*(n-1))/2.
Acho que há um outro erro em "Afirmamos que existe i, com i \in {1, ..., k} tal que |M_i| > (n-1)/2", não seria exatamente o contrário, ou seja, assumir que NÃO existe tal emparelhamento?
Quanto ao exercício 23.15, me lembro que o professor havia dado uma dica em aula. Mas também não me lembro muito bem... talvez algo relacionado ao teorema de Hall.
Acho que há um outro erro em "Afirmamos que existe i, com i \in {1, ..., k} tal que |M_i| > (n-1)/2", não seria exatamente o contrário, ou seja, assumir que NÃO existe tal emparelhamento?
Quanto ao exercício 23.15, me lembro que o professor havia dado uma dica em aula. Mas também não me lembro muito bem... talvez algo relacionado ao teorema de Hall.
"Ficou um pouco estranho, o enunciado do exercício ficou com um pequeno erro, o correto é m(G) estritamente maior do que (Delta*(n-1))/2."
É mesmo. Errei na hora de digitar, mas durante a resolução eu usei certo.
"Acho que há um outro erro em "Afirmamos que existe i, com i \in {1, ..., k} tal que |M_i| > (n-1)/2", não seria exatamente o contrário, ou seja, assumir que NÃO existe tal emparelhamento?"
É, mas eu fiz a prova por contradição, o que eu fiz foi supor que a coloração mínima de arestas tem cardinalidade Delta e mostrei que isso implicaria que existiria esse M_i, que contradiz o fato de n ser ímpar.
Mas realmente ficaria mais claro se fizesse uma demonstração direta. É o meu vício por provas por contradição.
É mesmo. Errei na hora de digitar, mas durante a resolução eu usei certo.
"Acho que há um outro erro em "Afirmamos que existe i, com i \in {1, ..., k} tal que |M_i| > (n-1)/2", não seria exatamente o contrário, ou seja, assumir que NÃO existe tal emparelhamento?"
É, mas eu fiz a prova por contradição, o que eu fiz foi supor que a coloração mínima de arestas tem cardinalidade Delta e mostrei que isso implicaria que existiria esse M_i, que contradiz o fato de n ser ímpar.
Mas realmente ficaria mais claro se fizesse uma demonstração direta. É o meu vício por provas por contradição.
> E 26.15 Suponha que n(G) é ímpar e
> m(G) >= \Delta(G) (n(G) - 1) / 2.
> Calcule \chi^{\prime} (G).
. . .
> |V(M_i)| >= n. Dessa forma M_i é um
> emparelhamento perfeito em G, de onde
> tiramos que n é par, o que contradiz
> o enunciado do exercício.
Boa!
(Veja as correções do Atol na mensagem seguinte.)
> E 26.12 Seja H um grafo r-regular, r >= 1,
> com um número ímpar de vértices. Seja G um
> grafo obtido de H pela remoção de no máximo
> (r-1)/2 arestas. Mostre que
> \chi^{\prime}(G) = \Delta(G) + 1.
>
> Esse sai quase que como corolário do anterior.
Boa!
> m(G) >= \Delta(G) (n(G) - 1) / 2.
> Calcule \chi^{\prime} (G).
. . .
> |V(M_i)| >= n. Dessa forma M_i é um
> emparelhamento perfeito em G, de onde
> tiramos que n é par, o que contradiz
> o enunciado do exercício.
Boa!
(Veja as correções do Atol na mensagem seguinte.)
> E 26.12 Seja H um grafo r-regular, r >= 1,
> com um número ímpar de vértices. Seja G um
> grafo obtido de H pela remoção de no máximo
> (r-1)/2 arestas. Mostre que
> \chi^{\prime}(G) = \Delta(G) + 1.
>
> Esse sai quase que como corolário do anterior.
Boa!
> E 23.15 Seja G um grafo (U,W)-bipartido.
> Suponha que |U| = |W| e m(G) > (k - 1) |U|
> para algum k inteiro positivo. Prove que G
> tem um emparelhamento de cardinalidade k.
Seja M um emparelhamento máximo e
suponha por um momento que |M| < k.
De acordo com o teorema de König,
G tem uma cobertura K tal que |K| < k.
Logo, m <= |U||K| <= |U|(k-1).
Contradição.
> Suponha que |U| = |W| e m(G) > (k - 1) |U|
> para algum k inteiro positivo. Prove que G
> tem um emparelhamento de cardinalidade k.
Seja M um emparelhamento máximo e
suponha por um momento que |M| < k.
De acordo com o teorema de König,
G tem uma cobertura K tal que |K| < k.
Logo, m <= |U||K| <= |U|(k-1).
Contradição.