跳到主要内容

東京大学 新領域創成科学研究科 メディカル情報生命専攻 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 corresponds to several structural isomers. Show all isomers as graphs. The following graph represents .

	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 . Find the probability of the network being functional as a function of .

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

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

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

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

	H
	|
H - C - H
    |
    H

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

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 be an undirected graph where is the set of vertices and is the set of edges.

Each edge 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 denote the number of edges.

Since is an integer, is even. Hence, the sum of the degrees of all vertices in an undirected graph is even.

(2)​

Chemical formula corresponds to several structural isomers. Show all isomers as graphs.

The structural isomers of pentane () 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 . Find the probability of the network being functional as a function of .

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:
  1. Exactly one edge fails:

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

  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:

Knowledge​

图论 化学异构体 概率论

重点词汇​

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

参考资料​

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