Lista1_TGS RESOLVIDA

Prévia do material em texto

Exercício 1
Os turistas Jenssen, Leuzinger, Dufour e Medeiros se encontram em um bar de Paris e começam a conversar. As línguas disponíveis são o Inglês, o Francês, o Português e o Alemão. Jenssen fala todas, Leuzinger não fala apenas o Português, Dufour fala Francês e Alemão e Medeiros fala Inglês e Português. 
1. Represente por meio de um grafo G = (x,u) todas as possibilidades de um turista dirigir a palavra a outro, sendo compreendido. Defina x e u.
2. Defina um subgrafo em que todos falem ao mesmo tempo.
3. A partir do grafo bipartido do item 1) construa um grafo rotulado que mostra quem pode falar com quem em qual língua,
SOLUÇÃO
1. Represente por meio de um grafo G = (x,u) todas as possibilidades de um turista dirigir a palavra a outro, sendo compreendido. Defina x e u.
M
D
L
J
A
P
F
I
 x= {x│x é um turista e uma língua disponível}
 u={(x,y) │x é um turista e y uma língua}.
2. Defina um subgrafo em que todos falem ao mesmo tempo.
M
D
L
J
P
A
F
I
3. A partir do grafo bipartido do item 1) construa um grafo rotulado que mostra quem pode falar com quem em qual língua,
J
 I I P
 F A F AM
 L
 A
 F
D
Exercício 2
Responda as questões que seguem justificando suas respostas:
a) é possível que tenhamos um grafo completo que não seja regular?
b) Considere um grafo no qual: V={x/x é uma pessoa adulta} e A={(x,y)│<x é casada com y>}. Se V tem mais de dois elementos, pode este grafo não ter arestas?
c) como saber se o grafo do item anterior é orientado ou não?
SOLUÇÃO
A) Não é possível, pois em um grafo completo, todos os vértices ligam-se a todos as arestas. Em um grafo completo de n vértices, o grau de cada um dos vértices é (n-1), sendo sempre um grafo regular.
B) O Conjunto de vértices V tendo mais de dois elementos, esse grafo pode não ter arestas, sim. Basta que as pessoas representadas pelos 3 ou mais vértices não sejam casados.
C) Sabe-se da orientação ou não de um grafo, pela relação expressada pelas arestas. No caso, x é casada com y, representa uma relação simétrica, levando o grafo a não ser orientado. O grafo orientado se dá quando da propriedade de não simetria na relação. Se a propriedade fosse x matou y, teríamos um grafo orientado.
Exercício 3
Os agentes A, B, C, D, E, F, G e H são conspiradores políticos. De forma a coordenar seus esforços, é vital que cada agente seja capaz de repassar informações direta ou indiretamente a todos os outros conspiradores. Cada repasse direto de informações, contudo, envolve um certo risco conforme apresentado na tabela que se segue:
	A
	A
	A
	A
	A
	B
	B
	C
	C
	C
	C
	D
	D
	E
	B
	C
	E
	F
	G
	C
	F
	D
	F
	G
	H
	E
	H
	H
	9
	3
	8
	3
	4
	10
	6
	6
	4
	5
	7
	6
	3
	5
 
As comunicações diretas não apresentadas na tabela acima são impraticáveis pois exporiam todo os esquemas de disfarce. Considerando esta descrição:
Apresente uma definição formal de um grafo(G(V,A))para o problema acima
SOLUÇÃO
Um grafo G =(VG1, AG1) consiste de um conjunto finito e não vazio V(G) ou VG|VG1, e uma família finita AG, de pares não ordenados de elementos de VG.
(G(V,A)) onde 
 V= {x│x é um informante conspirador}
 A={(x,y,r) │ x pode (é capaz) de repassar informações diretamente para y, com um risco r}.
Exercício 4
A RCT-SC e’uma rede de computadores que interliga diversas instituições de ensino e de pesquisa de santa Catarina. Algumas conexões entre instituições são a 2Mbps enquanto que outras as a 64 Mbps.
a) apresente uma definição de um grafo G(V,A)) para o problema acima na qual seja considerada a velocidade das conexões.
SOLUÇÃO
Um grafo G =(VG1, AG1) consiste de um conjunto finito e não vazio V(G) ou VG|VG1, e uma família finita AG, de pares não ordenados de elementos de VG.
G(V,A) onde
V={x│x é uma instituição laigada a RCT-SC}
A={ (x,y,v)│x é ligada a y pela RCT-SC com velocidade v}
Exercício 5
 Seja G um grafo no qual os vértices correspondem aos estudantes do Curso de Computação, sendo dois destes vértices adjacentes se e somente se os estudantes estejam cursando pelo menos uma disciplina em comum. O que se pode afirmar sobre este grafo no que se refere a orientação, conexidade deste grafo? Justifique.
 
SOLUÇÃO
Um grafo G =(VG1, AG1) consiste de um conjunto finito e não vazio V(G) ou VG|VG1, e uma família finita AG, de pares não ordenados de elementos de VG.
G(V,A) onde
 V={ v│v é um estudante de computação}
 A={(v1, v2) │v1 e v2 pertencem a V e estão cursando disciplina em comum}
 O grafo é não orientado pois se João cursa teoria dos grafos com Pedro, Pedro também cursa teoria dos grafos com João. (A relação apresentada é simétrica), e o grafo é conexo, pois haverá um cadeia ligando cada par de vértices do grafo.
Ou 
e nada se pode dizer se é conexo ou não, pois nada garante que os alunos da primeira fase, por exemplo, podem estar cursando disciplinas em comum com alunos da segunda fase...
Exercício 6
Admita que relacionamos um grafo G a um grupo de alunos de uma disciplina da Engenharia Elétrica. Os vértices representam os estudantes e são adjacentes se e somente se os estudantes integram à mesma fase. Fundamentando-se nisso responda:
a) Esse grafo é orientado?
b) Esse grafo é conexo?
c) Esse grafo é regular?
SOLUÇÃO
a) Orientação: sem orientação. Pois se João cursa teoria dos grafos com Pedro (na mesma fase), Pedro também cursa teoria dos grafos com João. (A relação apresentada é simétrica), e o grafo é conexo, pois haverá um cadeia ligando cada par de vértices do grafo
b) conexidade: se a turma for composta por estudantes da mesma fase, é conexo, caso contrário, pelo menos um não for da mesma fase, é desconexo.
c) Regularidade: se todos os estudantes forem da mesma fase será regular. Todos os vértices tem o mesmo grau. Caso contrário não será (grafo completo)
Exercício 7
Para o grafo direcionado apresentado a seguir, responda:
a) Qual a matriz de adjacência deste grafo?
b) O que você pode dizer a respeito da soma dos números de qualquer linha dessa matriz?
c) O que você pode dizer a respeito da soma dos números de qualquer coluna dessa matriz?
SOLUÇÃO
a) Qual a matriz de adjacência deste grafo?
A1
	
	1
	2
	3
	4
	5
	6
	7
	SOMA
	1
	0
	1
	0
	0
	0
	1
	0
	2
	2
	0
	0
	1
	0
	1
	0
	1
	3
	3
	0
	0
	0
	1
	1
	0
	0
	2
	4
	0
	0
	1
	0
	0
	0
	0
	1
	5
	1
	0
	0
	0
	0
	0
	0
	1
	6
	0
	1
	0
	0
	0
	0
	0
	1
	7
	0
	0
	1
	0
	0
	0
	0
	1
	SOMA
	1
	2
	3
	1
	2
	1
	1
	
 
b) O que você pode dizer a respeito da soma dos números de qualquer linha dessa matriz? Corresponde ao de arestas EXTERIORMENTE INCIDENTE
c) O que você pode dizer a respeito da soma dos números de qualquer coluna dessa matriz? Corresponde ao de arestas INTERIORMENTE INCIDENTE
Exercício 8
Se dois grafos G e H são isomorfos, então vale a relação:
P A2 PT = A1
Onde: A1 é a matriz de adjacência de G, A2 é a matriz de adjacência de H e P é uma matriz de permutação.
Para os grafos isomorfos G e H acima, encontre as matrizes A1, A2 e P que satisfaçam a relação
 
P A2 PT = A1
SOLUÇÃO
Sejam G1= (V1,E1) e G2 = (V2,E2)
· G1 = G2, se existir uma bijeção f:V1V2
· Se vw é uma aresta de E1, então f(v)f(w) é aresta de E2.
· Toda aresta em E2 tem a forma de f(v)f(w) para alguma aresta vw E1
Encontramos a correspondência é dada por:
f(1) = c, f(2) = d, f(3) = b, f(4) = e, f(5) = a, f(6) = f
	A1
	
	1
	2
	3
	4
	5
	6
	10
	1
	1
	0
	1
	0
	2
	1
	0
	0
	1
	0
	1
	3
	1
	0
	0
	0
	1
	0
	4
	0
	1
	0
	0
	0
	1
	5
	1
	0
	1
	0
	0
	0
	6
	0
	1
	0
	1
	0
	0
	A2
	
	a
	b
	c
	d
	e
	f
	a
	0
	1
	1
	0
	0
	0
	b
	1
	0
	1
	0
	0
	0
	c
	1
	1
	0
	1
	0
	0
	d
	0
	0
	1
	0
	1
	1
	e
	0
	0
	0
	1
	0
	1
	f
	0
	0
	0
	1
	1
	0
	P
	
	a
	b
	c
	d
	e
	f
	1
	0
	0
	1
	0
	0
	0
	2
	0
	0
	0
	1
	0
	0
	3
	0
	1
	0
	0
	0
	0
	4
	0
	0
	0
	0
	1
	0
	5
	1
	0
	0
	0
	0
	0
	6
	0
	0
	0
	0
	0
	1
	PT
	
	a
	b
	c
	d
	e
	f
	1
	0
	0
	0
	0
	0
	0
	2
	0
	0
	1
	0
	0
	0
	3
	1
	0
	0
	0
	0
	0
	4
	0
	1
	0
	0
	1
	0
	5
	0
	0
	0
	1
	0
	0
	6
	0
	0
	0
	0
	0
	1
 
	
	
	A2
	PT
	
	
	a
	b
	c
	d
	e
	f
	a
	b
	c
	d
	e
	f
	
	a
	0
	1
	1
	0
	0
	0
	0
	0
	0
	0
	1
	0
	
	b
	1
	0
	1
	0
	0
	0
	0
	0
	1
	0
	0
	0
	
	c
	1
	1
	0
	1
	0
	0
	1
	0
	0
	0
	0
	0
	
	d
	0
	0
	1
	0
	1
	1
	0
	1
	0
	0
	0
	0
	
	e
	0
	0
	0
	1
	0
	1
	0
	0
	0
	1
	0
	0
	P
	f
	0
	0
	0
	1
	1
	0
	0
	0
	0
	0
	0
	1
	
	a
	b
	c
	d
	e
	f
	 P A2
	 P A2 PT = A1
	1
	0
	0
	1
	0
	0
	0
	1
	1
	0
	1
	0
	0
	0
	1
	1
	0
	1
	0
	2
	0
	0
	0
	1
	0
	0
	0
	0
	1
	0
	1
	1
	1
	0
	0
	1
	0
	1
	3
	0
	1
	0
	0
	0
	0
	1
	0
	1
	0
	0
	0
	1
	0
	0
	0
	1
	0
	4
	0
	0
	0
	0
	1
	0
	0
	0
	0
	1
	0
	1
	0
	1
	0
	0
	0
	1
	5
	1
	0
	0
	0
	0
	0
	0
	1
	1
	0
	0
	0
	1
	0
	1
	0
	0
	0
	6
	0
	0
	0
	0
	0
	1
	0
	0
	0
	1
	1
	0
	0
	1
	0
	1
	0
	0
Exercício 9
Mostre que os dois grafos G1 e G2 abaixo são isomorfos usando a relação 
 
 G1 G2 
SOLUÇÃO
Sejam G1= (V1,E1) e G2 = (V2,E2)
· G1 = G2, se existir uma bijeção f:V1V2
· Se vw é uma aresta de E1, então f(v)f(w) é aresta de E2.
· Toda aresta em E2 tem a forma de f(v)f(w) para alguma aresta vw E1
Encontramos a correspondência é dada por:
Os grafos são isomorfos. Um possível isomorfismo é
 
f(u1) = v1, f(u2) = v9, f(u3) = v4, f(u4) = v3, f(u5) = v2, f(u6) = v8, f(u7) = v7, 
f(u8) = v5, f(u9) = v10 e f(u10) = v6 preserva adjacência.
Por exemplo se {u9 e u7} é uma aresta no grafo G1 com {v10 e v7} a aresta correspondente no grafo G2. Mas como apresentaremos essa correspondência?
Devido ao fato do isomorfismo preservar adjacências, ele preserva as subestruturas tais como caminhos e ciclos. Por exemplo, o ciclo no grafo G1:
(u1,u10), (u10, u7), (u7,u4), (u4,u3), (u3,u2), (u2, u1) comprimento 5
As correspondentes arrestas no grafo G2 também preserva um ciclo de comprimento 5
(v1, v6), (v6, v7), (v7, v3), (v3, v4), (v4,v9, (v9, v1)
P A2 PT = A1 LOGO A MATRIZ DE PERMUTAÇÃO P É:
	
	V1
	V2
	V3
	V4
	V5
	V6
	V7
	V8
	V8
	V9
	V10
	U1
	1
	0
	0
	0
	0
	0
	0
	0
	0
	0
	0
	U2
	0
	0
	0
	0
	0
	0
	0
	0
	0
	1
	0
	U3
	0
	0
	0
	1
	0
	0
	0
	0
	0
	0
	0
	U4
	0
	0
	1
	0
	0
	0
	0
	0
	0
	0
	0
	U5
	0
	1
	0
	0
	0
	0
	0
	0
	0
	0
	0
	U6
	0
	0
	0
	0
	0
	0
	0
	0
	1
	0
	0
	U7
	0
	0
	0
	0
	0
	0
	1
	0
	0
	0
	0
	U8
	0
	0
	0
	0
	1
	0
	0
	0
	0
	0
	0
	U9
	0
	0
	0
	0
	0
	0
	0
	0
	0
	0
	1
	U10
	0
	0
	0
	0
	0
	1
	0
	0
	0
	0
	0
Exercício 10
I. Considere um Grafo G = (V,E) não direcionado sem laço 8-regular. Prove que se |V| = 15 então G tem um ciclo Hamiltoniano.
II. Dê um exemplo de um grafo bipartido não direcionado G(V,E) onde V é particionado em V1 ᵁ V2 e |V1| = |V2| - 1
SOLUÇÃO
a) Sabe-se que se G = (V,E) é um grafo não direcionado e sem laço com |V| = n ˃3, então, se grau(y) + grau(w)≥ n para todos vértices não adjacentes y,w ϵ V, então G contém um ciclo Hamiltoniano.
Nesse caso, uma vez que todos os vértices não adjacentes y,w ϵ V têm grau(y) + grau(w) = 8 + 8 = 16 ˃15 = |V| (TEOREMA DE ORE)
a) Um exemplo de grafo bipartido não direcionado G(V,E) onde V é particionado em V1 ᵁ V2 e |V1| = |V2| - 1. Nesse caso |V1| =3 e |V2| = 4 onde V1 = {a, b, c} e V2 = {d, e, f, g}
 a b c
 d e f g
Exercício 11
I. Explique porque não é possível traçar um grafo simples conexo, não direcionado, com oito vértices, onde os graus dos vértices são 1, 1, 1, 2, 3, 4, 5 e 7.
II. Dê um exemplo de um grafo não simples, conexo, não direcionado, com oito vértices e a sequência de graus 1,1,1,2,3,4,5 e 7.
SOLUÇÃO
I) Sejam (a, b, c, x, y) ϵ V com grau(a) = grau(b) = grau(c) = 1, grau(x)=5 e grau(y) = 7. Uma vez que grau(y) = 7 então y é adjacente a todos os outros sete vértices em V. Entretanto, o vértice x não é adjacente a nenhum dos vértices a, b e c. Como o vértice x não pode ser adjacente a si mesmo, a menos que tenhamos um laço, conclui-se que grau(x) ≤ 4 e não se pode desenhar um grafo nas condições dadas.
II) Neste caso existem várias alternativas que podem ser apresentadas pelos alunos ( é só conferir)
 1 1 1c
b
a
 7y
x
m
j
w
Exercício 12
A RETEL uma rede de computadores que interliga diversas instituições de ensino em Brasília. Algumas conexões entre instituições são de 2Mbps enquanto que outras são de 64 Mbps.
d) Represente formalmente o grafo G(V,A) para o problema acima onde se deve levar em consideração a velocidade das conexões.
e) Redes de computadores como esta tendem a apresentar uma estrutura arbórea, mas em geral não o são. Porque é interessante que a estrutura tenda a ser uma árvore? Qual a consequência (o que se pode dizer) se o grafo resultante da rede de computadores não for uma árvore?
SOLUÇÃO
Um grafo G =(VG1, AG1) consiste de um conjunto finito e não vazio V(G) ou VG|VG1, e uma família finita AG, de pares não ordenados de elementos de VG.
G(V,A) onde
a) V={x│x é uma instituição ligada a RETEL}
 A={ (x,y,v) │x é ligada a y pela RETEL com velocidade v}
b) Pelo custo das ligações. Uma arvore pode, por suas propriedades, ligar todas as instituições entre si proporcionando um custo mais baixo do que se houvesse algum ciclo. Não sendo uma arvore, a rede torna-se mais cara, mas ganha em performance, na medida em que se pode escolher um caminho que esteja menos congestionado para ligar dois computadores. Seguindo esse princípio, pode-se continuar conectado ao resto da rede mesmo com a queda de determinada ligação.
Exercício 13
Seja G o grafo mostrado a seguir. É verdade que a, b, f, g, k é um caminho em G? É verdade que e, a, b, f, c, d é um caminho em G? É verdade que e, a, b, f, g, k, g, i é um circuito em G? É verdade que G contém um circuito de comprimento 6? 
Exercício 14
Para o grafo mostrado a seguir, faça o que se pede com justificativa.
a) Ele é um grafo Euleriano?
b) Ele é um grafo Hamiltoniano?
Exercício 15
Considere o problema a seguir e resolva-o fundamentando-se nos conceitos da teoria de grafos: 
Admita que se tenha as seguintes 15 peças de um jogo de dominó: 
{1,2}, {1,3}, {1,4}, {1,5}, {1,6}, {2,3}, {2,4}, {2,5}, {2,6}, {3,4}, {3,5}, {3,6}, {4,5}, {4,6}, {5,6}, 
Deseja-se saber se é possível enfileirar todas estas peças de forma a fechar um ciclo. A notação {a,b} indica que a peça contém os números a e b.
 Fundamente sua resposta.
RESPOSTA:
Cada peça de dominó será uma aresta e os seus respectivos valores serão os vértices do grafo, sendo assim o valor 1 de uma dada peça deverá ser conectado ao valor 1 de todas as demais peças. Isso vale também para os valores 2, 3, 4, 5 e 6. Procedendo com todas as conexões, teremos o seguinte grafo:
Para enfileirar todas as peças a fim de se formar um círculo, seria necessário que o grafo acima fosse euleriano o que não se observa visto que todos os vértices possuem grau ímpar, logo, não é possível formar um círculo.
Exercício 16
Sabe-se que:
· um grafo é Euleriano se admite um passeio fechado que visita cada aresta do grafo exatamenteuma vez;
· um grafo é Hamiltoniano se admite um ciclo que visita cada vértice do grafo exatamente uma vez.
Determine, os valores de m e n para os quais:
a. o grafo completo Km é Euleriano;
b. o grafo completo Kn é Hamiltoniano;
c. o grafo completo Km,n é Euleriano;
d. o grafo completo Km,n é Hamiltoniano.
SOLUÇÃO
	Para esta questão vamos usar o Teorema de Euler (um grafo conexo é Euleriano se e somente se todo vértice do grafo tem grau par). Condição necessária para um ciclo Hamiltoniano: Se um grafo tem ciclo Hamiltoniano a condição suficiente para ciclo Hamiltoniano se G tem n ≥ 3 e grau (n) ≥ n/2, então G em ciclo Hamiltoniano
a) Como o grafo completo Km é regular de grau m-1, obtemos m ímpar, m ≥ 3
b) Para n ≥ 3 satisfaz a condição suficiente, tem ciclo Hamiltoniano
c) Como o grafo bipartido completo Km,n tem vértices de grau m e de grau n, obtemos m,n pares, m,n ≥ 2 ele é Euleriano.
d) p ≠q não satisfaz a condição necessária. Por outro lado, para m=n, com m,n ≥ 2 satisfaz a condição suficiente
Exercício 17
Prove ou refute cada uma das afirmações:
a) Todo grafo euleriano com um número par de vértices tem um número par de arestas.
b) Todo grafo bipartido que é euleriano tem um número par de arestas.
SOLUÇÃO
a) FALSA. Para refutar, considere o grafo V = {a, b, c, d, e, f}, A = {(a,b), (b,f), (f,c), (c,a), (f,d), (d,e), (e,f).
a
b
f
c
e
d
b) VERDADE. Seja V = XUY a bipartição. Podemos contar o número de 
 arestas assim: m = ∑ d(v) = ∑ d(v) 
 vꞓX vꞓY
Como cada parcela de cada soma é par, a soma é par 
Exercício 18
Tertuliano Gonçalves havia prometido a Josefina das Graças em casamento. O evento deveria ser realizado, segundo ele, assim que acabasse o contrato de trabalho recém assinado com uma empresa encarregada de pavimentar toda a rede de estradas que ligava Santana do Caixa Prego (cidade onde morava Josefina) às cidades da região. O trabalho iria começar na cidade de Rio Largo e prosseguir em continuidade, estrada após estrada, terminando, segundo explicou Tertuliano, em Santana. A rede de estradas é dada pela matriz de adjacência abaixo, na qual a cidade de Santana é representada pelo número 1 e a cidade de Rio Largo pelo número 10.
A. você que leu esta estória acha que Tertuliano estava sendo sincero com Josefina? Por quê?
B. E se o itinerário 1-5-9-10 estivesse a cargo de outra empresa, estaria ele sendo sincero? Por quê?
	
	1
	2
	3
	4
	5
	6
	7
	8
	9
	10
	1
	
	x
	x
	
	x
	
	
	
	
	
	2
	x
	
	x
	x
	x
	
	
	
	
	
	3
	x
	x
	
	
	x
	x
	
	
	
	
	4
	
	x
	
	
	x
	
	x
	
	
	x
	5
	x
	x
	x
	x
	
	x
	x
	x
	x
	
	6
	
	
	x
	
	x
	
	
	x
	
	x
	7
	
	
	
	x
	x
	
	
	x
	
	x
	8
	
	
	
	
	x
	x
	x
	
	
	x
	9
	
	
	
	
	x
	
	
	
	
	x
	10
	
	
	
	x
	
	x
	x
	x
	x
	
SOLUÇÃO
	
	1
	2
	3
	4
	5
	6
	7
	8
	9
	10
	
	1
	
	x
	x
	
	x
	
	
	
	
	
	3
	2
	x
	
	x
	x
	x
	
	
	
	
	
	4
	3
	x
	x
	
	
	x
	x
	
	
	
	
	4
	4
	
	x
	
	
	x
	
	x
	
	
	x
	4
	5
	x
	x
	x
	x
	
	x
	x
	x
	x
	
	8
	6
	
	
	x
	
	x
	
	
	x
	
	x
	4
	7
	
	
	
	x
	x
	
	
	x
	
	x
	4
	8
	
	
	
	
	x
	x
	x
	
	
	x
	4
	9
	
	
	
	
	x
	
	
	
	
	x
	2
	10
	
	
	
	x
	
	x
	x
	x
	x
	
	5
	
	
	
	
	
	
	
	
	
	
	
	
	
	3
	4
	4
	4
	8
	4
	4
	4
	2
	5
	
Para que estória de Tertuliano com Josefina seja verdadeira faz-se necessário que o grafo seja SEMI EULERIANO, ou seja, que 2 (DOIS) vértices do grafo tenham grau ÍMPAR. Um grafo semi-Euleriano (que permite um caminho Euleriano) possui exatamente dois vértices de grau ímpar, um é o ponto de partida (Rio Largo - 10) e outro é o ponto de chegada.(SANTANA-1)
a) Como existem dois vértices exatamente dois vértices de grau ímpar o GRAFO É SEMI EULERIANO, logo Tertuliano estaria FALANDO A VERDADE para Josefina.
b) Se o itinerário 1-5-9-10 for retirado, ELE ESTARIA MENTINDO, pois os vértices de grau ímpar seriam 1 e 9, ou seja, o número 9 não corresponde a cidade de Rio Largo.
	
	1
	2
	3
	4
	5
	6
	7
	8
	9
	10
	
	1
	
	x
	x
	
	
	
	
	
	
	
	2
	2
	x
	
	x
	x
	x
	
	
	
	
	
	4
	3
	x
	x
	
	
	x
	x
	
	
	
	
	4
	4
	
	x
	
	
	x
	
	x
	
	
	x
	4
	5
	
	x
	x
	x
	
	x
	x
	x
	
	
	7
	6
	
	
	x
	
	x
	
	
	x
	
	x
	4
	7
	
	
	
	x
	x
	
	
	x
	
	x
	4
	8
	
	
	
	
	x
	x
	x
	
	
	x
	4
	9
	
	
	
	
	
	
	
	
	
	
	1
	10
	
	
	
	x
	
	x
	x
	x
	x
	
	5
	
	
	
	
	
	
	
	
	
	
	
	
	
	3
	4
	4
	4
	6
	4
	4
	4
	1
	4
	
A
B
C
D
E
F
A
BC
D
E
F
1
2
3
4
5
6