Skip to content

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

Author

zephyr

Description

Let \(G = (V, E)\) be a directed acyclic graph such that \(V\) is the set of integers from \(1\) to \(n\) \((n \geq 3)\). We will consider the following sets of edges for \(E\).

\[ E_1 = \{(1, i), (i, n) \mid i = 2, \ldots, n-1\} \]
\[ E_2 = \{(i, i+1) \mid i = 1, \ldots, n-1\} \cup \{(i, i+2) \mid i = 1, \ldots, n-2\} \]

(1) Consider a bijective function \(f\) from \(V\) to \(V\) such that \(f(u) < f(v)\) for any \((u, v) \in E\). For each of \(E_1\) and \(E_2\), answer the number of all different bijective functions and the rationale.

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

(3) For any directed acyclic graph \(G = (V, E)\), design an algorithm that calculates the number of paths from \(s\) to \(t\) in \(O(|V| + |E|)\) time for any \(s, t \in V\), and explain the rationale.

Kai

(1) Bijective Functions

Bijective Function Explanation

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

For \(E_1\)

  • Structure: The graph \(G\) with edges \(E_1\) has two types of edges: from vertex 1 to every other vertex \(i \in \{2, \ldots, n-1\}\), and from every vertex \(i \in \{2, \ldots, n-1\}\) to vertex \(n\). Thus, \(f(1)\) must be the smallest and \(f(n)\) must be the largest.

  • Ordering: The remaining values \(\{f(2), \ldots, f(n-1)\}\) must be placed in increasing order between \(f(1)\) and \(f(n)\).

  • Number of bijective functions: Given that \(f(1)\) and \(f(n)\) are fixed as the smallest and largest respectively, the remaining \(n-2\) vertices can be permuted freely.

\[ (n-2)! \]

For \(E_2\)

  • Structure: The graph \(G\) with edges \(E_2\) has edges from each vertex \(i\) to \(i+1\) and \(i+2\).

  • Ordering: For \(f\) to satisfy \(f(u) < f(v)\) for all \((u, v) \in E_2\), \(f(i)\) must be in ascending order for all \(i\).

  • Number of bijective functions: There is only one valid permutation: the natural ordering \(f(i) = i\).

\[ 1 \]

(2) Number of Paths from \(1\) to \(n\)

For \(E_1\)

  • Path Analysis: From \(1\) to \(n\), the paths must pass through an intermediate vertex \(i\).

  • Paths: Each vertex \(i\) in \(\{2, \ldots, n-1\}\) provides a unique path \(1 \rightarrow i \rightarrow n\).

\[ \text{Number of paths} = n-2 \]

For \(E_2\)

  • Path Analysis: From \(1\) to \(n\), paths can be analyzed using dynamic programming:

Define \(P(k)\) as the number of paths from \(1\) to \(k\).

\[ P(k) = P(k-1) + P(k-2) \]
  • Base cases: \(P(1) = 1\) (direct path from 1 to 1)

  • For \(P(2)\), there is also a direct path, so \(P(2) = 1\).

  • Recurrence relation: Compute the number of paths to each vertex until \(P(n)\).

(3) Algorithm for Number of Paths in a DAG

Algorithm

  • Initialize an array \(P\) of size \(|V|\) to store the number of paths to each vertex.
  • Initialize \(P(s) = 1\) for the starting vertex \(s\).
  • Traverse the vertices in topological order, and update the number of paths to each vertex based on the incoming edges.
  • For each vertex \(v\), iterate over its incoming neighbors \(u\) and update \(P(v) += P(u)\).
  • Once all vertices are processed, the number of paths to the destination vertex \(t\) will be stored in \(P(t)\).

Time Complexity

  • The topological sort can be done in \(O(|V| + |E|)\) time.
  • Updating the number of paths for each vertex takes \(O(|E|)\) time.
  • Thus, the overall time complexity is \(O(|V| + |E|)\).

Knowledge

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

难点解题思路

在 Part 1 中，需要理解图的结构及其对函数 \(f\) 的约束。在 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).