Please enable JavaScript.
Coggle requires JavaScript to display documents.
FLUXO E GRAFOS ESPECIAIS - Coggle Diagram
FLUXO E GRAFOS ESPECIAIS
Definição do problema: Dado um grafo direcionado e com pesos, simule o fluxo de algo, em que as arestas são os meios que o fluxo percorre e os vértices os pontos de bifurcação
Algoritmo de Ford Fulkerson:
- Lógica: Por meio de um algoritmo interativo, ele busca partir de um ponto s inicial e achar o maior flow até um vértice t final, adicionando e tirando os valores das arestas a medida que ele passa de uma aresta para outra. Para achar o caminho usa-se uma bfs ou uma dfs.
Algoritmo de Edmonds Karp
- Lógica: Usar a bfs para achar o maior flow, tendo como base o código de ford fulkerson, pois consegue percorrer de uma maneira mais rápida todos os possíveis caminhos de flow
Problemas de fluxo
Minimum cut:
- Defnição: Achar qual o menor valor que pode-se retirar arestas de um grafo, de modo que o maior flow de um ponto s a um ponto t desse grafo seja 0
- Resolução: O custo dessas remoções é o próprio max flow e as arestas a serem retiradas são as arestas que partem dos vértices ligados a o vértice de origem até os vértices que não podem ser alcançados pelo vértice de origem.
Multi-source:
- Definição: Achar o fluxo pedido para mais de um vértice de origem chegando em pelo menos 1 vértice de chegada.
- Resolução: Basta ligar os vértices de origem pedidos com um peso muito alto e fazer o mesmo para os vértices de destino
Capacidade dos vértices:
- Definição: Problema em que não só as arestas possuem peso, mas também os vértices.
- Resolução: Gerar novas arestas que representem o peso do vértice. OBS: Isso dobra o número de arestas do grafo
GRAFOS ESPECIAIS
DAG
-
Problemas
Menor caminho:
- Lógica: Como não existem ciclos no grafo e ele é direcionado, então ao fazer um toposort no grafo, então para achar o menor caminho é só fazer uma travessia no grafo do ponto de partida ao ponto de chegada
Maior caminho:
- Lógica: Basta multiplicar as arestas por -1 e fazer a mesma coisa do menor caminho, com o toposort já calculado
Counting paths:
- Definição: Dado um problema em que o agente só pode se mover em um sentido sem poder voltar, basta fazer uma bfs acrescentando 1 no valor de cada vizinho de um vértice
Árvores
Problemas
Pontos de articulação
- Solução: Como cada nó de uma árvore é um ponto de articulação, logo basta fazer uma travessia na árvore analisando os pontos desejados e sabendo que ao retirar um nó perde-se a conexão com os nós dele em diante
Menor caminho
- Solução: como só existe um caminho entre 2 vértices em uma árvore, basta rodar uma dfs ou bfs para encontrar o menor caminho
Para todos os pares: basta repetir o algoritmo de menor caminho para cada vértice onde altera-se a raiz da árvore para o vértice analisado
Diâmetro de uma árvore:
- Solução: Basta rodar 2 Bfs ou dfs, uma para um vértice qualquer e a outra para o vértice mais distante desse vértice inicial
Grafo euleriano
Checagem:
- Solução: Basta checar se o grau de cada vértice é par