Please enable JavaScript.

Coggle requires JavaScript to display documents.

M11 (Mapa Mental 11) - Coggle Diagram

- - - - Alguns sendo conectados por segmentos de linhas; arcos ou arestas.
  - - - Um set V finito e não vázio, composto dos itens chamados vértices
        
        Se os pares de vértices são sem ordem (ex: (u, v) é o mesmo que (v, u), nós dizemos que esse par é adjecente um ao outro, e é conectado por uma aresta sem direção. Chamamos os vértices (u e v) de endpoints da aresta (u, v), e dizemos que u e v são incidentes à aresta.
        
        Se um par de vértices (u, v) não é o mesmo que o par (v, u), dizemos que sua aresta tem direção partindo do vértice u, chamado a cauda da aresta, até o vértice v, chamado a cabeça da aresta.
        
        Também dizemos que a aresta (u, v) sai de u e entra v.
      - Um set E de pares de itens chamados arestas.
        
        Um grafo G é sem direção se toda aresta nele é sem direção.
        
        Um grafo G é direcionado se toda aresta nele é direcionado
    - - Sem múltiplos arestas entre as mesmas vértices de um grafo sem direção, temos a seguinte inequação:
        
        0 ≤ |E|≤|V |(|V | − 1)/2.
        
        Sendo |E| o número de arestas possíveis, e |V| o número de vértices. Não há loops.
        
        Obtemos o maior número possível de arestas se tem uma aresta conectando cada um de seus |V| vértices com todos |V|-1 outros vértices. Temos, porém, que dividir por 2, pois inclui cada aresta em dobro.
        
        Um grafo com todo par de vértices conectado por uma aresta é chamado de completo. Um grafo com relativamente poucas arestas sobrando é denso, mas um com poucas arestas relativo ao número de vértices é chamado de sparse.
        
        Essa "densidade" afeta a performance do algoritmo e como representamos o grafo.
  - - - Matriz de Adjecência
        
        Em um gráfico com n vértices, é uma matriz booleana de n x n, com uma coluna e uma fileira para cada um dos vértices do grafo.
        
        Um elemento na ith fileira e na jth coluna é igual a 1 se tem uma aresta do ith vértice até o j vértice, e igual a 0 se não há tal aresta.
        
        Note que a matriz de adjecência é sempre simétrica
      - Lista de Adjecência
        
        A lista de adjecência de um grafo é a coleção de linked lists, um para cada vértice, contendo todas as vértices adjecentes à vértice da lista. Geralmente, temos um header identificando a vértice para qual a lista é compilada.
        
        Se um grafo é sparse, tal representação pode usar menos espaço, mesmo com o espaço extra consumido por pointers. O contrário acontece com grafos densos.
        
        Essencialmente, contém columinas de uma matriz de adjecência que, para certo vértice, contém 1's.
    - - Um grafo ou diagrama com números associados às arestas. Esses são os pesos ou custos. Assim é útil para tarefas como descobrir a menor distância entra dois pontos.
        
        Ambas representações principais podem adotar grafos com peso.
        
        Se um grafo ponderado for representado por sua matriz adjecente, então seu elemento A[i, j] vai simplesmente conter o peso a aresta de eu ith até seu jth vértice se tal aresta existe, e um símbolo especial se não existe.
        
        Matriz Ponderada
        
        Listas adjecentes para um grafo ponderado precisam incluir em seus nós não só o nome da vértice adjecente, mas também o peso associado à aresta.
    - - Path
        
        Conectividade
        
        Aciclidade
        
        Um path de vértice u a v de um grafo G pode ser definido como a sequência de vértices adjecentes que começam por u e termina com v.
        
        Se todas vértices forem distintas, a path é simples
        
        O tamanho de uma path é o número total de vértices na sequência menos 1, que é o mesmo número de arestas no path.
        
        No caso de um grafo direcionado, temos a path direcionada, que é uma sequência de vértices em que todo par consecutivo é conectado por uma aresta direcionada da vértice listada primeira até a vértice listada seguinte.
        
        Um grafo é dito conectado se para todo par de vértices u e v, tem caminho de u para v.
        
        É importante saber se um grafo tem ciclos. Um ciclo é a path de tamanho positivo que começa e termina no mesmo vértice, e não atravesa uma aresta mais que uma vez. Um grafo sem cíclos é acíclico
  - - - Começa o travesso do grafo em uma vértice arbitrária, marcando-o como visitado. Em cada iteração, o algoritmo procede a um vértice não visitado, adjecente a seu atual.
        
        Esse processo segue até encontrar um vértice sem adjecências que não foram visitados. Nesse ponto de fim, o algoritmo volta uma aresta para a vértice origem e continua a visitar a partir desse ponto.
        
        O algoritmo eventualmente para após voltar para o índice inicial.
        
        Finalizado, todos vértices no mesmo componente que o inicial foram visitados.
        
        Se ainda há vértices não visitadas, precisa-se reiniciar o algoritmo com uma de tais vértices como o ponto de origem.
        
        É conveniente usar um stack para traçar a operação.
        
        É útil acompanhar construindo uma floresta de busca de profundidade.
        
        O vértice inicial sendo a raiz da primeira árvore em tal floresta. Arestas encontradas são chamadas de arestas de árvore.
        
        É possível encontrar uma aresta que traz a árvore de volta a uma vértice diferente de seu parente na árvore. Tal aresta é uma aresta de volta.
        
        Não é realmente uma floresta, considerando que tem arestas de árvore e arestas de volta.
        
        Possui alta eficiência. Tem tempo de travessia em Θ(V^2) na matriz de adjecência, e Θ(|V|+|E|) na lista de adjecência.
    - - Se busca em procura é "valente", busca em largura é cauteloso.
        
        Segue de maneira concentrada, visitando primeiro todas as vértices adjecentes à inicial, depois todas as não visitadas a 2 arestas de distância, continuando assim, até todas as vértices no mesmo componente conectado que a inicial são visitadas.
        
        Se sobrarem vértices não visitadas, o algoritmo é reiniciado em um ponto arbitrário não visitado.
      - É conveniente o uso de queues para traçar a operação.
      - É util acompanhar construindo uma floresta de busca em largura.
        
        O índice inicial sendo a raiz da primeira árvore na floresta. Novas vértices são ligadas a seu vértice pai com uma aresta árvore. Se a aresta leva a uma vértice previamente encontrada que não é seu predecessor, é uma cross aresta.
        
        BFS' podem ser usadas para checar conectividade e aciclidade do grafo, essencialmente da mesma forma que DFS'.
        
        Não é aplicável, porém, em aplicações menos diretas ao ponto.
        
        É util na busca de paths com o menor número de arestas entre 2 vértices.
      - Tem a mesma eficiência que Busca em Profundidade, Θ(V^2) na matriz de adjecência, e Θ(|V|+|E|) na lista de adjecência.
        
        Ao contrário de Busca em Profundidade, resulta em uma única ordem de vértice, pois a queue é uma FIFO, assim a ordem de inclusão de vértices é a mesma de remoção.
  - - - Vemos que para um digrafo sem ciclo direcionado não pode ter solução.
        
        Assim, para sorting topológico ser possível, o digrafo em questão precisa ser um dag (grafo direcionado acíclico).
        
        Há dois algoritmos eficientes que verificam se um digrafo é um dag, e se é, produz a ordem de vértices que resolve o sorting topológico.
        
        O primeiro é uma simples aplicação de busca a profundidade;
        
        percorre a DFS traversal e anota a ordem em que vértices viram becos sem saída.
        
        Revertendo tal ordem, temos a solução ao problema de topologia, contanto que nenhuma aresta de volta seja encontrado no percurso.
        
        1 more item...
        
        O segundo é uma aplicação do diminuir (por um) para conquistar.
        
        Repetidamente, identifica no digrafo a fonte, que é a vértice sem arestas vindo a ela, e deletar ela além de todas as vértices que saiem dela.
        
        A ordem em que as vértices são deletadas tras a solução ao problema de sorting topológico.