离散习题讲解（11）
离散习题讲解（11）
她来听我的演唱会......
Q1:
How many vertices and how many edges do these graphs have?
The graphs are:
- $ K_n $ (Complete graph on $ n $ vertices)
- $ C_n $ (Cycle graph on $ n $ vertices)
- $ W_n $ (Wheel graph on $ n $ vertices)
- $ Q_n $ (Hypercube graph on $ n $ vertices)
A1:
a) $ K_n $ (Complete graph on $ n $ vertices)
Vertices: $ n $ vertices.
Edges: The complete graph on $ n $ vertices has an edge between every pair of distinct vertices. The number of edges in a complete graph is given by: $ = $ This is because each vertex can be connected to $ n-1 $ other vertices, and since the edges are undirected, we divide by 2 to avoid double-counting.
Answer:
- Vertices: $ n $
- Edges: $ $
b) $ C_n $ (Cycle graph on $ n $ vertices)
Vertices: $ n $ vertices, arranged in a cycle.
Edges: In a cycle graph, each vertex is connected to exactly two other vertices (one to the left and one to the right), so there are $ n $ edges.
Answer:
- Vertices: $ n $
- Edges: $ n $
c) $ W_n $ (Wheel graph on $ n $ vertices)
Vertices: A wheel graph $ W_n $ has $ n+1 $ vertices, consisting of a cycle graph $ C_n $ with an additional central vertex.
- The cycle graph $ C_n $ has $ n $ vertices, and the central vertex adds 1 more, making it $ n+1 $ vertices.
Edges: In a wheel graph, the central vertex is connected to all $ n $ vertices in the cycle, and the cycle itself has $ n $ edges. So, the total number of edges is: $ = 2n $ because there are $ n $ edges in the cycle and $ n $ edges connecting the central vertex to each of the $ n $ cycle vertices.
Answer:
- Vertices: $ n+1 $
- Edges: $ 2n $
d) $ Q_n $ (Hypercube graph on $ n $ vertices)
Vertices: The number of vertices in a hypercube graph $ Q_n $ is $ 2^n $, as each vertex corresponds to a distinct binary string of length $ n $.
Edges: Each vertex in a hypercube is connected to $ n $ other vertices (because each vertex differs from another by exactly one bit). So, the total number of edges is: $ = $ The factor of $ 2^n $ accounts for the total number of vertices, and dividing by 2 avoids double-counting the edges.
Answer:
- Vertices: $ 2^n $
- Edges: $ n ^{n-1} $
Summary of Answers:
- a) $ K_n $:
- Vertices: $ n $
- Edges: $ $
- b) $ C_n $:
- Vertices: $ n $
- Edges: $ n $
- c) $ W_n $:
- Vertices: $ n+1 $
- Edges: $ 2n $
- d) $ Q_n $:
- Vertices: $ 2^n $
- Edges: $ n ^{n-1} $
Q2:
假设岛上有五位年轻女性和六位年轻男性。每位女性愿意嫁给岛上的一些男性，每位男性愿意娶任何愿意嫁给他的女性。
给定的信息如下：
- A 愿意嫁给 J、L 和 M。
- B 愿意嫁给 K 和 L。
- C 愿意嫁给 J、N 和 O。
- D 愿意嫁给 J、L、N 和 O。
- E 愿意嫁给 J 和 M。
a) 使用二分图表示岛上可能的婚姻。
在这个问题中，我们将使用 二分图 来建模，图中的：
- 一部分表示 女性：$ A, B, C, D, E $。
- 另一部分表示 男性：$ J, K, L, M, N, O $。
图中的边表示每个女性愿意嫁给某个男性。例如，如果 A 愿意嫁给 J，那么图中就会有一条从 A 到 J 的边。
二分图表示：
- 女性： $ A, B, C, D, E $
- 男性： $ J, K, L, M, N, O $
根据给定信息，二分图中的边如下：
- A 愿意嫁给 J、L、M：$ A J, A L, A M $
- B 愿意嫁给 K、L：$ B K, B L $
- C 愿意嫁给 J、N、O：$ C J, C N, C O $
- D 愿意嫁给 J、L、N、O：$ D J, D L, D N, D O $
- E 愿意嫁给 J、M：$ E J, E M $
所以，二分图的边集为：
$ { AJ, AL, AM, BK, BL, CJ, CN, CO, DJ, DL, DN, DO, EJ, EM } $
b) 找到岛上年轻女性和年轻男性的配对，使得每个年轻女性都与她愿意嫁给的男性配对。
在二分图中，一个 匹配 是一个边的集合，其中每条边连接一对女性和男性，并且没有任何两条边共享一个顶点。在这个问题中，我们需要找到一种匹配方式，使得每位女性都与她愿意嫁给的男性配对。
我们可以通过试探法找到一种匹配方式，或者使用 二分图匹配 或 最大匹配 等算法。这里，我们给出一种可能的匹配。
- A 可以与 L 配对（因为 A 愿意嫁给 L）。
- B 可以与 K 配对（因为 B 愿意嫁给 K）。
- C 可以与 J 配对（因为 C 愿意嫁给 J）。
- D 可以与 N 配对（因为 D 愿意嫁给 N）。
- E 可以与 M 配对（因为 E 愿意嫁给 M）。
所以，一种可能的配对是：
$ { AL, BK, CJ, DN, EM } $
这个配对是有效的，因为每条边都没有共享相同的顶点，并且每位女性都与她愿意嫁给的男性配对。
解释：
a) 我们将岛上的可能婚姻表示为一个二分图，图中一侧是女性，另一侧是男性，每条边代表一个女性愿意嫁给某个男性。
b) 我们通过试探法找到了一个匹配：$ { AL, BK, CJ, DN, EM } $，这个匹配是有效的，因为每位女性都与她愿意嫁给的男性配对，并且没有两条边共享同一个顶点。
答案总结：
a) 二分图的边集为： $ { AJ, AL, AM, BK, BL, CJ, CN, CO, DJ, DL, DN, DO, EJ, EM } $
b) 一种可能的配对是： $ { AL, BK, CJ, DN, EM } $
