论文标题
计数定向的无环和基本挖掘
Counting directed acyclic and elementary digraphs
论文作者
论文摘要
可以将定向的无环图（DAG）表征为有向图的图形，其强烈连接的组件是孤立的顶点。使用对强组件的这种限制，我们发现，当$ m = cn $（$ m $）是有向边的数量时，$ n $是顶点的数量，而$ c <1 $，随机挖掘物是acyclaph是acyclic的渐近可能性，即明确的功能$ p（c）$ P（0）$ P（0）= 1 $ $ p（1 $ p（1）= 0 $ p（1）= 0 $ p（1）= 0 $ p（1）= 0。当$ m = n（1 +μn^{ - 1/3}）$时，渐近行为会发生变化，并且digraph为acyclic的可能性变为$ n^{ - 1/3} c（μ）$，其中$ c（μ）$是$ $ $ $ $ $ $的明确函数。 uczak and Seierstad（2009年，随机结构和算法，35（3），271--293）表明，作为$μ\ to-\ to-\ infty $，具有$ n $ Vertices和$ m = n（1 +μn^^niment and的$ n $ digraph的紧密连接的组件）周期。我们称此类Digraphs基本挖掘物。我们表明，随机挖掘是基本的，这是$μ$的函数。这些结果是使用来自分析组合学技术的技术，特别是为了研究随机图而开发的。
Directed acyclic graphs (DAGs) can be characterised as directed graphs whose strongly connected components are isolated vertices. Using this restriction on the strong components, we discover that when $m = cn$, where $m$ is the number of directed edges, $n$ is the number of vertices, and $c < 1$, the asymptotic probability that a random digraph is acyclic is an explicit function $p(c)$, such that $p(0) = 1$ and $p(1) = 0$. When $m = n(1 + μn^{-1/3})$, the asymptotic behaviour changes, and the probability that a digraph is acyclic becomes $n^{-1/3} C(μ)$, where $C(μ)$ is an explicit function of $μ$. Łuczak and Seierstad (2009, Random Structures & Algorithms, 35(3), 271--293) showed that, as $μ\to -\infty$, the strongly connected components of a random digraph with $n$ vertices and $m = n(1 + μn^{-1/3})$ directed edges are, with high probability, only isolated vertices and cycles. We call such digraphs elementary digraphs. We express the probability that a random digraph is elementary as a function of $μ$. Those results are obtained using techniques from analytic combinatorics, developed in particular to study random graphs.
