有向グラフ内の最大異なるDAGの数?

有向グラフ$ overrightarrow {G} $が与えられると、私は$ overrightarrow {G}
$からすべてのDAGを抽出することに興味があります:

  1. 各DAGの頂点のソート方法が異なります。
  2. 各DAGは最大です(余分なエッジを追加するとDAGプロパティに違反します)
  3. 各DAGは$ overrightarrow {G} $の頂点全体を含む必要があります。

Obviously, the union of DAGs with above conditions recreates
$overrightarrow{G}$ again and any path given on
$overrightarrow{G}$ is traceable on DAGs. Any simple path on
$overrightarrow{G}$ can be wholly found at some DAG whose root is
the starting point of the path. Given a non-simple path, one can
move through different DAGs efficiently to trace the path as well
(e.g. path $a c d b a b$ can be traced by starting from the DAG
with node $a$ going to $c$, then switching to the DAG with the root
$d$, again switching back to the DAG with root $a$ and going to
$b$). Path $a c d b a b$ can be traced by starting the DAG with node a going to c, then switching to the DAG with the root d, then again DAG with root a and going to b.

私の意図は、データ構造に効率的にDAGを格納して、$ overrightarrow {G}
$上の任意のパスに対してそれらを素早く抽出することです。上記の特性を持つDAGはいくつあるか?そのようなDAGを計算するための多項式時間アルゴリズムはありますか?この時点で提案できる関連論文はありますか?

ベストアンサー
申し訳ありませんが、適切な答えはありません

返信を残す

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です