Please enable JavaScript.

Coggle requires JavaScript to display documents.

Grafos - Coggle Diagram

- - - - Essa informação é importante para sabermos como vamos representar o grafo e isso tem uma relação direta com a eficiência temporal
        
        Matriz de adjacência
        
        Esse método de representação consiste em criar uma matriz booleana nxn em que n = |V|, em que cada vértice "possui" uma linha e uma coluna, se o valor de um elemento é true(supondo que ele está na linha i e na coluna j), então o vértice relacionado a linha i está ligado ao vértice da coluna j
        
        Uma matriz de adjacência é sempre simétrica no caso de ser um grafo sem direção, ou seja, (u,v)=(v,u), ou ambos são 0 ou ambos são 1
        
        Os grafos densos são mais bem tratados (em relação a lista de adjacência)
        
        Lista de adjacência
        
        Consiste em um conjunto de linked lists, uma para cada vértice, cada linked list mostra todos os vértices que um vértice aponta
        
        No geral é melhor com grafos esparsos
  - - - A duas formas de representar grafos podem ser usadas para esse tipo de grafo
        
        No caso da matriz de adjacência, é só armazenarmos em cada célula o peso da aresta que liga os vértices relacionados a célula ( juntamente com a informação booleana),caso (u,v) não tenham ligação, então colocamos um símbolo especial para mostrar isso, a nova matriz vai se chamar de matriz de custos
        
        No caso da lista de adjacência, é só armazenarmos o peso da aresta junto com o nome do vértice em cada célula da linked list
  - - - Se todos os vértices na sequencia são diferentes então caminho é simples
      - O tamanho de um caminho é o números de vértices na sequência - 1, ou seja, é o número de arestas (ou a soma de seus pesos)
      - Em dígrafos, nós temos os Caminhos direcionados, que também são descritos como uma sequência de vértices, porém para cada par de vértices existe uma aresta direcionada (v,u) em que v é o termo que vem primeiro na sequência e u vem em seguida
      - Um grafo é conectado se para qualquer vértices u e v, existe um caminho de u para v
      - Um ciclo é um caminho de tamanho positivo que começa e termina no mesmo vértice ( um grafo sem ciclo é chamado de acíclico)
- - - - Um vértice inicial é escolhido arbitrariamente
        
        Marcamos o presente vértice como visitado e, em seguida, verificamos se existe algum vértice adjacente que não foi visitado
        
        Caso exista :
        
        Vamos para esse vértice e repetimos o processo
        
        Caso não exista, então voltamos para o vértice anterior e verificamos se ele tem algum adjacente não visitado:
        
        Se sim, então :
        
        Se não, então:
        
        Fazemos isso novamente, a condição de parada é chegar no vértice inicial e o mesmo não ter mais adjacentes não visitados (dead end)
    - - A eficiência vai depender da forma que foi usada para representar o grafo:
        
        Utilizando a matriz de adjacência, a eficiência fica em θ(|V|^2)
        
        Onde |V| e |E| são o número de elementos nos conjuntos de vértices e de arestas, respectivamente
        
        Utilizando a lista de adjacência, a eficiência fica em θ(|V| + |E|)
  - - - A DFS tem uma abordagem de profundidade, já a BFS em vez de ir mais fundo, ele faz a travessia de maneira mais ampla
        
        Ele começa com o vértice v, então marca todos os vértices adjacentes a v como visitados, após isso, masca-se como visitados todos aqueles adjacentes aos adjacentes de v, e assim por diante
        
        No caso de ainda haver vértices não visitados ( um grafo desconecto) reinicia-se o processo partindo de outro vértice arbitrário (que não foi visitado ainda)
- - - - num de arestas
- - - - Para esse problema ter solução é necessário( e suficiente) que o dígrafo seja dag
        
        "dag" significa directed acyclic graph ou grafo direcionado acíclico
      - Existem dois algoritmos para resolver esse problema:
        
        1º: Aplique o DFS e liste os vértices que se tornam dead ends ( em ordem), e depois inverta a ordem
        
        Caso tenha alguma aresta voltando para o vértice em que ela já passou então o problema não tem solução, pois o dígrafo não é um dag
        
        2º: Encontre uma fonte e remova ela e todas as arestas que saem dela, e repita esse processo, no caso de haver várias fontes, então devemos escolher uma arbitrariamente, e caso não tenha nenhuma, então o problema não tem solução pois o dígrafo não é dag
        
        Uma fonte é um vértice que não tem nenhuma aresta "entrando" nele
        
        A ordem de deleção gera uma solução para o problema
        
        A solução pode ser diferente, mas ambas vão estar corretas, pois a classificação topológica tem várias possíveis soluções