Please enable JavaScript.

Coggle requires JavaScript to display documents.

M10 (Levitin) - Coggle Diagram

- - - - Grafo
        
        É uma coleção de pontos no plano chamados "vértices" ou "nós", que podem estar conectados entre si através de "arestas" ou "arcos"
        
        Um grafo G é formalmente definido como G = <V, E>, isto é, como um par de conjuntos V e E, sendo V um conjunto finito não vazio dos elementos chamados "vértices" e E um conjunto das "arestas", que são duplas, ordenadas ou não, entre os vértices.
        
        Quando as duplas são não-ordenadas, representam uma aresta não-direcionada, e os vértices ligados por ela são considerados adjacentes uma ao outro e são "pontos finais" incidentes à aresta.
        Um grafo cujas únicas arestas são não-direcionadas é um grafo também não direcionado
        
        Quando a dupla é ordenada, a aresta é dita "direcionada"/"dirigida"/"orientada" da "cauda" (primeiro vértice) até a "cabeça" (segundo vértice).
        Um grafo cujas únicas arestas são todas direcionadas são também chamados de "direcionados"/"dirigidos"/"orientados" ou "dígrafos".
        
        As arestas que ligam um vértice a ele próprio são chamadas "laços".
        
        Todo grafo sem laços e sem múltiplas arestas ligando os mesmos pares de vértices, respeitam a desigualdade:
        0 <= |E| <= |V|(|V|-1)/2
        Em que |X| é a cardinalidade do conjunto X.
        
        Grafos em que todos os pares de vértices distintos estão ligados por uma aresta são chamados "completos"
        Quando o número de arestas é próxima do máximo admitido o grafo é "denso" e quando esse número é relativamente baixo, o grafo é "esparso"
        
        Em grafos pesados, cada aresta é associada a um valor, chamado "peso" ou "custo", os quais servem para distinguir as arestas entre si e indicar um "custo total" obtido num percurso de um vértice a outro, dependendo do caminho tomado, somando-se os pesos das arestas consideradas
        
        São normalmente representados de 2 formas:
        
        Como matrizes de adjacência, isto é, matrizes "booleanas" quadradas nxn (sendo n o número de vértices), com uma linha e uma coluna para cada um desses vértices, sendo 1 o valor da posição (i, j) caso exista uma aresta ligando o vértice da linha i ao da coluna j, e sendo 0 o valor nessa posição caso contrário.
        
        Para grafos pesados, a matriz deixa de ser booleana e cada posição passa a receber o custo da aresta determinada. Quando não há aresta, a posição é ocupada por um símbolo especial (geralmente algo como "∞", para indicar que o custo da travessia seria "absurdo", "inviável", "impossível") e em alguns casos utiliza-se outro símbolo para distinguir as posições de arestas laço (geralmente o "0", como se não houvesse custo para realizar a travessia)
        
        Em geral, para grafos esparsos, pode ser mais interessante a utilização de listas de adjacência, uma vez que poucas arestas irão precisar de poucos ponteiros, enquanto a matriz de adjacência gastaria espaço representando todas as arestas que não existem. Por outro lado, para grafos densos, o grande número de arestas torna necessária uma grande quantidade de ponteiros para as listas de adjacência, o que requer um grande custo de armazenamento em comparação ao tamanho fixo da matriz de adjacência desse mesmo grafo
        
        Como listas de adjacência, isto é, uma coleção de listas ligadas definidas pra cada vértice, em que cada lista contém um vértice como header e os vértices adjacentes a ele são dispostos após o header, ligados através de ponteiros para o nome do vértice
        
        Para grafos pesados, além de indicar a lista de nomes de vértices adjacentes à cada nó, é necessário armazenar o custo de cada aresta existente entre o header e o vértice adjacente
        
        Um "caminho" entre 2 vértices u e v de um grafo é definido como uma sequência de vértices adjacentes (conectados por uma aresta) iniciada em u e terminada em v
        
        Se todos os vértices de um caminho forem distintos, o caminho é chamado de "simples"
        
        O "comprimento" de um caminho é o número de arestas "percorridas", ou seja, o número de vértices da sequência menos 1
        
        Um caminho é "direcionado" quando todos os pares de vértices consecutivos da sequência estão no conjunto das arestas direcionadas do grafo
        
        Um grafo é "conexo" quando existe pelo menos um caminho entre quaisquer 2 de seus vértices.
        
        "Componentes conexos" de um grafo são subgrafos conexos que não conseguem ser expandidos para um grafo conexo maior com a adição de outros vértices e arestas pertencentes ao grafo total
        
        Um "ciclo" é um caminho de tamanho maior que zero que se inicia em um vértice e termina nele próprio, utilizando sempre arestas distintas do grafo
- - - - Busca em profundidade (Depth-first search ou DFS)
        
        Consiste em uma busca que prioriza caminhos "profundos", isto é, que partem de um vértice e seguem até outro mais "distante", a partir do qual é preciso retroceder para ser retomado recursivamente um novo caminho
        
        Parte-se de um vértice, marcando-o como "visitado", e "visita-se" um de seus vértices adjacentes que ainda não tenham sido visitados, repetindo o procedimento para cada vértice visitado até chegar em um vértice em que todos os seus adjacentes já foram visitados (chamado dead-end). Quando isso acontece, a busca retrocede um nó e realiza o mesmo procedimento até que, de maneira recursiva, retorne-se ao nó inicial sem que haja vértices não visitados adjacentes a ele.
        Caso ainda restem vértices não visitados no grafo, a DFS é novamente aplicada para qualquer um desses vértices. Dessa maneira, garante-se que todos os vértices serão visitados
        
        Devido ao seu caráter recursivo sempre em relação ao último nó visitado, a DFS geralmente é implementada por meio de uma pilha, na qual o vértice é pushed quanto visitado pela primeira vez e popped quando se torna um dead-end
        
        A travessia realizada pelo DFS é usualmente representada por meio de uma floresta de busca em profundidade, na qual cada conjunto de caminhos partindo de um vértice inicial é representado por um componente conexo do tipo árvore enraizado no primeiro vértice visitado e adicionando os novos vértices visitados como folhas, por meio de arestas chamadas tree edges.
        Quando é encontrado uma aresta que liga um nó a um antepassado seu que não seu pai, essa aresta é chamada back edge. Se essa aresta for considerada no grafo, então ele deixa de ser uma floresta propriamente dita
        
        Como todas operações de "marcação" e "visitação" são imediatas, a eficiência temporal depende somente do tamanho da data structure utilizada. Assim, para uma matriz de adjacência, a eficiência está em θ(|V|^2) (pois é uma matriz com |V|x|V| elementos) e para uma lista de adjacência, está em θ(|V|+|E|) (pois além dos |V| headers são visitadas as |E| arestas)
        
        Alguma de suas aplicações são:
        
        Verificar a conectividade do grafo, pois caso ainda restem nós não visitados após o vértice inicial da busca se tornar um dead-end, então depreende-se que existe mais de um componente conexo na árvore. Caso contrário, todos os vértices deveriam ter sido visitados, pois todos os caminhos partindo do vértice inicial foram percorridos
        
        Verificar a aciclicidade do grafo, pois se nenhuma back edge for encontrada, então certamente o grafo é acíclico, e caso contrário, ele contém ciclos internos
        
        Encontrar pontos de articulação do grafo (pontos cuja remoção divide o grafo em mais componentes conexos)
      - Busca em largura (Breadth-first search ou BFS)
        
        Consiste em uma busca que prioriza verificar o "entorno" de um vértice, isto é, todos os vértices que são adjacentes a ele, antes de aumentar o comprimento do caminho
        
        Parte-se de um vértice, marcando-o como "visitado" e "visita-se" todos os vértices adjacentes a ele que ainda não foram visitados (a ordem em que essa visitação é feita pode ser escolhida arbitrariamente). Em seguida, repete-se o procedimento para cada um dos nós adjacentes até que todos os últimos nós visitados em cada caminho só tenham nós adjacentes já visitados (os quais também são chamados de dead-ends)
        Se ainda restarem vértices não visitados no grafo, então a BFS é aplicada novamente em um desses vértices, até que todos os vértices do grafo tenham sido visitados
        
        Devido ao seu caráter recursivo sempre na ordem em que os vértices são visitados, a BFS geralmente é implementada por meio de uma fila, na qual os vértices são enqueued na ordem em que são identificados e dequeued na ordem em que são visitados.
        
        Também é útil representar a travessia realizada pelo BFS como uma floresta de busca em largura, na qual cada conjunto de caminhos partindo de um vértice inicial é representado por um componente conexo do tipo árvore enraizado no primeiro vértice visitado e adicionando os novos vértices visitados como folhas, por meio de arestas chamadas tree edges.
        Quando é encontrado uma aresta que liga um nó a um antepassado seu que não seu pai, essa aresta é chamada cross edge. Se essa aresta for considerada no grafo, então ele deixa de ser uma floresta propriamente dita
        
        Assim como na DFS, todas operações de "marcação" e "visitação" são imediatas, a eficiência temporal depende somente do tamanho da data structure utilizada. Assim, para uma matriz de adjacência, a eficiência está em θ(|V|^2) (pois é uma matriz com |V|x|V| elementos) e para uma lista de adjacência, está em θ(|V|+|E|) (pois além dos |V| headers são visitadas as |E| arestas)
        
        Alguma de suas aplicações são:
        
        Verificar a conectividade do grafo, pois caso ainda restem nós não visitados após os últimos vértices de cada caminho se tornarem dead-ends, então depreende-se que existe mais de um componente conexo na árvore. Caso contrário, todos os vértices deveriam ter sido visitados, pois todos os caminhos partindo do vértice inicial foram percorridos
        
        Verificar a aciclicidade do grafo, pois se nenhuma cross edge for encontrada, então certamente o grafo é acíclico, e caso contrário, ele contém ciclos internos
        
        Encontrar o caminho de menor comprimento entre dois vértices, pois partindo de um deles, quando o outro vértice for visitado, o caminho único encontrado até então entre eles será necessariamente o menor, pois os caminhos partindo do vértice inicial são todos encontrados em ordem crescente de comprimento
- - - - Existem 4 tipos de arestas ao invés de 2: tree edges (que liga um vértice a seu filho), back edges (que liga um vértice a um ancestral seu), forward edges (que liga um vértice a um descendente seu que não seja seu filho) e cross edges (que liga vértices sem relação de "parentesco", ou seja, ligam nós de componentes conexos distintos, considerando tree edges como as únicas arestas da floresta)
      - Um ciclo direcionado é uma sequência de três ou mais vértices que se inicia e termina no mesmo vértice. Com exceção da aresta entre os dois últimos vértices, que é evidentemente uma back edge, as demais arestas devem ser tree edges
        
        Consequentemente, um dígrafo sem back edge não possui ciclos direcionados, e é portanto denominado um grafo direcionado acíclico (directed acyclic graph ou dag)
      - É possível aplicar essa estrutura para resolver um problema de
        
        Ordenação Topológica
        
        Consiste em um sequenciamento em que, para todo par ordenado (u, v) de vértices ligados por uma aresta direcionada, a "cauda" está sempre em uma posição anterior à posição da "cabeça". Ou seja, é uma ordem em que, considerando uma aresta qualquer do grafo, o vértice antecessor está sempre em uma posição anterior ao seu sucessor
        
        Como uma back edge de uma DFS faz um vértice ser ao mesmo tempo antecessor e sucessor de outros vértices, então para ser possível realizar uma ordenação topológica é necessário que o grafo seja um dag
        
        Também é suficiente que o grafo seja uma dag para ter uma ordenação topológica, pois nesse caso há sempre pelo menos um vértice sem antecessor que pode servir como primeiro vértice da ordenação, a partir do qual são encontrados os demais vértices daquele mesmo componente conexo
        
        Duas implementações comuns dessa ordenação são:
        
        1) Aplicar a DFS de maneira que a ordem desejada é o inverso da ordem em que os vértices são popped da pilha, pois um vértice u antecedente a outro v é necessariamente removidos depois, do contrário a aresta direcionada (u, v) seria uma back edge, e havendo back edges na DFS, a ordenação topológica não pode ser realizada
        
        2) Aplicar um algoritmo que busca repetidamente um vértice sem antecedentes (chamado "fonte" ou source) e o remove do grafo juntamente com as arestas anexadas a ele, repetindo o procedimento até que não restem mais vértices. A ordem em que esses vértices são removidos é a ordem desejada, pois os vértices estão removidos em ordem crescente do número de antepassados, e como um sucessor tem sempre mais antepassados que seu antecessor, então ele está sendo removido posteriormente