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

Author

zephyr

Description

Let be a simple undirected graph with the vertex set and edge set . For an -dimensional vector , define by

Answer the following questions.

(1) For the case where is a complete graph of vertices, compute .

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

(3) Let be an arbitrary simple undirected graph. When each takes a value of either or with probability independently, compute the expected value of . You may use the linearity of expectation.

(4) Show that, for any simple undirected graph , there exists some such that

Here, denotes the number of edges of .

---

令 为一个简单无向图，其顶点集为 ，边集为 。对于一个 维向量 ，定义 为

回答以下问题。

(1) 当 是一个 个顶点的完全图 时，计算 。

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

(3) 令 为任意一个简单无向图。当每个 独立地以 的概率取 或 时，计算 的期望值。你可以使用期望值的线性性。

(4) 证明对于任意简单无向图 ，存在某个 使得

这里， 表示 的边数。

Kai

(1)

For , a complete graph with vertices, every pair of distinct vertices is connected by an edge. Thus, the edge set has edges.

To compute , consider the definition of :

For each edge , the term is either or :

To maximize , we need to maximize the number of edges where . Let be the number of vertices where , and be the number of vertices where .

The number of edges between vertices with and is . Therefore:

We need to maximize . The function is a quadratic function in with its maximum value when .

Case 1: is even

When is even, let . Then:

Case 2: is odd

When is odd, let or . Either way, is maximized when the sizes of the two groups differ by at most one. Therefore:

or

Since and , we have:

Thus:

In conclusion:

(2)

The number of edges in a complete graph is .

Using the result from Question 1:

We have:

Thus,

(3)

Let be an arbitrary simple undirected graph, and with each taking values or independently with probability .

To find the expected value of , use the linearity of expectation:

Now, consider :

since and are independent and each has expectation (values are or with equal probability).

Thus,

Therefore,

(4)

To show that there exists some such that , consider the expected value derived in Question 3.

We have:

Since is the average value of over all possible , there must be at least one particular for which . Otherwise, the average value could not be .

Therefore, there exists some such that:

Knowledge

图论 期望值 极大值

难点解题思路

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

解题技巧和信息

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

重点词汇

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

参考资料

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