東京大学 情報理工学系研究科 コンピュータ科学専攻 2022年2月実施 問題2

标签：

• Tokyo-University
• Graph-Basics

Author

zephyr

Description

Let $G = (V, E)$ be a simple undirected graph with the vertex set $V = \{v_i \mid i = 1, \ldots, n\}$ and edge set $E$. For an $n$-dimensional vector $\mathbf{x} = (x_1, \ldots, x_n) \in \{-1, +1\}^n$, define $f_G(\mathbf{x})$ by

$$f_G(\mathbf{x}) = \sum_{(v_i, v_j) \in E} \frac{1 - x_i x_j}{2}.$$

Answer the following questions.

(1) For the case where $G$ is a complete graph $K_n$ of $n$ vertices, compute $a_n = \max_{\mathbf{x} \in \{-1, +1\}^n} f_G(\mathbf{x})$.

(2) Let $K_n$ and $a_n$ be those given in question (1). Let $b_n$ be the number of edges of $K_n$. Compute

$$\lim_{n \to \infty} \frac{a_n}{b_n}.$$

(3) Let $G$ be an arbitrary simple undirected graph. When each $x_i$ takes a value of either $-1$ or $+1$ with probability $\frac{1}{2}$ independently, compute the expected value of $f_G(\mathbf{x})$. You may use the linearity of expectation.

(4) Show that, for any simple undirected graph $G$, there exists some $\mathbf{x} \in \{-1, +1\}^n$ such that

$$f_G(\mathbf{x}) \geq \frac{|E|}{2}.$$

Here, $|E|$ denotes the number of edges of $G$.

---

令 $G = (V, E)$ 为一个简单无向图，其顶点集为 $V = \{v_i \mid i = 1, \ldots, n\}$，边集为 $E$。对于一个 $n$ 维向量 $\mathbf{x} = (x_1, \ldots, x_n) \in \{-1, +1\}^n$，定义 $f_G(\mathbf{x})$ 为

$$f_G(\mathbf{x}) = \sum_{(v_i, v_j) \in E} \frac{1 - x_i x_j}{2}.$$

回答以下问题。

(1) 当 $G$ 是一个 $n$ 个顶点的完全图 $K_n$ 时，计算 $a_n = \max_{\mathbf{x} \in \{-1, +1\}^n} f_G(\mathbf{x})$。

(2) 令 $K_n$ 和 $a_n$ 为问题（1）中给出的。令 $b_n$ 为 $K_n$ 的边数。计算

$$\lim_{n \to \infty} \frac{a_n}{b_n}.$$

(3) 令 $G$ 为任意一个简单无向图。当每个 $x_i$ 独立地以 $\frac{1}{2}$ 的概率取 $-1$ 或 $+1$ 时，计算 $f_G(\mathbf{x})$ 的期望值。你可以使用期望值的线性性。

(4) 证明对于任意简单无向图 $G$，存在某个 $\mathbf{x} \in \{-1, +1\}^n$ 使得

$$f_G(\mathbf{x}) \geq \frac{|E|}{2}.$$

这里，$|E|$ 表示 $G$ 的边数。

Kai

(1)

For $G = K_n$, a complete graph with $n$ vertices, every pair of distinct vertices is connected by an edge. Thus, the edge set $E$ has $\binom{n}{2} = \frac{n(n-1)}{2}$ edges.

To compute $a_n = \max_{\mathbf{x} \in \{-1, +1\}^n} f_G(\mathbf{x})$, consider the definition of $f_G(\mathbf{x})$:

$$f_G(\mathbf{x}) = \sum_{(v_i, v_j) \in E} \frac{1 - x_i x_j}{2}.$$

For each edge $(v_i, v_j)$, the term $\frac{1 - x_i x_j}{2}$ is either $0$ or $1$:

$$\frac{1 - x_i x_j}{2} = \begin{cases} 0 & \text{if } x_i = x_j \\ 1 & \text{if } x_i \neq x_j \end{cases}$$

To maximize $f_G(\mathbf{x})$, we need to maximize the number of edges where $x_i \neq x_j$. Let $k$ be the number of vertices where $x_i = 1$, and $n-k$ be the number of vertices where $x_i = -1$.

The number of edges between vertices with $x_i = 1$ and $x_j = -1$ is $k(n-k)$. Therefore:

$$f_G(\mathbf{x}) = k(n-k).$$

We need to maximize $k(n-k)$. The function $k(n-k)$ is a quadratic function in $k$ with its maximum value when $k = \frac{n}{2}$.

Case 1: $n$ is even

When $n$ is even, let $k = \frac{n}{2}$. Then:

$$a_n = \left(\frac{n}{2}\right)\left(n - \frac{n}{2}\right) = \left(\frac{n}{2}\right)\left(\frac{n}{2}\right) = \frac{n^2}{4}.$$

Case 2: $n$ is odd

When $n$ is odd, let $k = \left\lfloor \frac{n}{2} \right\rfloor$ or $k = \left\lceil \frac{n}{2} \right\rceil$. Either way, $k(n-k)$ is maximized when the sizes of the two groups differ by at most one. Therefore:

$$a_n = \left\lfloor \frac{n}{2} \right\rfloor \left(n - \left\lfloor \frac{n}{2} \right\rfloor \right).$$

or

$$a_n = \left\lceil \frac{n}{2} \right\rceil \left(n - \left\lceil \frac{n}{2} \right\rceil \right).$$

Since $\left\lfloor \frac{n}{2} \right\rfloor = \left(\frac{n-1}{2}\right)$ and $\left\lceil \frac{n}{2} \right\rceil = \left(\frac{n+1}{2}\right)$, we have:

$$a_n = \left(\frac{n-1}{2}\right)\left(\frac{n+1}{2}\right).$$

Thus:

$$a_n = \frac{(n-1)(n+1)}{4} = \frac{n^2 - 1}{4}.$$

In conclusion:

$$a_n = \begin{cases} \frac{n^2}{4} & \text{if } n \text{ is even} \\ \frac{n^2 - 1}{4} & \text{if } n \text{ is odd} \end{cases}$$

(2)

The number of edges in a complete graph $K_n$ is $b_n = \binom{n}{2} = \frac{n(n-1)}{2}$.

Using the result from Question 1:

$$a_n = \begin{cases} \frac{n^2}{4} & \text{if } n \text{ is even} \\ \frac{n^2 - 1}{4} & \text{if } n \text{ is odd} \end{cases}$$

We have:

$$\lim_{n \to \infty} \frac{a_n}{b_n} = \lim_{n \to \infty} \frac{\frac{n^2}{4}}{\frac{n(n-1)}{2}} = \lim_{n \to \infty} \frac{n^2}{4} \cdot \frac{2}{n(n-1)} = \lim_{n \to \infty} \frac{n}{2(n-1)} = \lim_{n \to \infty} \frac{1}{2} \cdot \frac{n}{n-1} = \frac{1}{2}$$

Thus,

$$\lim_{n \to \infty} \frac{a_n}{b_n} = \frac{1}{2}$$

(3)

Let $G = (V, E)$ be an arbitrary simple undirected graph, and $\mathbf{x} = (x_1, \ldots, x_n) \in \{-1, +1\}^n$ with each $x_i$ taking values $-1$ or $1$ independently with probability $\frac{1}{2}$.

To find the expected value of $f_G(\mathbf{x})$, use the linearity of expectation:

$$\mathbb{E}[f_G(\mathbf{x})] = \mathbb{E}\left[\sum_{(v_i, v_j) \in E} \frac{1 - x_i x_j}{2}\right] = \sum_{(v_i, v_j) \in E} \mathbb{E}\left[\frac{1 - x_i x_j}{2}\right]$$

Now, consider $\mathbb{E}\left[\frac{1 - x_i x_j}{2}\right]$:

$$\mathbb{E}[x_i x_j] = \mathbb{E}[x_i] \mathbb{E}[x_j] = 0 \cdot 0 = 0$$

since $x_i$ and $x_j$ are independent and each has expectation $0$ (values are $-1$ or $1$ with equal probability).

Thus,

$$\mathbb{E}\left[\frac{1 - x_i x_j}{2}\right] = \frac{1 - \mathbb{E}[x_i x_j]}{2} = \frac{1 - 0}{2} = \frac{1}{2}$$

Therefore,

$$\mathbb{E}[f_G(\mathbf{x})] = \sum_{(v_i, v_j) \in E} \frac{1}{2} = \frac{|E|}{2}$$

(4)

To show that there exists some $\mathbf{x} \in \{-1, +1\}^n$ such that $f_G(\mathbf{x}) \geq \frac{|E|}{2}$, consider the expected value derived in Question 3.

We have:

$$\mathbb{E}[f_G(\mathbf{x})] = \frac{|E|}{2}$$

Since $\mathbb{E}[f_G(\mathbf{x})]$ is the average value of $f_G(\mathbf{x})$ over all possible $\mathbf{x} \in \{-1, +1\}^n$, there must be at least one particular $\mathbf{x} \in \{-1, +1\}^n$ for which $f_G(\mathbf{x}) \geq \frac{|E|}{2}$. Otherwise, the average value could not be $\frac{|E|}{2}$.

Therefore, there exists some $\mathbf{x} \in \{-1, +1\}^n$ such that:

$$f_G(\mathbf{x}) \geq \frac{|E|}{2}$$

Knowledge

图论 期望值 极大值

难点解题思路

在第 1 题中，找到使得 $f_G(\mathbf{x})$ 最大的 $\mathbf{x}$ 是关键。在处理完全图时，可以通过对称性和顶点划分来简化问题。对于一般图，期望值和线性期望的使用使得问题更易处理。

解题技巧和信息

对于复杂的图论问题，可以通过图的对称性来简化问题。期望值的计算可以利用线性期望的性质，使得问题转化为求和问题。求极大值时，可以考虑图的特殊结构，例如完全图的顶点划分。

重点词汇

• graph 图
• complete graph 完全图
• edge 边
• vertex 顶点
• expected value 期望值

参考资料

1. Bollobás, B. (1998). Modern Graph Theory. Springer. Chap. 1-3.