Please enable JavaScript.
Coggle requires JavaScript to display documents.
Grafos - Coggle Diagram
Grafos
Formalmente
- G= (V,E) é um par de dois conjuntos, V é um conjunto não vazio chamado de vértices e E é o conjunto de pares de vértices, chamado de arestas
- Se uma aresta (v,u) é a mesma que (u,v) dizemos que é uma aresta não direcionada, caso contrário chamamos de aresta direcionada.
- Em uma aresta direcionada temos a cabeça e o rabo.
- Um grafo onde todas as suas arestas são direcionadas é chamado de digrafo
- laços: vertices conectados em si mesmos
-
Caminho de um grafo
- um caminho de u à v pode ser definido como a sequencia de vértices adjacentes que começam em u e terminam em v
- se todos os vértices são distintos, o caminho é dito simples
- o tamanho de um caminho é o número de vértices que o definem
Busca em Largura (BFS)
- Visita todos os vértices adjacentes ao primeiro, depois os vértices não visitados separados por duas arestas, e assim por diante
-
-
Ordenação topológica
-
O objetivo é listar todos os vértices de tal maneira que o vértice que começa deve ser listado antes do vértice final
- Uma coleção de pontos chamados de vértices e alguns deles estão conectados por um segmento chamado de aresta
Grafos com peso
Grafos com numeros associados às suas arestas, chamados de pesos
-