Lista8-MO405

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Lista de Exercicio 8
|t*| = piso (n/2). Descobri empíricamente.
Tentei formalizar. Conferir:
Por definição, todo vértice possui n-1 adjacências. Repare que uma aresta w = uv do emparelhamento inviabiliza 2(n-2) arestas. Isso porque o vértice u inviabiliza todas suas n-2 arestas adjacentes e o vértice v inviabiliza todas suas n-2 arestas adjacentes. u e v possuem n-1 arestas, mas uma delas (w) pertence ao emparelhamento (por isso temos n-2)
No entanto, se o emparelhamento tiver mais de uma aresta, deixa de ser 2(n-2) e se torna (n-2) porque arestas serão contadas duas vezes. (tem um bug aqui com n ímpar; nem todas serão contadas duas vezes, mas “é como se fossem”)
|t*| + |t*|(n-2) <= m
|t*| + |t*|(n-2) <= n(n-1)/2
|t*| (1 + n-2) <= n(n-1)/2
|t*|(n-1) <= n(n-1)/2
|t*| <= n/2
piso(n/2) ajusta |t*| para n ímpares.
Prova 1: Eu acho que esse aqui é maximal e não máximo, pois o máximo contém duas arestas, mas é impossível ele contemplar a aresta vermelha
Prova 2: O exemplo que o livro sugere é um P4 com a aresta do meio como emparelhamento maximal. Nesse caso não podemos acrescentar outras arestas, mas não é o emparelhamento máximo (que seria pegar as duas arestas ligadas aos vértices das extremidades).
Falso (contra-examplo) (conferir):
Pendente
Por definição, os vértices de V(G)\X não estão na cobertura, mas suas arestas têm um extremo em algum vértice de X. Se os vértices de V(G)\X não forem independentes, então haveria uma aresta entre dois vértices desse conjunto não cobertas por X, o que contradiz X ser uma cobertura. Portanto, V(G)\X é um conjunto independente. Veja os dois vértices vermelhos que fazem parte da cobertura e a aresta pontilhada que contradiz a cobertura (caso existisse).
C4.
	Grafos bipartidos k-regulares possuem emparelhamento perfeitos: |t| = |k|
C3. Só temos uma aresta no emparelhamento e precisamos de 2 vértices para cobertura.
Supondo que X seja a partição de cima, não há emparelhamento.
Numerando os vértices da esquerda para a direita em X, temos que X’ = {3, 5, 7} é maior do que sua vizinhança N(X’) = {4’, 5’} e, por Hall, não há emparelhamento.
Prova segundo o West:
Let G be a k-regular X,Y-bigraph. Counting the edges by endpoints in X and by endpoints in Y shows that k * |X| = k * |Y| , so |X| = |Y|. Hence it suffices to verify Hall’s Condition; a matching that saturates X will also saturate Y and be a perfect matching.
Consider S X. Let m be the number of edges from S to N(S). Since G is k-regular, m = k * |S|. These m edges are incident to N(S), so m k * |N(S)|. Hence k|S| k|N(S)|, which yields |N(S)| |S|, when k > 0. Having chosen S arbitrarily, we have established Hall’s Condition.
Essa prova foi feita em aula também para provar que todo grafo bipartido k-regular tinha um emparelhamento perfeito.
Resolução:
Sim. Vide figura:
Tentativa 1. Não, pois contem ciclos não-disjuntos. Ou então, não pois contém ciclos com cordas, as quais não podem ser contempladas por outros ciclos.
Tentativa 2 (conferir): Argumentar pelo grau dos vértices. O grau de todos os vértices é 3, então você não consegue fazer subgrafos 2-regulares disjuntos nas arestas.
Pendente.
Resolução:
Igual ao exercício 8, não ? Condição de Hall é satisfeita e como |A|=|B|, o emparelhamento é perfeito (1-fator). Sim, mas usando palavras diferentes, pois a pessoa pode não saber que emparelhamento perfeito implica em 1-fator
Resolução: