TEORIA DE GRAFOS Flashcards
Qual a nomenclatura dos grafos?
1 - Vértice, ponto ou nós.
2 - Aresta, arcos ou ramos.
3 - Vertices adjacentes
2 - Quais são os Elementos históricos da Teoria do Grafo?
1 - Russia, Konigsberg, Rio Pregel, tem sete pontes e duas ilhas.
2 - Matemático Leonhard Euler
3 - Precisaria construir mais 3 pontes (ligações em pares)
3 - O que faz a Teoria dos Grafos?
Estuda a relação entre os objetos de um determinado conjunto.
4 - Qual o conceito formado de grafo?
Um grafo é um par (V (vértice), A (aresta)), em que V é um conjunto arbitrário e A é um subconjunto de V(2)
5 - Quais são os tipos de grafos?
1 - Orientado e não orientado.
2 - de 1º grau a n graus.
3 - Portador de grau de emissão ou grau de recepção.
4 - Grau conexo ou desconexo.
6 - Quais os tipos de Matrizes o grafo pode se converter? O que é importante informar quando se transforma um grafo em matriz?
1 - Em uma Matriz (0, 1) byte ou matriz binária.
2 - Em uma matriz de valor absoluto.
Obs: Importante infortmar se o valor é a falta de aresta ou representa um valor zero.
7 - Como pode ser a representação do grafos em Python? Qual biblioteca se usa para estas representação?
A representação pode ser:
1 - Representação explícita: quando nós mesmo nomeamos os vértices no grafo.
2 - Representação implícita: a nomeação dos vértice é feito automaticamente através de números inteiros.
Obs. Biblioteca é NetWorkx
8 - A busca em grafo começa por onde?
A busca em grafo sempre começa por um vértice qualquer.
9 - Quais os tipos de busca que foi estudado? Qual suas siglas?
1 - Busca em profundidade. DFS
2 - Busca em Largura. BFS
3 - Busca com Algoritmo Dijkstra
