英和和英

出典:『Wikipedia』 (2011/02/19 00:48 UTC 版)

英語による解説

引用

In graph theory, the cycle rank of a directed graph is a digraph connectivity measure proposed first by Eggan and Büchi (). Intuitively, this concept measures how close a digraph is to a directed acyclic graph (DAG), in the sense that a DAG has cycle rank zero, while a complete digraph of order n with a self-loop at each vertex has cycle rank n. When applied to undirected graphs, the concept of cycle rank bears many different names in the research literature, including vertex ranking number, ordered chromatic number, minimum elimination tree height and tree-depth (, )