【木のDAG】
木に単一の方向性を持たせるとDAGになる
割り振り直した頂点IDは降順あるいは昇順になる
このようなDAGは木でもあるので元の頂点IDはユニークでもある
頂点の割り振り直し方法
・DAGの最長経路=木の根からの深さ=末端からMAXのBFS、で頂点IDを割り振り直すと最小化
・根からBFSまたはDFSで頂点IDを割り振り直すと全頂点ユニークIDになる、このとき頂点IDは最大化される
【一般的なDAG】
割り振り直した頂点IDは降順あるいは昇順、元の頂点IDはユニーク
頂点の割り振り直し方法
・DAGの最長経路=木の根からの深さ=末端からMAXのBFS、で頂点IDを割り振り直すと最小化