Please enable JavaScript.
Coggle requires JavaScript to display documents.
MM11 - Coggle Diagram
MM11
Graphs
Formalmente: Grafo G = <V, E> é definido por um par de dois conjuntos: um conjunto finito e não vazio V de itens chamados
vértices
e um conjunto de E de pares desses itens chamados
arestas
Se esses pares de vértices são desordenados, ou seja, um par de vértices (u, v) é igual ao par (v, u), dizemos que os vértices u e v são adjacentes entre si e que estão conectados por uma borda não direcionada (u, v)
Se um par de vértices (u, v) não é igual ao par (v, u), dizemos que a aresta (u, v) é direcionada do vértice u, chamada de cauda da aresta, até o vértice v, chamada de cabeça da borda
Um grafo cujas arestas são direcionadas é chamado de direcionado
Graphs direcionados também são chamados de dígraphs
A aresta (u, v) sai de u e entra em v
É conveniente rotular os vértices de um graph ou dígraph com letras, números inteiros ou, se uma aplicação assim o exigir, cadeias de caracteres
É informalmente pensando como uma coleção de pontos no plano chamados “vértices” ou “nós”, alguns deles conectados por segmentos de linha chamados “arestas” ou “arcos”
A definição de graphs não proíbe loops ou arestas conectando vértices a si mesmo, a menos que seja explicitamente indicado o contrário
Como a definição não permite múltiplas arestas entre os mesmos vértices de um graph não direcionado, tem a seguinte desigualdade para o número de arestas |E| possíveis para um graph não direcionado com |V| vértices e sem loop:
Obtemos o maior número de arestas em um graph se houver uma aresta conectado cada um de seus |V| vértices com todos os |V-1| outros vértices
Um graph com cada par de seus vértices conectados por uma aresta é chamado
completo
Uma notação padrão para o graph completo com vértices |V| é K|v|
Um graph com relativamente poucas arestas possíveis faltando é chamado de
denso
Um graph com poucas arestas em relação ao número de seus vértices é chamado
esparso
O fato de estar lidando com um graph denso ou esparso pode influenciar na forma como escolher representar o graph e, consequentemente, o tempo de execução do algoritmo que está sendo usado
Representação do graph: são geralmente representados de duas maneiras: a matriz de adjacência e as listas de adjacência
As
listas de adjacência
de um graph ou dígraph são uma coleção de listas encadeadas, uma para cada vértice, que contém todos os vértices adjacentes ao vértice da lista (ou seja, todos os vértices conectados a ela por uma aresta)
Normalmente, essas listas começam com um cabeçalho que identifica um vértice para o qual a lista é copilada
Dito de outra maneira, essas listas indicam a coluna da matriz em que o índice é 1
A
matriz de adjacência
de um graph com n vértices é uma matriz n x n booleana com uma linha e uma coluna para cada um dos vértices do graph, em que o elemento da i-ésima linha e j-ésima coluna é igual a 1 se houver
aresta e 0 se não houver essa aresta
Graphs ponderados:
graph ponderado (ou dígraph ponderado) é um graph (ou dígraph) com números atribuídos as suas arestas
Esses números são chamados de pesos ou custos
O interesse nesse tipo de graph é motivado por inúmeras aplicações no mundo real, como encontrar o caminho mais curto entre dois pontos em uma rede de transporte ou comunicação
Ambas as representações de graph podem ser adotadas para acomodar um graph ponderado. Se for representado por uma matriz, então seu elemento A [i, j] conterá o peso da aresta do i-ésimo ao j-ésimo termo vértice se existir tão aresta e um símbolo especial caso não exista
Essa matriz é chamada de matriz de peso ou matriz de custo
Para as listas para um graph ponderado em seus nós não aparecer apenas o nome de um vértice adjacente, mas também o peso da aresta correspondente
Caminhos e ciclos:
dentre muitas propriedades, duas são importantes para um grande número de aplicação: conectividade e aciclicidade (ambos baseados na noção de caminho)
Um caminho do vértice u ao vértice v do graph G pode ser definido como uma sequência de vértices adjacentes (conectados por uma aresta) que começa com u e termina com v. Se todos os vértices de um caminho são distintos, diz-se que o caminho é simples
O comprimento de um caminho é o número total de vértices na sequência de vértices que define o caminho menos 1, que é igual ao número de arestas no caminho
Depth-First Seach
Inicia a travessia de um graph em um vértice arbitrário, marcando o como visitado. Em cada interação, o algoritmo prossegue para um vértice não visitado que é adjacente aquele em que se encontra atualmente
Por questão prática, qual dos candidatos adjacentes não visitados é escolhido é ditado pela estrutura de dados que representa o graph. Esse processo continua até um beco sem saída – um vértice sem vértices adjacentes não visitados- seja encontrado
Em um beco sem saída, o algoritmo faz backup de uma aresta até o vértice de onde veio e tenta continuar visitando vértices não visitados a partir daí. Eventualmente o algoritmo para após voltar ao vértice inicial, sendo este o último beco sem saída
Breadth-First
Seach
Ele prossegue ne maneira concêntrica visitando primeiro todos os vértices adjacentes a um vértice inicial, depois todos os vértices não visitados a duas arestas de distância dele, e assim por diante, até que todos os vértices no mesmo componente conectado do vértice inicial sejam visitados
Se ainda restarem vértices não visitados, o algoritmo deverá ser reinicializado em um vértice arbitrário de outro componente conectado ao graph
Topological Sorting
Em termos desde dígraph, a questão é se podemos listar seus vértices em tal ordem que, para cada aresta do graph, o vértice onde a aresta começa seja listado antes do vértice onde a aresta termina, este problema é chamado ordenação topológica
Para que seja possível o dígraph em questão deve ser um dag (graph acíclico direcionado)
Ser um dag não é apenas necessário, mas também suficiente para que a ordenação topológica seja possível, ou seja, se um dígraph não tem ciclos direcionados, o problema de classificação topológica para ele tem uma solução
O primeiro algoritmo é uma aplicação simples do depth-first seach: execute uma travessia DFS e observe a ordem na qual os elementos se tornam becos sem saída (ou seja, são retirados da pilha de travessia)
A inversão dessa ordem produz uma solução para o problema de classificação topológica, desde que nenhuma aresta posterior tenha sido encontrada durante a travessia. Se uma aresta posterior foi encontrada, o dígraph não é um dag e classificação topológica dos seus vértices é impossível
O segundo algoritmo é baseado em uma técnica direta da técnica diminuir para conquistar: repetidamente, identifique em um dígraph restante uma fonte, que é um vértice sem aresta de entrada, e exclua-o junto com todas as arestas saindo dele
Se houver várias fontes, desfaça o empate arbitrariamente. Se não houver nenhuma, pare porque o problema não pode ser resolvido
A ordem em que os vértices são excluídos produz uma solução para o problema de classificação topológica
A solução obtida pelo algoritmo de remoção fonte é diferente daquela obtida pelo algoritmo baseado em DFS, ambos estão corretos. O problema de classificação topológica pode ter várias soluções alternativas
