Please enable JavaScript.

Coggle requires JavaScript to display documents.

Grafos, Topological Sorting - Coggle Diagram

- - - - Nossa definição de grafo não proíbe loops ou arestas conectando vértices para eles mesmos. Uma vez que nossa definição não permite arestas múltiplas entre os mesmos vértices de um grafo não direcionado, temos a seguinte desigualdade para o número de arestas | E | possível em um grafo não direcionado com | V | vértices e sem loops : 0 ≤ |E|≤|V |(|V | − 1)/2.
        
        Um grafo com cada par de seus vértices conectados por uma aresta é chamado de completo. Um grafo com relativamente poucas arestas possíveis faltando é chamado de denso; um grafo com poucas arestas em relação ao número de seus vértices é chamado esparso. Se estamos lidando com um grafo denso ou esparso pode influenciar a forma como escolhemos representar o grafo e, conseqüentemente, o tempo de execução de um algoritmo que está sendo projetado ou usado.
- - - - No caso de um grafo direcionado, geralmente estamos interessados em caminhos direcionados.Um caminho direcionado é uma sequência de vértices em que cada par consecutivo dos vértices são conectados por uma aresta direcionada do vértice listado primeiro para o vértice listado a seguir.
        
        Diz-se que um grafo está conectado se para cada par de seus vértices u e v há um caminho de u a v. Se um gráfico não estiver conectado, tal modelo consistirá de várias peças conectadas que são chamadas de componentes conectados do gráfico. Formalmente, um componente conectado é um máximo (não expansível incluindo outro vértice e uma aresta) subgrafo conectado 2 de um dado gráfico.
        
        Um ciclo é um caminho de comprimento positivo que começa e termina no mesmo vértice e não atravessa a mesma aresta mais de uma vez.Um gráfico sem ciclos é dito seja acíclico.
- - - - Pode ser colocado para um dígrafo arbitrário, mas é fácil ver que o problema não pode ter uma solução se um dígrafo tem um ciclo direcionado. Assim, para que a classificação topológica seja possível, um dígrafo em questão deve ser um dag. Acontece que ser um dag não é apenas necessário mas também suficiente para que a classificação topológica seja possível; ou seja, se um dígrafo não tem ciclos dirigidos, o problema de classificação topológica para isso tem uma solução. Além disso, existem dois algoritmos eficientes que verificam se um dígrafo é um dag e, se for, produz uma ordenação de vértices que resolve a ordenação topológica.