Talk:Directed acyclic graph

From Wikipedia, the free encyclopedia

Contents 1 Missing term definition 2 Wikipedia Categories 3 Definition 4 Longest path

[edit] Missing term definition

I can not find the term "dicycle" explained in the graph theory glossary.

Thanks for the heads up. I fixed this, and added some explanation and images to the pages describing it. Deco 00:17, 19 Jun 2005 (UTC)

[edit] Wikipedia Categories

Directed they are, but acyclic they are not ;-) Gabriel Wicke 09:02, 4 November 2005 (UTC)

There's a category that indirectly includes itself? Really? Deco 09:09, 4 November 2005 (UTC)

I don't know if there is, but there certainly could be. --Saforrest 04:14, 24 February 2006 (UTC)

But should most categories avoid directed cycles? If we had a cycle in the category tree, then all its vertices (categories) would have an identical set of "subarticles", say articles belonging to a category directly or indirectly. It is not good, generally. гык 07:08, 23 May 2006 (UTC)

[edit] Definition

"for any vertex v", I believe should be "for all verticies", because if any of the verticies are part of a cycle then the graph is not a DAG.

[edit] Longest path

Should we note that finding the longest path in a weighted graph is NP-hard, except for DAGs?