CBMS-2020-09

题目来源：[[做题/文字版题库/CBMS/2020#Question 9|2020#Question 9]] 日期：2024-07-23 题目主题：CS-离散数学-无向图

解题思路

这三个问题涉及无向图的性质、化学结构异构体的图表示、以及概率计算。

1. 第一个问题考察无向图顶点度数之和的性质。
2. 第二个问题涉及化学分子异构体的图表示。
3. 第三个问题涉及图的连通性和概率计算。

Solution

Problem 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}\mathrm{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}\mathrm{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.

Problem 2

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

The structural isomers of pentane ($C_5{H}_{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

Problem 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})=\left(\genfrac{}{}{0ex}{}{3}{1}\right)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-9p^2+6p+1=2p^3-3p^2+1$$

知识点

图论化学异构体概率论

重点词汇

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

参考资料

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