京都大学 情報学研究科 知能情報学専攻 2024年8月実施 情報学基礎 F2-1

标签：

• Kyoto-University
• Maximum-Subarray-Sum
• Vertex-Degree
• Graph-Diameter
• Extremal-Graph-Construction

Author

itsuitsuki

Description

大学公表の原題

Q.1

Let $S = (3, -1, 2, -4, 5, -1, 3, -3, 4, -2, 1, -2)$ be a number sequence of length 12 and $s(i)$ is the value of the $i$-th element of $S$. For example, $s(1) = 3$ holds. Let us define $\text{maxSum}(i, j) = \max_{i \leq a \leq b \leq j} \sum_{k=a}^{b} s(k)$ and $M = \text{maxSum}(1, 12)$.

(1) Derive the value of $\text{maxSum}(1, 4)$.

(2) Derive $M$ and all the values of $(a, b)$ that satisfy $\sum_{k=a}^{b} s(k) = M$.

(3) Derive all the values of $(a, b)$ that satisfy $\sum_{k=a}^{b} s(k) = M - 1$.

Q.2

Consider an algorithm for generating an undirected graph using random numbers, whose pseudocode is given below.

let $G_1(V_1, E_1)$ be an undirected graph with $V_1 = \{v_0, v_1\}$ and $E_1 = \{\{v_0, v_1\}\}$;

for $i = 2$ to $n$ do

begin

    let $v_i$ be a new vertex;

    let $v_j$ and $v_k$ be distinct vertices randomly selected from $V_{i-1}$;

    let $G_i(V_i, E_i)$ be an undirected graph with $V_i = V_{i-1} \cup \{v_i\}$ and

        $E_i = E_{i-1} \cup \{\{v_i, v_j\}, \{v_i, v_k\}\}$;

end

Note that for any pair of distinct vertices $(v_j, v_k)$, the selection probability is positive. Obviously, any graph $G_n(V_n, E_n)$ constructed by this algorithm is connected, has $n+1$ vertices, and does not contain a self-loop or a multi-edge. In the following, we use $G_n$ to denote $G_n(V_n, E_n)$.

For a graph $G_n$, $\deg_{G_n}(v_p)$ denotes the degree of a vertex $v_p \in V_n$ (i.e., the number of edges connecting to $v_p$), and $\text{dist}_{G_n}(v_p, v_q)$ denotes the length (i.e., the number of edges) of the shortest path (i.e., the path consisting of the minimum number of edges) between two distinct vertices $v_p$ and $v_q$ in $V_n$. Note that $\deg_{G_n}(v_p)$ and $\text{dist}_{G_n}(v_p, v_q)$ are positive integers depending on randomly selected vertices in the algorithm.

In the following, $n$ is an even number greater than or equal to 4. Let $\mathcal{G}_n$ be the set of all possible undirected graphs $G_n$ generated by this algorithm. For example, for any $n$, $\min_{G_n \in \mathcal{G}_n} \{~ \min_{v_p \in V_n} \{\deg_{G_n}(v_p)\} ~\} = 2$ and $\max_{G_n \in \mathcal{G}_n} \{~ \min_{v_p \in V_n} \{\deg_{G_n}(v_p)\} ~\} = 2$ hold because $\deg_{G_n}(v_n) = 2$ always holds and $\deg_{G_n}(v_p) \geq 2$ always holds for any vertex $v_p \in V_n$.

Derive the following values. Note that the values may be given as mathematical expressions of $n$.

(1) $\max_{G_n \in \mathcal{G}_n} \{ ~\max_{v_p \in V_n} \{\deg_{G_n}(v_p)\}~ \}$

(2) $\min_{G_n \in \mathcal{G}_n} \{~ \max_{p < q, v_p \in V_n, v_q \in V_n} \{\text{dist}_{G_n}(v_p, v_q)\} ~\}$

(3) $\max_{G_n \in \mathcal{G}_n} \{~ \max_{p < q, v_p \in V_n, v_q \in V_n} \{\text{dist}_{G_n}(v_p, v_q)\} ~\}$

题目描述

1. 令 $S=(3,-1,2,-4,5,-1,3,-3,4,-2,1,-2)$，并定义
   $$\operatorname{maxSum}(i,j)= \max_{i\le a\le b\le j}\sum_{k=a}^b s(k),\qquad M=\operatorname{maxSum}(1,12).$$
   求 $\operatorname{maxSum}(1,4)$；求 $M$ 及全部使区间和为 $M$ 的 $(a,b)$；再求全部使区间和为 $M-1$ 的 $(a,b)$。
2. 随机图算法从边 $\{v_0,v_1\}$ 开始。对 $i=2,\ldots,n$，新建 $v_i$，从已有顶点中随机选不同的 $v_j,v_k$，加入边 $\{v_i,v_j\},\{v_i,v_k\}$。设 $n\ge4$ 为偶数，$\mathcal G_n$ 为所有可能输出。求：
   1. 所有图中最大可能顶点度；
   2. 所有图中最小可能直径；
   3. 所有图中最大可能直径。 答案可写成 $n$ 的表达式。

Kai

Q.1

Let $p_0=0$ and $p_j=\sum_{k=1}^j s(k)$. The complete prefix-sum list is

$$(p_0,p_1,\ldots,p_{12})=(0,3,2,4,0,5,4,7,4,8,6,7,5).$$

Every interval sum is $p_b-p_{a-1}$, with $a-1<b$.

(1) Among the first four elements, the maximum is $4$, attained by $(a,b)=(1,3)$.

(2) The largest difference of a prefix sum and an earlier prefix sum is $M=8$. The complete set of maximizing intervals is

$$(a,b)=(1,9),\ (5,9).$$

(3) Reading all ordered pairs of prefix sums whose difference is $7$ gives exactly

$$(a,b)=(1,7),\ (1,11),\ (5,7),\ (5,11).$$

Q.2

(1)

There are $n+1$ vertices, so every degree is at most $n$. Choose $v_0,v_1$ as the two neighbors of every new vertex. Then $v_0$ has degree $n$, proving that the answer is $n$.

(2)

The same construction has diameter $2$: any two new vertices share $v_0$ as a neighbor. A diameter of $1$ would require a complete graph, but every generated graph has

$$|E_n|=1+2(n-1)=2n-1<\frac{n(n+1)}2\qquad(n\ge4).$$

Thus the minimum diameter is $2$.

(3)

Every generated graph with at least three vertices remains connected after deleting any one vertex. This holds for the initial triangle. Inductively, a new vertex has two distinct neighbors, so deleting one old vertex leaves it joined to the remaining connected old graph; deleting the new vertex simply restores the old graph.

Let $u,v$ have distance $d$, and group vertices by their distance from $u$. Each layer $1,\ldots,d-1$ contains at least two vertices: a singleton layer would disconnect $u$ from $v$ when its sole vertex was deleted, since an edge changes distance from $u$ by at most one. Counting the endpoints and intermediate layers gives

$$n+1\ge1+2(d-1)+1=2d.$$

Because $n$ is even, $d\le n/2$.

To attain this bound, connect each $v_i$ to $v_{i-1}$ and $v_{i-2}$. Every edge changes the index by at most two, and the path $v_0,v_2,\ldots,v_n$ has length $n/2$. Hence the maximum diameter is $n/2$.