scientific article; zbMATH DE number 3937195

From MaRDI portal
Publication:3710539





This paper formalises the concept of rooted acyclic digraphs (RAD's). The main characteristics of RAD's are (i) RAD's have a finite number of terminal vertices, (ii) all vertices are reachable from some specified vertex designated as the root, (iii) all vertices are ranked, (iv) RAD's contain no cycles. A path entropy function is defined on a RAD which may be considered as a measure of the choices to the made when traversing the path from the root to a given vertex. A lower bound for the path entropy of a RAD is given. Next, a graph product is defined for RAD's. It is shown that the path entropy function is additive with respect to this graph product. These results are then generalized to the case when the terminal vertices are assigned weights. Many of the results in this paper are extensions of results proved by the first author for rooted trees. A possible application is that of obtaining bounds for the path entropy values of particular classification schemes.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3710539)