Classificação de grafo Teoria dos Grafos e Análise de Algoritmos

Prévia do material em texto

Classificação de grafo – Teoria dos Grafos e Análise de Algoritmos
Exercícios
1. Um administrador de redes deseja criar um grafo para representar a interligação
dos equipamentos na rede da sua empresa. Pesquisando sobre o assunto, ele
descobriu sobre o módulo NetworkX e resolveu criar um script Python para resolver
seu problema. O grafo que ele deseja criar é mostrado a seguir:
Ao criar o grafo, o administrador decidiu definir um dicionário contendo os vértices
e a lista de vértices associados. Para isso, ele deveria criar um dicionário Python
com o seguinte formato:
dicionario = ｛
 Vértice01 : [ Lista_de_Vértices_Adjacentes] ,
 Vértice02 : [ Lista_de_Vértices_Adjacentes] ,
...
｝
Qual das opções a seguir contém um dicionário que permita gerar o grafo
desejado?
Você acertou!
C. 
arestas = ｛
    "Router 01" : ["Switch 01", "Switch 02"],
    "Switch 01" : ["Servidor 01", "Host A", "Host B", "Host C"],
    "Switch 02" : ["Servidor 02", "Host D", "Host E", "Host F"]
    ｝
2. Na teoria dos grafos, um Caminho Euleriano é um caminho em um grafo que
visita todas as arestas exatamente uma vez. Um circuito euleriano é um Caminho
Euleriano que começa e termina no mesmo vértice. O conceito foi introduzido por
Leonard Euler para a resolução do famoso problema das sete pontes de
Königsberg em 1736.
Observe o grafo a seguir:
Qual das alternativas a seguir contém uma sequência de arestas que faz um circuito
euleriano válido no grafo acima partindo do vértice 1?
Você acertou!
C. G - F - I - H - D - E - B - C – A
A - C - B - E - D - I - H - F - G
Está  incorreta, pois é  impossível:  após percorrermos a aresta D, não podemos
percorrer a aresta I.
C - B - E - D - H - I - F - G - A
Está incorreta, pois, apesar de fazer um circuito euleriano, parte do vértice 2.
G - F - I - H - D - E - B - C - A
Está correta, já que contém um circuito que passa por todas as arestas do
grafo sem repetição.
A - C - B - G - F - I - H - C - A
Não está correta, pois passa mais de uma vez pelas arestas A e C.
B - H - I - D - C - A - E - F
Não está correta,  pois não percorre  todas as arestas do grafo nem retorna ao
vértice 1.
3. Um grafo direcionado G (V, A) é constituído por um conjunto V = ｛v1, v2, . . . ,
vn ｝ não vazio de objetos, chamados vértices (ou nós), e um conjunto A = {a1, a2, . .
. , am} de arestas ou arcos, em que cada aresta é um par ordenado de vértices.
Usando Python, um estudante deseja criar o seguinte grafo direcionado:
E, para isso, implementou o seguinte script Python:
import networkx as nx
G=nx.DiGraph()
G.add_node(1,pos=(0,0))
G.add_node(2,pos=(0,1))
G.add_node(3,pos=(1,1))
G.add_node(4,pos=(1,0))
G.add_node(5,pos=(0.5,-0.5))
--------------------- ?
--------------------- ?
--------------------- ?
--------------------- ?
--------------------- ?
--------------------- ?
--------------------- ?
pos=nx.get_node_attributes(G,'pos')
nx.draw(G,pos, with_labels=True, width=3, node_size=1600)
labels = nx.get_edge_attributes(G,'nome')
nx.draw_networkx_edge_labels(G,pos,edge_labels=labels)
Qual das alternativas a seguir contém uma sequência de comandos add_edge que
gera as arestas direcionadas para o grafo desejado?
Você acertou!
E. 
G.add_edge(1,2,nome='A')
G.add_edge(3,1,nome='B')
G.add_edge(2,3,nome='C')
G.add_edge(3,4,nome='D')
G.add_edge(1,4,nome='E')
G.add_edge(4,5,nome='F')
G.add_edge(5,1,nome='G')
4. Uma loja de equipamentos de informática tem um sistema simples de controle de
vendas que trabalha com um banco de dados SQLite3 contendo os seguintes
esquemas de tabelas:
cliente (id integer PRIMARY KEY, nome text NOT NULL)
produto (id integer PRIMARY KEY, nome text NOT NULL)
pedido (id_cliente integer, id_produto integer)
O dono da empresa quer saber quais produtos são mais pedidos pelos seus
clientes. Para resolver essa questão, foi solicitado ao desenvolvedor que criasse
uma solução que permitisse visualizar essas informações em forma de diagrama,
conforme o exemplo mostrado a seguir:
Sobre a solução proposta, são feitas as seguintes afirmações:
I. Ela gera um grafo bipartido, pois um grupo de vértices (cliente) só se relaciona
com elementos de outro grupo de vértices (produto).
II. Os vértices relativos aos clientes são adicionados ao grafo pelos comandos
executados nas linhas 06 e 07.
III. Na linha 23, as arestas do grafo são criadas a partir do resultado da consulta
SQL definida nas linhas 18, 19 e 20.
Qual(is) das afirmações é ou são verdadeira(s)?
Você acertou!
C. Alternativas I e III.
A afirmação I é verdadeira,   pois   não   há   relações   de   clientes   entre   si   e   de
produtos entre si. A afirmação II é falsa, pois esse trecho do código (linhas 06 e
07) tratam da busca dos dados da tabela cliente, não tendo sido feita até então
nenhuma   inserção   de   vértices. A afirmação III também é verdadeira. O
comando fetch_all retorna uma lista de tuplas contendo os valores pesquisados na
consulta SELECT. Como nesse caso a consulta retorna um par contendo o nome
do cliente e o nome do produto, podemos usar esse resultado para gerar a lista de
arestas de forma direta e única.
5. Uma loja especializada em games dispõe de um sistema que relaciona os títulos
do seu catálogo com o gênero do game (plataforma, luta, corrida etc.). Esse sistema
utiliza um banco de dados NoSQL para manter seus dados (MongoDB). O cadastro
dos títulos e gêneros foi feito por meio do seguinte script Python:
import pymongo
cliente = pymongo.MongoClient("mongodb://127.0.0.1:27017/")
bd = cliente["bdEx5"]
collection = bd["games"]
lista_contatos = [
{ "titulo": "Super Mario Bros.", "genero": "Plataforma" ｝,
{ "titulo": "Street Fighter II", "genero": "Luta" },
{ "titulo": "Mortal Kombat", "genero": "Luta" },
{ "titulo": "Final Fantasy VIII", "genero": "RPG" },
{ "titulo": "Legend of Zelda", "genero": "Aventura" },
{ "titulo": "Top Gear", "genero": "Corrida" } ]
x = collection.insert_many(lista_contatos)
Para facilitar sua visualização, a empresa decidiu solicitar a uma equipe de
desenvolvimento que fizesse um script para ler os dados do banco e criar um grafo
direcionado de cada título de game com seu respectivo gênero.
A solução proposta foi a seguinte:
import pymongo
import networkx as nx
cliente = pymongo.MongoClient("mongodb://127.0.0.1:27017/")
bd = cliente["bdEx5"]
collection = bd["games"]
dados = collection.find()
G = nx.DiGraph()
for x in dados:
 ----------?---------- 
nx.draw(G, with_labels=True)
Qual das alternativas a seguir contém o comando que faz com esse script funcione
de maneira correta?
Você acertou!
A. G.add_edge(x["titulo"], x["genero"] ).
O comando correto a ser inserido é: G.add_edge(x["titulo"], x["genero"] ),
pois x obterá um dicionário com os campos titulo e genero, usados para
definir a origem e o destino de cada aresta.
O comando G.add_edge(dados) não funciona corretamente, pois a variável dados
não contém uma tupla de dados que possa ser atribuída a uma aresta do grafo.
O comando G.add_edge(x) também não funciona corretamente porque a variável
x não contém uma tupla de dados que possa ser atribuída a uma aresta do grafo.
O  comando  G.add_node(x["titulo"])   serve  para  criar   vértices,  e  não  arestas.  O
grafo criado teria apenas vértices, mas não teria aresta nenhuma.
O comando G.add_node(x["titulo"], x["genero"]) geraria um erro de sintaxe na sua
execução.
	Classificação de grafo – Teoria dos Grafos e Análise de Algoritmos
	Exercícios