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

标签：

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

Author

itsuitsuki

Description (English)

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)\} ~\}$