como funciona ordem topologica de grafos? heeelllpppp :)
Soluções para a tarefa
Respondido por
0
Em teoria dos grafos, uma ordenação topológica de um digrafo acíclico (DAG) é uma ordem linear de seus nós em que cada nó vem antes de todos nós para os quais este tenha arestas de saída. Cada DAG tem uma ou mais ordenações topológicas.
Mais formalmente, define-se a relação acessibilidade R sobre os nós do DAG tal que xRy se e somente se existe um caminho dirigido de x para y. Então, R é uma ordem parcial, e uma ordenação topológica é uma extensão linear desta ordem parcial, isto é, uma ordem total compatível com a ordem parcial.
Mais formalmente, define-se a relação acessibilidade R sobre os nós do DAG tal que xRy se e somente se existe um caminho dirigido de x para y. Então, R é uma ordem parcial, e uma ordenação topológica é uma extensão linear desta ordem parcial, isto é, uma ordem total compatível com a ordem parcial.
Perguntas interessantes
Matemática,
9 meses atrás
Saúde,
9 meses atrás
Matemática,
9 meses atrás
História,
1 ano atrás
Matemática,
1 ano atrás
Física,
1 ano atrás