Please enable JavaScript.
Coggle requires JavaScript to display documents.
Problemas em Grafo - Coggle Diagram
Problemas em Grafo
Grafos Especiais
DAGs
Um grafo direto, sem ciclos. Pode ser usado para topological sorting, DP, detecção de ciclos, caminho mais longo, contagem de caminhos, e etc
Tree
Uma árvore deve possuir as seguintes características: A sua quantidade de arestas é igual a quantidade de vértices -1; Não possui ciclo; É conexa; E a partir de um vértice v, existe um único caminho até outro vértice u.
O diâmetro de uma árvore pode ser encontrado utilizando a seguinte técnica: A partir de um vértice qualquer devemos encontrar o vértice mais distante, com esse vértice que encontramos devemos fazer o mesmo. Ao encontrar esses dois vértices o diâmetro da árvore vai ser a distância entre ambos os vértices encontrados.
Grafo Euleriano
Checar se um grafo possui um caminho euleriano é relativamente simples, devemos checar os graus de cada nó, todos devem possuir grau par.
-
Grafo Bipartido
O conjunto de vértices pode ser separado em dois conjuntos disjuntos V1 e V2, de tal forma que o conjunto de arestas {u, v}, todo u pertence a V1 e v pertence a V2.
-
Network Flow
Problemas que podem ser modelados como fluxos de água, exemplo: fluxo de água até o ralo de uma pia
Um dos problemas motivadores é o Maximum Flow que busca o maior fluxo possível de uma ou mais fontes para uma ou mais saídas
Esse problema pode ser representado como um grafo conexo, direto e com pesos.
Algoritmos
Ford Fulkerson
Encontra caminhos que possuem f como o menor peso nas arestas o algoritmo vai realizar os seguintes passos:
-
-
Edmond Karp
Variante do algoritmo de Ford Fulkerson que utiliza BFS para encontrar o menor caminho entre uma fonte s e uma saída t