Please enable JavaScript.
Coggle requires JavaScript to display documents.
Grafos - Coggle Diagram
Grafos
Pesquisa em profundidade
o algoritmos visita um vértice em em seguida um adjacente ao seu, ainda não visitado
caso tenha mais de um adjacente isso é decidido de forma arbitraria
Continua até quando não há mais vértices adjacentes não visitados
chamado de
beco sem saída
Em um
beco sem saída
volta para a aresta inicial e repete o algoritmo
Pesquisa
Vertice inicial serve do raiz da subarvore
ao verificar uma nova aresta é anexada como filho do inicial
Eficiência
Leva o tempo relacionado ao tamanho do grafo
MIn-Theta (| V |2),
é uma estrutura LIFO (last-in first-out)
O que é
Um conjunto de nós e vertices em um plano
Tipos
Direcionado ou dígrafos
Geralmente indicado com setas
Não direcionado
Quando a ordem de um par ordenado não importa
Nomenclatura
Um par (V, U)
V é a
cabeça
do grafo
U é a
cauda
do grafo
Numero de arestas
0 ≤ | E | ≤ | V | ( | V | - 1 ) / 2 .
Grafo completo
Cada par de seus vértices conectados por uma aresta
Matrix adjacencia
Representar um grafo em forma de matriz "binaria"
Gráficos ponderados
possuem números (pesos) atribuídos em suas arestas
Aplicaçoes em real-world
avaliar o caminho mais curto entre vários outros
Para representar em uma matriz adjacência
coloca-se o símbolo infinito em arestas que não se ligam
Chamada de matriz custo
Pesquisa em amplitude
Visita primeiro todos os vértices adjacentes ao primeiro
breadth-first search forest
Eficiencia
Possui a mesma eficiência que a pesquisa em profundidade
MIn-Theta (| V |2),
É uma estrutura FIFO (first-in first-out)
Classificação topologica
DAG
Sigla para
Directed acyclic graph
Verificar se é um DAG
pesquisa em profundidade
Se uma borda posterior foi encontrada, o dígrafo não é um
DAG
, e a classificação topológica de seus vértices é impossível
baseado em uma implementação direta da diminuição
A ordem em que os vértices são excluídos produz uma solução para o problema de classificação topológica.
classificação topológica
Analisa se vértices de um grafo pode ser distribuída de determinada maneira
Requisitos para aplicar a classificação
Se um dígrafo não tem ciclos dirigidos
Caminhos e ciclos
caminho
Uma sequencia de arestas indo do vértice X para um vértice Y
Caminho direfionado
É mostrado em cada aresta do grafo a direção a ser seguida
Ciclos
Uma sequencia de arestas saindo do vértice X e voltando para x sem repetir vértices