Please enable JavaScript.

Coggle requires JavaScript to display documents.

Mapa Mental 10 - Coggle Diagram

- - - - Chamamos "u" e "v" de pontos finais da aresta (u,v), ou incidentes a ela
        
        Um grafo é não-direcionado se todas as suas arestas forem não-direcionadas
        
        Inequação para o número de arestas E, considerando nossa definição sem loops e sem múltiplas arestas entre o mesmo vértice de um grafo
        
        0 ≤ |E| ≤| V |(|V | − 1)/2.
        
        Um grafo direcionado - com todas as arestas direcionadas - é um digrafo
        
        Um grafo com todo par de vértices conectados por uma aresta é completo
        
        Um grafo com poucas arestas faltando é dito denso
        
        O grafo com poucas arestas em relação ao número de vértices é esparso
        
        É importante escolher algoritmos apropriados a depender para lidar com grafos densos ou esparsos.
        
        Grafos em computadores são representados por matrizes de adjacência ou listas de adjacência
        
        Matriz de adjacência: um grafo com n vértices possui uma matriz nxn de adjacência, sendo esta uma matriz de booleano onde o elemento na posição [i, j] será 1 se existir uma aresta do vértice i até j, 0 se não existir
        
        Lista de adjacência: é uma coleção de listas encadeadas, uma para cada vértice, que contém todos os vértices adjacentes ao vértice da lista
        
        Gráficos com peso: são grafos onde cada vértice tem um peso associados a ele
        
        Se utilizarmos matrizes de adjacência, então o elemento A[i.j] contém o peso da aresta que vai do vértice i até o vértice j, se ele existir
        
        Se utilizarmos listas de adjacência, então os nós conteriam não apenas os nomes dos vértices mas também o seu peso
- - - - Uma pilha geralmente é usada para rastrear a operação DFS
        
        Quando um vértice é visitado pela primeira vez, este vértice é dado push na pilha, e dado pop quando aquele vértice fica sem caminhos possíveis de serem caminhados
        
        Eficiência (traversal time)
        
        Matriz: Θ(|V|^2)
        
        Lista: Θ(|V|+|E|)
- - - - Matriz: Θ(|V|^2)
      - Lista: Θ(|V|+|E|)
- - - - DFS: Pode verificar se é DAG e se for, retorna ele ordenado.
        
        Realiza DFS e nota a ordem em que os vértices dão caminhos sem-saída. Revertendo esta ordem, nós temos uma solução para o topological sorting.
        
        Se algum back edge for encontrado, sabemos que este grafo não é DAG, e portanto não pode ser ordenado utilizando topological sorting
      - Estratégia "decrease-and-conquer" para resolver o problema do topological sorting
        
        Em um digrafo, identificar repetidamente qual é a "fonte" (vértice que nenhuma aresta aponta para ele), e deleta esta fonte junto com todas as arestas que saem dela.
        
        Se tiver muitas fontes, uma é escolhida arbitrariamente. Se não tiver nenhuma, não pode ser resolvido.
        
        A ordem em que os vértices são deletados dão uma solução ao problema topological sorting.