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

标签：

• Tokyo-University
• Topological-Sort

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).