Skip to content

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

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\).

1
2
3
4
5
    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\).

1
2
3
4
5
O
|\
| \
|  \
O---O

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

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

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

1
2
3
4
5
    H
    |
H - C - H
    |
    H

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

1
2
3
4
5
O
|\
| \
|  \
O---O

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:

    1
2
3
4
5
    H   H   H   H   H
|   |   |   |   |
H - C - C - C - C - C - H
    |   |   |   |   |
    H   H   H   H   H

  2. Isopentane (2-Methylbutane):

    1
2
3
4
5
6
7
        H   H   H
    |   |   |
    C - C - C - C - H
    |   |   |
    H   H   C
        |   |
        H   H

  3. Neopentane (2,2-Dimethylpropane):

    1
2
3
4
5
6
7
            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:

1
2
3
4
5
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