京都大学 情報学研究科 知能情報学専攻 2021年2月実施 基礎科目 F2-2

标签：

• Kyoto-University
• Graph-Theory
• Dynamic-Programming
• Postorder-Tree-Traversal
• Algorithm-Complexity

Author

祭音Myyura (co-authored with GPT 5.6 SOL)

Description

Let $G=(V,E)$ be a simple undirected graph. Each vertex $v\in V$ has a positive integer weight $w(v)$. A set $S\subseteq V$ is independent if $(u,v)\notin E$ for every pair $u,v\in S$. Its weight is

$$w(S)=\sum_{v\in S}w(v).$$

An independent set of maximum weight is called a maximum independent set, and its weight is denoted by $\operatorname{IN}(G)$.

(1)

Give a maximum independent set and $\operatorname{IN}(G_1)$ for the following graph. The integer beside each vertex name is its weight.

a(2) ----- c(1) ----- e(1)       g(2)
 | \         |           | \       |
 |   \       |           |   \     |
b(2) ----- d(3) ----- f(2) ----- h(3)

Thus

$$\begin{aligned} E(G_1)=\{& (a,b),(a,c),(a,d),(b,d),(c,d),(c,e),\\ &(d,f),(e,f),(e,h),(f,h),(g,h)\}. \end{aligned}$$

(2)

From this point on, consider rooted trees only. For a vertex $v$, let $T(v)$ be the subtree rooted at $v$, and define

$$\begin{aligned} X(v)&=\max\{w(S)\mid S\text{ is independent in }T(v),\ v\in S\},\\ Y(v)&=\max\{w(S)\mid S\text{ is independent in }T(v),\ v\notin S\},\\ Z(v)&=\operatorname{IN}(T(v)). \end{aligned}$$

For the following tree $T_1$, give $X(v_1),Y(v_1),Z(v_1),X(v_2),Y(v_2),Z(v_2)$. The root is $r_1$, and the numbers in brackets are vertex weights.

                 r1[2]
              /    |    \
          v1[2]  v2[3]   [1]
                  / \
                [3] [2]
                 |
                [1]

(3)

Algorithm 1 computes $\operatorname{IN}(T)$ for a tree rooted at $r$. Fill the blanks (a)--(f). If necessary, use $C(v)$ for the set of children of $v$.

Algorithm 1
Input:  A tree T rooted at r.
Output: IN(T).

1:  Let all vertices be unmarked.
2:  while there is an unmarked vertex do
3:      Let v be an unmarked vertex having no unmarked child.
4:      Mark v.
5:      if v is a leaf then
6:          X(v) := (a); Y(v) := (b); Z(v) := (c).
7:      else
8:          X(v) := (d); Y(v) := (e); Z(v) := (c).
9:      end if
10: end while
11: Output (f).

(4)

Suppose depth-first search from $r$ is used to determine the order of vertices processed at line 3. Which ordering is appropriate: preorder, inorder, or postorder? Give reasons.

(5)

Let $n$ be the number of vertices in $T$. Give the time complexity of Algorithm 1 with reasons.

题目描述

设简单无向图 $G=(V,E)$ 的每个顶点 $v$ 有正整数权重 $w(v)$。 独立集 $S$ 的权重为 $w(S)=\sum_{v\in S}w(v)$，最大权独立集的权重记作 $\operatorname{IN}(G)$。

1. 对题图 $G_1$，给出一个最大权独立集及 $\operatorname{IN}(G_1)$。
2. 对根树定义：$X(v)$ 为必须选 $v$ 时子树 $T(v)$ 的最大独立集权重， $Y(v)$ 为不选 $v$ 时的最大权重，$Z(v)=\operatorname{IN}(T(v))$。 求题图 $T_1$ 中 $v_1,v_2$ 各自的 $X,Y,Z$。
3. 补全自底向上计算 $\operatorname{IN}(T)$ 的算法空栏 (a)--(f)。
4. 为保证处理顶点时其子结点均已处理，应采用前序、中序还是后序遍历？说明理由。
5. 设输入树有 $n$ 个顶点，求算法的时间复杂度并说明理由。

Kai

(1)

The set

$$\boxed{S=\{b,c,f,g\}}$$

is independent, and its weight is

$$w(S)=2+1+2+2=7.$$

For completeness, conditioning on whether vertices $d$ and $h$ are selected gives the following best possible weights:

$d\in S$	$h\in S$	best weight
no	no	$7$
no	yes	$6$
yes	no	$6$
yes	yes	$6$

Therefore,

$$\boxed{\operatorname{IN}(G_1)=7}.$$

(2)

The vertex $v_1$ is a leaf of weight $2$, so

$$\boxed{X(v_1)=2,\qquad Y(v_1)=0,\qquad Z(v_1)=2}.$$

For the weight-$3$ child of $v_2$, whose only child has weight $1$, the three values are $(3,1,3)$. For the weight-$2$ leaf child, they are $(2,0,2)$. Consequently,

$$\begin{aligned} X(v_2)&=3+1+0=4,\\ Y(v_2)&=3+2=5,\\ Z(v_2)&=\max\{4,5\}=5. \end{aligned}$$

Thus

$$\boxed{X(v_2)=4,\qquad Y(v_2)=5,\qquad Z(v_2)=5}.$$

(3)

For a leaf, selecting it gives its weight and excluding it gives zero. For a non-leaf, selecting $v$ forces every child to be excluded, while excluding $v$ allows the optimal choice in every child subtree. Hence the blanks are

$$\begin{array}{c|l} \text{blank}&\text{expression}\\ \hline (a)&w(v)\\ (b)&0\\ (c)&\max\{X(v),Y(v)\}\\ (d)&w(v)+\displaystyle\sum_{u\in C(v)}Y(u)\\ (e)&\displaystyle\sum_{u\in C(v)}Z(u)\\ (f)&Z(r) \end{array}$$

(4)

The appropriate ordering is

$$\boxed{\text{postorder}}.$$

Postorder visits every child before its parent, so all values needed to compute $X(v),Y(v),Z(v)$ are already available when $v$ is processed. Preorder does the opposite, and inorder does not guarantee this property.

(5)

Using the postorder schedule, every vertex is processed once. Computing the values at $v$ takes $O(|C(v)|)$ time, and

$$\sum_{v\in V}|C(v)|=n-1.$$

Therefore the total running time is

$$\boxed{\Theta(n)}.$$