Lista4-MO405

Prévia do material em texto

Lista de Exercícios 4 - MO405
Resolução:
Resolução:
Aqui ainda podemos destacar mais um caso. Na resolução acima, estamos falando de grafo euleriano, que contém uma trilha euleriana fechada; e a pergunta é sobre se ter uma trilha de Euler. Segundo o corolário visto em aula, um grafo conexo G contém uma trilha euleriana se e somente se tem exatamente dois vértices de grau ímpar (que são os extremos da trilha T).
Além disso, como estamos falando de Kn, então todos os vértice tem grau (n-1). O único caso que se encaixaria no caso do corolário, seria o K2.
Verdadeiro, pois a trilha euleriana especifica é uma trilha fechada (vn = v0). Sendo assim, estamos lidando com um circuito euleriano em G, então o número de arestas incidentes a vi é par para i.
Resolução:
Resolução:
Resolução:
Qualquer grafo conexo G é um 1-conexo ou 1-aresta-conexo, porque é preciso um ou mais vértices/arestas para desconectá-lo e não é possível desconectá-lo com 0 vértices/arestas. Em outras palavras, para qualquer corte S de G, são necessários pelo menos 1 vértice/aresta no conjunto de corte para G\S ser desconexo.
	
1-conexo são grafos conexos que possuem articulação (K2 ‘conexo, mas nao se desconecta ao remover um vértice)
	1-aresta-conexo são os grafos conexos com uma ponte
Resolução:
2-conexos: 
G é conexo e _não_ tem vértice de corte (c.c. 1 vértice desconectaria G) ou;
Para todo u,v V(G), existe um caminho internamente disjunto entre u e v ou;
Para todo u,v V(G), existe um ciclo entre u e v ou;
1 e a cada par de arestas a,b E(G) há um ciclo comum.
2-arestas-conexos:
Como K(G) <= K’(G):
G é conexo e não tem ponte (c.c., uma aresta desconectaria G) ou;
Para todo u,v V(G), existe um caminho int. disjunto entre u e v ou;
Para todo u,v V(G), existe um ciclo entre u e v ou;
1 e a cada par de arestas a,b E(G) há um ciclo comum.
Resolução:
Teorema 2.3: Uma aresta w E(G) = uv tal que u,v V(G) não é de corte se e somente se não pertence a nenhum ciclo.
Resolução:
Seja H o grafo obtido retirando-se k - 1 arestas.
H é conexo, pois G é k-aresta-conexo. Além disso, H pode conter uma aresta de corte uv (se tivermos retirado K’(G) - 1 arestas que pertencem ao corte de arestas de cardinalidade K’(G)).
Logo C(H) = 1.
Ao retirarmos mais uma aresta, temos duas opções:
Aresta de corte: C(H\a) = C(H) + 1 = 2
Caso contrário: C(H\a) = C(H)
Logo, C(G[E(G)\S] 2.
Resolução:
Para k = 1, o exemplo é K1,3 que, ao retirarmos o vértice que fica isolado em uma partição, temos 3 componentes conexos.
Para k = 2. Vale o mesmo para K2,3.
Para k 3, devemos ter grafos bipartidos com uma partição com |X| k elementos e outra com |Y| k elementos.
Resolução.
Precisamos de k arestas para desconectar o grafo.
Além disso, K’(G) = k (G).
d(v) k (para qualquer vértice)
 d(v) = 2m ⇒ m .
Resolução:
*A proposição é “Se G é um grafo simples e |[S, S]| < (G) para algum subconjunto próprio S de V(G), então |S| > (G).
Resolução:
dH(v) = dG(v) - (k-1)
Dado o enunciado, então: dH(v) . Logo, dH(v) .
Sendo assim, os conjuntos Hi , i={1, 2} tem no mínimo elementos.
|V(G)| = |H1| + |H2| + |S| = V(G) 
Contradição!
Resolução: