Por que os gráficos direcionados são importantes?

18

Temos lido sobre algoritmos para MST, conectividade forte, roteamento etc. em gráficos direcionados.

Também recentemente, as pessoas vêm pesquisando algoritmos dinâmicos e tolerantes a falhas para gráficos direcionados.

Mas eu queria saber se existem aplicações práticas nas quais a rede gráfica subjacente é "Dirigida". Além das redes sociais, todos os problemas em que eu conseguia pensar, como rede ferroviária / rodoviária, rede da Internet etc., lidam apenas com gráficos não direcionados.

Edit 1: Entendo que eles podem ser usados ​​para modelar alguns cenários em que os links são direcionados, mas eu queria saber com que freqüência esses cenários ocorrem no mundo real e qual a importância do estudo da tolerância a falhas para gráficos direcionados.

graphs graph-theory fault-tolerance quilo
fonte
6
Duas das classes mais famosas de gráficos direcionados em toda a ciência da computação são a árvore e o DAG (Directed Acyclic Graph). A árvore é usada em muitas coisas (por exemplo, árvores genealógicas, hierarquias); O DAG pode fazer versões mais sofisticadas delas. Os DAGs são usados ​​essencialmente sempre que você tem um conjunto de entidades que dependem umas das outras. Quando o seu problema tem um componente "tempo" ou "passo a passo", a direcionamento representa essa marcha inexorável do progresso. Você vê DAGs em diagramas de fluxograma, software de gerenciamento de pacotes e formulários SSA de representação intermediária dos compiladores.
Iwillnotexist Idonotexist
2
OK, qual é a sua pergunta real? Deseja saber por que os gráficos direcionados são importantes ou por que a tolerância a falhas nos gráficos direcionados é importante? Essas são duas perguntas completamente separadas.
David Richerby
2
Seus exemplos, embora fisicamente "não direcionados" na implementação, ainda frequentemente direcionam gráficos operando logicamente sobre eles. Por exemplo, os trens não viajam bidirecionalmente - eles seguem um caminho ou o outro de acordo com o cronograma. Digamos que um não agende os trens, mas apenas agende passageiros. Então, essa pessoa está interessada em um gráfico direcionado, apesar do fato arbitrário de que os trens podem teoricamente viajar de qualquer maneira em um trilho.
Darren Ringer
5
chyle: As redes certamente podem se beneficiar de serem representadas por um gráfico direcionado. A maioria das conexões domésticas à Internet é assimétrica. As ligações a montante ea jusante podem ter propriedades completamente diferentes (largura de banda, latência, perda de pacotes, etc.)
Alexander - Reintegrar Monica
1
Não conheço todos os outros, mas minha árvore genealógica é um dígrafo. Eu não sou pai da minha mãe.

Respostas:

36

Lembrando que um gráfico direcionado é um gráfico em que as arestas têm uma direção associada a elas.

Usando um gráfico direcionado, você pode representar relacionamentos assimétricos entre os nós, enquanto no gráfico não direcionado, podemos representar apenas relacionamentos simétricos .

Praticamente, usando um gráfico direcionado, você pode representar:

  • Redes rodoviárias (usando um gráfico direcionado, você pode representar a direção das ruas);
  • hiperlinks para conectar páginas da web ;
  • dependências em módulos de software ;
  • relações presa-predador ;
  • autômato finito determinístico .

Além desses exemplos clássicos, você pode representar muitos outros cenários do mundo real (comércio financeiro, programação, doenças infecciosas, citações, fluxo de controle etc.) que precisam de um relacionamento ordenado [1] .

darioSka
fonte
4
Ótima resposta. Acho que o OP está esquecendo que quando você tem uma rua, na verdade você tem duas ruas (uma para cada direção, geralmente perfeitamente paralela). Eles podem ser representados como um gráfico simples, mas os gráficos direcionados adicionam informações essenciais ao modelo.
ECC
Gosto disso e percebo que esta resposta é cuidadosa ao dizer hiperlink em páginas da web conectadas - o que exclui o uso da função Voltar. ;-)
SDsolar 2/17/17
Para colocar o comentário do @ ecc no vernáculo, você tem dois nós conectados por duas arestas. Cada aresta é direcionada oposta à outra. É visto frequentemente em diagramas de estados determinísticos. Nas ruas, isso reduziria a uma única borda, seja direcionada (unidirecional) ou não direcionada.
SDsolar
4
@ecc também, de onde eu sou (California), temos ruas de sentido único
k_g
5

Gráficos direcionados existem. Conforme mencionado nos comentários, os Directed Acyclic Graphs (DAGs), em particular, são tremendamente úteis em muitas tarefas computacionais, como a compilação de código.

Além disso, é importante notar que a maioria dos algoritmos de gráfico direcionado pode ser usada no caso não direcionado, simplesmente substituindo cada aresta não direcionada por duas arestas direcionadas. O duplo disso, tentando criar um gráfico direcionado a partir de um gráfico não direcionado, não pode ser feito para a maioria dos algoritmos.

Cort Ammon - Restabelecer Monica
fonte
3

O início da classificação topológica (uma operação fundamental em gráficos acíclicos direcionados) reside em redes de dependências no gerenciamento de projetos, especificamente no método PERT . Kahn e Lasser citam PERT em seus trabalhos e baseiam seus exemplos, por exemplo,

Uma rede PERT de 30.000 atividades pode ser solicitada em menos de uma hora de tempo da máquina.

O agendamento de trabalhos on-line ainda é feito com esse tipo de rede; por exemplo, um sistema ETL agenda os trabalhos para serem executados somente após a execução dos trabalhos que fornecem seus dados de entrada.

KWillets
fonte
2

Resposta: No OP, deduzo que a pergunta está realmente relacionada aos ODS (gráficos direcionados assinados). Então, aqui está a minha resposta, que aborda gráficos direcionados básicos e leva aos ODS.

Gráficos direcionados são amplamente utilizados na análise de árvores de falhas em sistemas industriais. Ao eliminar as causas de uma falha, siga o gráfico direcionado para explorar outras possibilidades.

Gráficos direcionados são utilizados para evitar revisitações contraproducentes de nós que foram efetivamente eliminados. No diagnóstico de falhas, geralmente o tempo para a restauração do serviço é crítico. Em sistemas industriais complexos, sempre existe uma árvore paralela com base no tempo, que pode levar ao desligamento total do sistema se a falha não for corrigida dentro de várias limitações de tempo. Ir e voltar seria mais provável que levasse à falha total, o que pode causar operações de restauração muito mais demoradas (como drenagem de tanques e tubulações para reiniciar uma refinaria).

É como aparar um galho de árvore - não é necessário voltar ao tronco quando você tenta encontrar um único galho.

Os ODS têm a propriedade adicional de fornecer orientação com base em probabilidades ou limites, a fim de ajudar a tomar decisões à medida que a árvore é percorrida.

Aqui está um link para um bom livro sobre o assunto, chamado Detecção e diagnóstico de falhas em sistemas industriais (página 224), onde descreve os benefícios do diagnóstico baseado em SDG:

https://books.google.com/books?id=KFLlBwAAQBAJ&pg=PA224

SDsolar
fonte