跳到主要内容

東京大学 新領域創成科学研究科 メディカル情報生命専攻 2022年8月実施 問題9

Author​

zephyr

Description​

Let be a directed acyclic graph such that is the set of integers from to . We will consider the following sets of edges for .

(1) Consider a bijective function from to such that for any . For each of and , answer the number of all different bijective functions and the rationale.

(2) For each of and , answer the number of all different paths from to (or a recurrence for computing the number), and the rationale.

(3) For any directed acyclic graph , design an algorithm that calculates the number of paths from to in time for any , and explain the rationale.

Kai​

(1) Bijective Functions​

Bijective Function Explanation​

A bijective function is a function that is both injective (one-to-one) and surjective (onto). This means every element in maps to a unique element in , and every element in is mapped to by exactly one element in . For the given problem, we are interested in bijective functions that also respect the condition for any edge .

For ​

  • Structure: The graph with edges has two types of edges: from vertex 1 to every other vertex , and from every vertex to vertex . Thus, must be the smallest and must be the largest.

  • Ordering: The remaining values must be placed in increasing order between and .

  • Number of bijective functions: Given that and are fixed as the smallest and largest respectively, the remaining vertices can be permuted freely.

For ​

  • Structure: The graph with edges has edges from each vertex to and .

  • Ordering: For to satisfy for all , must be in ascending order for all .

  • Number of bijective functions: There is only one valid permutation: the natural ordering .

(2) Number of Paths from to ​

For ​

  • Path Analysis: From to , the paths must pass through an intermediate vertex .

  • Paths: Each vertex in provides a unique path .

For ​

  • Path Analysis: From to , paths can be analyzed using dynamic programming:

    Define as the number of paths from to .

  • Base cases: (direct path from 1 to 1)

  • For , there is also a direct path, so .

  • Recurrence relation: Compute the number of paths to each vertex until .

(3) Algorithm for Number of Paths in a DAG​

Algorithm​

  • Initialize an array of size to store the number of paths to each vertex.
  • Initialize for the starting vertex .
  • Traverse the vertices in topological order, and update the number of paths to each vertex based on the incoming edges.
    • For each vertex , iterate over its incoming neighbors and update .
  • Once all vertices are processed, the number of paths to the destination vertex will be stored in .

Time Complexity​

  • The topological sort can be done in time.
  • Updating the number of paths for each vertex takes time.
  • Thus, the overall time complexity is .

Knowledge​

图论 有向无环图 拓扑排序 动态规划 双射函数

难点解题思路​

在 Part 1 中，需要理解图的结构及其对函数 的约束。在 Part 2 中，关键在于找出从起点到终点的所有可能路径数目，并用动态规划求解。在 Part 3 中，难点在于设计有效算法，通过拓扑排序和动态规划计算从起点到终点的路径数目。

解题技巧和信息​

对于有向无环图 (DAG) 相关的问题，拓扑排序和动态规划是常用的解题技巧。在这个问题中，我们需要理解图的结构，找出有效的算法来计算从起点到终点的路径数目。

重点词汇​

  • directed acyclic graph (DAG) 有向无环图
  • topological order 拓扑排序
  • dynamic programming 动态规划
  • bijective function 双射函数
  • recurrence 递推关系

参考资料​

  1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. Chap. 22 (Elementary Graph Algorithms), Chap. 24 (Single-Source Shortest Paths).