Tipos de grafo Teoria dos Grafos e Análise de Algoritmos

Prévia do material em texto

Tipos de grafo – Teoria dos Grafos e Análise de Algoritmos
Exercícios
1. Teoria dos grafos é um ramo da matemática que estuda as relações entre objetos
de um conjunto. Essas relações são formadas por vértices (que representam os
elementos) e as arestas (os relacionamentos entre os elementos).
Com base no grafo ilustrado, assinale a alternativa correta.
Você acertou!
C. Vértices: 5
     Arestas: 7
    Grau do vértice 3: 4
Os   vértices   são   representados   pelos   círculos   numerados,   que   representam   os
elementos. Portanto, são 5. As arestas são representadas pelas linhas que unem
os vértices, indicando os relacionamentos entre os vértices. Logo, são 7. O grau
do vértice 3 é o número de linhas que saem desse ponto. Então, são 4.
2. Os grafos são representações de situações que foram pensadas para gerar
soluções a respeito de determinado problema. Uma das formas de representação
de um grafo, para ser tratado na programação de computadores, é a partir da sua
matriz de adjacência.
Utilizando-se o grafo ilustrado, assinale o item que tem a matriz de adjacência
correta.
Você acertou!
E. 
A matriz de adjacência é uma forma de representação de um grafo para ser utilizado na
linguagem de programação. Nela, são exibidos os vértices, tanto na vertical quanto na
horizontal,   e   depois   é   assinalado   o   relacionamento   entre   eles. Caso haja
relacionamento, o número que vem na intersecção dos vértices será 1; caso não
haja relacionamento, será 0.
3. Uma lista de adjacência mostra, para cada vértice do grafo, uma relação de todos
os outros vértices com os quais ocorre o relacionamento.
A partir disso, escolha o grafo que representa a situação proposta pela lista de
adjacência.
Você acertou!
B. 
O grafo correto é aquele que tem a ligação do vértice 1 com os vértices 2 e 3, do
vértice 2 com os vértices 1, 3 e 4, do vértice 3 com os vértices 1, 2 e 5, do vértice
4 com os vértices 2 e 5 e do vértice 5 com os vértices 3 e 5 (relacionamento com
ele próprio).
4. Grafos isomorfos são aqueles que têm a mesma forma, mas este não é o único
requisito para se definir que é isomorfo. Deve-se fazer uma série de verificações e,
de acordo com as respostas, é possível ou não afirmar que o grafo é isomorfo,
mesmo que o formato seja o mesmo.
Assinale a alternativa que exibe a resposta correta, ou seja, se os grafos G e H são
isomorfos. Considere Vg (número de vértices do grafo G), Vh (número de vértices
do grafo H), Ag (número de arestas do grafo G) e Ah (número de arestas do grafo
H).
Você acertou!
E. 
É isomorfo.
Vg = 10, Ag = 15
Vh = 10, Ah = 15
f(a) = 1, f(b) = 2, f(c) = 3, f(d) = 4, f(e) = 5, f(f) = 6, f(g) = 7, f(h) = 8, f(i) = 9, f(j) = 10
Para   que   os   grafos   sejam   considerados   isomorfos,   eles   deverão   ter   o   mesmo
número de vértices, o mesmo número de arestas e deve-se verificar se o vértice
“a” está na mesma posição que o vértice “1”, o “b” na mesma posição do “2” e,
assim, até que o “h” esteja na mesma posição do vértice “10”. Como isso ocorreu,
então pode-se afirmar que os grafos são isomorfos.
5. A teoria dos grafos foi criada pelo matemático Leonhard Euler em 1736 para
resolver o problema das sete pontes da Cidade de Königsberg. Os habitantes
daquela cidade perguntavam-se se era possível cruzar as sete pontes em uma
caminhada contínua sem passar duas vezes por qualquer uma delas.
Sobre a teoria dos grafos, relacione a letra do grafo (que contém o nome) com o
número do grafo (que contém a imagem) e escolha a resposta que tem o
relacionamento correto.
Você acertou!
C. 1e, 2d, 3b, 4a, 5c.
Com o desenvolvimento dessa área da matemática, surgiram muitos outros tipos
de grafos, dentre eles: trivial, regular, multigrafo, laço, buquê, isomorfo. Um trajeto
que inclua todas as arestas de dado grafo G (V, A) é chamado de trajeto
euleriano e aquele em que o caminho passa por cada vértice uma única vez é
conhecido como caminho hamiltoniano.
O grafo 1 é bipartido, ou seja, é o grafo que se divide em 2 conjuntos, ou seja, x
e y.
O grafo 2 é trivial, ou seja, aquele que tem somente vértice sem arestas.
O grafo 3 é laço, ou seja, aquele cujo vértice conecta-se com ele mesmo (loop).
O grafo 4 é dígrafo,   ou   seja,   aquele   que   tem   arestas   com   setas  indicando   a
direção.
O grafo 5 é simples, ou seja, são vértices ligados por arestas.
	Tipos de grafo – Teoria dos Grafos e Análise de Algoritmos
	Exercícios