UNIVESP - 2021 - Exercícios de apoio 1 - Semana 7 - Fundamentos Matemáticos da Computação

Prévia do material em texto

FUNDAMENTOS MATEMÁTICOS DA COMPUTAÇÃO
Grafos7
 
EXERCÍCIOS DE APOIO
Apenas para praticar. Não vale nota.
G
u v
1
2,
3,
4,
5
2
1,
3,
4,
5
3
1,
2,
4,
5
4
1,
2,
3,
5
5 1,
Seja um grafo e dizemos que é ligado a se existe um passeio em cujo primeiro nó é 
e o último é . Determine todos os pares tais que está ligado a nos grafos e H.
 
H
u v
1 2, 3,4, 7
2 3, 4,7
3 4, 2,3, 7
4 2, 7
5 4, 7,2, 3
6
5, 7,
4, 2,
3
7 —
1.
 
 
2,
3,
4
 
 
Considere o seguinte grafo e os dois grafos H e H . Escreva as matrizes de adjacência , M
e M de , H e H , respectivamente.
 
 
2. 1 2 1
2 1 2
 
 
Por definição um grafo é chamado de bipartido se o conjunto de seus vértices pode ser dividido
em dois conjuntos distintos e , de forma que cada aresta de conecta um vértice de a
um vértice de .
Verifique se o grafo abaixo é um grafo bipartido. Se for, identifique os nós que pertencem a cada
um dos subconjuntos e .
 
 
3.
Uma rede de computadores pode ser configurada com diferentes topologias. As mais usuais são: 
Leia as afirmações abaixo e escreva V caso a afirmação seja verdadeira ou F caso seja falsa.
4.
( ) Toda a rede em topologia-estrela é um grafo bipartido.a.
 
 
( ) Nunca é possível estruturar uma rede híbrida de forma a obtermos um grafo
bipartido.
b.
( ) O grafo com topologia anel acima é simples.c.
( ) O grafo com topologia anel só pode ser bipartido se o número de nós for par.d.
Va.
Fb.
Vc.
Vd.
Dados H e , dois grafos não orientados, determine a união de e H.
RESPOSTA:
 
 
5.
Sejam os grafos não orientados 6.
 
 
Escreva o conjunto V(G).a.
Escreva o conjunto E(G).b.
Identifique quais dos grafos H, X, W e Z são sub-grafos de G.c.
a.
b.
 Portanto, H não é sub-grafo de 
.
 Portanto, é sub-grafo de .
 Portanto, não é sub-grafo de 
.
 Portanto, Z é sub-grafo de .
c.
Verifique se os grafos H e H são sub-grafos do grafo .7. 1 2
Definição: Um grafo H é sub-grafo de um grafo G se as arestas em E e E possuem os mesmos
extremos.
 não é sub-grafo de G pois a aresta que une os nós 3 e 6 não pertence
a E .
 é um sub-grafo de G.
 
 
h g
g
Dados H e G, dois grafos não orientados, determine H união G.
RESPOSTA: 
8.
 
 
Seja H o grafo abaixo. Determine quais nós de H distintos de 2 podem ser escolhidos em V como
nó inicial, de modo que exista uma trilha começando no vértice escolhido e terminando no nó 2.
Portanto, os nós 1, 3, 4, 5 e 6 podem ser escolhidos como nó de origem.
 
 
9. h
Considere o seguinte grafo G e os passeios P1, P2 e P3. Complete a tabela com V para verdadeiro
e F para falso, se o passeio é uma trilha, caminho ou ciclo, lembrando que o passeio pode ter mais
de um atributo verdadeiro.
Trilha Caminho Ciclo
Trilha Caminho Ciclo
10.
 
ESCONDER
GABARITO
 
V F F
F F F
V V V
 
 
Represente os seguintes grafos por sua matriz de adjacência.
Grafo G, matriz M:
Grafo H, matriz N:
 
 
11.