東京大学 新領域創成科学研究科 メディカル情報生命専攻 2019年8月実施 問題9

标签：

• Tokyo-University
• Graph-Basics

Author

zephyr

Description

Answer the following problems about undirected graphs.

(1) Prove that the sum of degrees of all vertices of an undirected graph is even.

(2) Chemical formula $C_5H_{12}$ corresponds to several structural isomers. Show all isomers as graphs. The following graph represents $CH_4$.

	H
	|
H - C - H
    |
    H

(3) Three servers are connected as in the graph below. The network is functional when the graph is connected. Each edge disconnects independently with probability $p$. Find the probability of the network being functional as a function of $p$.

O
|\
| \
|  \
O---O

---

回答以下关于无向图的问题。

(1) 证明无向图中所有顶点度数之和是偶数。

(2) 化学式 $C_5H_{12}$ 对应于几种结构异构体。将所有异构体表示为图。以下图表示 $CH_4$。

	H
	|
H - C - H
    |
    H

(3) 三台服务器按下图连接。当图是连通时，网络是功能性的。每条边以概率 $p$ 独立断开。找到网络作为 $p$ 的函数是功能性的概率。

O
|\
| \
|  \
O---O

题目描述

回答下列无向图问题：

1. 证明无向图全部顶点的度数之和为偶数。
2. 化学式 $C_5H_{12}$ 有若干结构异构体；仿照上文以图表示 $CH_4$ 的方式，画出 $C_5H_{12}$ 的全部结构异构体。
3. 三台服务器按上图构成三角形网络；网络恰在对应图连通时正常工作。每条边相互独立地以概率 $p$ 断开，求网络正常工作的概率关于 $p$ 的表达式。

考点

• 无向图度数：利用每条边对两个端点的度数各贡献一次，证明度数和为边数的两倍。
• 分子结构的图表示：在满足碳四价、氢一价和总分子式 $C_5H_{12}$ 的条件下，按非同构碳骨架枚举全部结构。
• 图网络可靠性：对三角形的三条边独立失效，按保留至少两条边或其补事件计算连通概率。

Kai

(1)

Prove that the sum of degrees of all vertices of an undirected graph is even.

In an undirected graph, each edge contributes 2 to the sum of the degrees of the vertices because each edge is incident to two vertices. Let $G = (V, E)$ be an undirected graph where $V$ is the set of vertices and $E$ is the set of edges.

$$\text{Sum of degrees} = \sum_{v \in V} \deg(v)$$

Each edge $e \in E$ connects two vertices and contributes 1 to the degree of each vertex it connects. Therefore, each edge contributes exactly 2 to the sum of degrees. Let $\left| E \right|$ denote the number of edges.

$$\sum_{v \in V} \deg(v) = 2 \left| E \right|$$

Since $\left| E \right|$ is an integer, $2 \left| E \right|$ is even. Hence, the sum of the degrees of all vertices in an undirected graph is even.

(2)

Chemical formula $C_5H_{12}$ corresponds to several structural isomers. Show all isomers as graphs.

The structural isomers of pentane ($C_5H_{12}$) can be represented as graphs where each vertex represents a carbon atom, and each edge represents a bond between carbon atoms. The hydrogen atoms are implied but not shown in the graphs for simplicity.

1. n-Pentane:

   H   H   H   H   H
   |   |   |   |   |
   H - C - C - C - C - C - H
       |   |   |   |   |
       H   H   H   H   H

2. Isopentane (2-Methylbutane):

       H   H   H
       |   |   |
       C - C - C - C - H
       |   |   |
       H   H   C
           |   |
           H   H

3. Neopentane (2,2-Dimethylpropane):

           H   H
           |   |
       H - C - C - H
           |   |
       H - C - C - H
           |   |
           H   H

(3)

Three servers are connected as in the graph below. The network is functional when the graph is connected. Each edge disconnects independently with probability $p$. Find the probability of the network being functional as a function of $p$.

The graph of the network is a triangle:

O
|\
| \
|  \
O---O

To find the probability that the network is functional (connected), we need to consider the cases where the graph remains connected.

1. All edges are connected:

$$P(\text{All edges connected}) = (1 - p)^3$$

1. Exactly one edge fails:

The network remains connected if exactly one edge fails because the remaining two edges still connect all vertices.

$$P(\text{Exactly one edge fails}) = \binom{3}{1} p (1 - p)^2 = 3p(1 - p)^2$$

1. More than one edge fails:

If two or three edges fail, the network becomes disconnected. The probability of these events does not need to be computed explicitly since they are complementary to the first two cases.

The total probability of the network being functional is the sum of the probabilities of the above two cases:

$$P(\text{Network functional}) = (1 - p)^3 + 3p(1 - p)^2 = 4p^3 - 9 p^2 +6p +1 = 2p^3 - 3p^2 + 1$$

Knowledge

图论 化学异构体 概率论

重点词汇

• graph 图
• isomer 异构体
• probability 概率

参考资料

1. "Introduction to Graph Theory" by Douglas B. West
2. "Principles of Mathematical Chemistry" by Eugene S. Gladyshev