Special Types of Graph | 特殊类型的图

📚 Special Types of Graph | 特殊类型的图

In Edexcel Decision Mathematics, graphs are used to model networks, routes, and relationships. A graph consists of vertices, also called nodes, connected by edges, also called arcs. To solve problems such as route inspection, matching, and the travelling salesman problem, you need to identify and classify special types of graph. These include connected graphs, complete graphs, bipartite graphs, trees, Eulerian graphs, semi-Eulerian graphs, Hamiltonian graphs, planar graphs, and isomorphic graphs. This article explains the key properties, conditions, and common exam applications of each type.

在Edexcel决策数学中，图用于建立网络、路线和关系模型。图由顶点（也称节点）和边（也称弧）组成。要解决路径检查、匹配和旅行商等问题，你需要识别和分类特殊类型的图。这些图包括连通图、完全图、二分图、树、欧拉图、半欧拉图、哈密顿图、平面图和同构图。本文逐一说明每种图的关键性质、判定条件和常见考试应用。

1. Connected Graphs | 连通图

A graph is connected if there is a path between every pair of vertices. In other words, you can travel from any vertex to any other vertex by following a sequence of edges. If a graph is not connected, it is split into two or more separate components. A connected graph has exactly one component, while a disconnected graph has at least two components. Isolated vertices with degree zero also make a graph disconnected unless the graph has only one vertex.

如果一个图中任意两个顶点之间都存在一条路径，则该图是连通的。换句话说，你可以沿着边从任意一个顶点到达任意另一个顶点。如果图不连通，它会被分成两个或更多独立的连通分量。连通图只有一个分量，而不连通图至少有两个分量。度为零的孤立顶点也会使图不连通，除非该图只有一个顶点。

In exam questions, you may be asked to state whether a graph is connected, to find the number of components, or to add the minimum number of edges to make a graph connected. Always check for separate clusters and isolated vertices before applying algorithms such as Prim’s or Kruskal’s, because those algorithms require a connected network. A quick visual check is often enough, but for a formal answer you should reference the existence of a path between every pair of vertices.

在考试题中，你可能需要判断一个图是否连通、求连通分量的数量，或者添加最少边使图连通。在应用Prim算法或Kruskal算法之前，一定要检查是否存在分离的簇和孤立顶点，因为这些算法要求网络连通。快速画图观察通常就足够了，但正式作答时应提及每一对顶点之间都存在路径。

2. Complete Graphs | 完全图

A complete graph with n vertices is written Kₙ. It is a simple graph in which every pair of distinct vertices is joined by exactly one edge. There are no loops and no multiple edges. In Kₙ, every vertex has degree n − 1, because each vertex is connected to all other vertices. The total number of edges in Kₙ is given by the formula n(n − 1) ÷ 2.

具有n个顶点的完全图记作Kₙ。它是一种简单图，其中每一对不同的顶点之间恰好由一条边相连。完全图中没有环和重边。在Kₙ中，每个顶点的度都是n − 1，因为每个顶点都与所有其他顶点相连。Kₙ的边总数由公式n(n − 1) ÷ 2给出。

Complete graphs are useful when modelling networks where every node must be directly linked to every other node. The table below shows the number of edges for small complete graphs.

完全图在为每个节点都必须直接与其他所有节点相连的网络建模时非常有用。下表列出了小规模完全图的边数。

n	Vertices	Edges n(n − 1) ÷ 2
1	K₁	0
2	K₂	1
3	K₃	3
4	K₄	6
5	K₅	10
6	K₆	15

You should also know that K₅ is non-planar, meaning it cannot be drawn in a plane without edges crossing. This fact is used in planarity arguments. Complete graphs often appear in route inspection and travelling salesman contexts because they represent the densest possible simple network.

你还应知道K₅是非平面图，也就是说它无法在平面内画出而不出现边交叉。这个事实常用于平面性论证。完全图经常出现在路径检查和旅行商问题中，因为它们代表了最稠密的简单网络。

3. Bipartite Graphs | 二分图

A bipartite graph is a graph whose vertices can be divided into two disjoint sets, usually called X and Y, such that every edge connects a vertex in X to a vertex in Y. There are no edges joining two vertices within the same set. If every vertex in X is connected to every vertex in Y, the graph is called a complete bipartite graph and is written Kₘ,ₙ, where m and n are the sizes of the two sets.

二分图是这样的图：其顶点可以分成两个不相交的集合，通常记为X和Y，并且每条边都连接X中的一个顶点和Y中的一个顶点。同一个集合内的两个顶点之间没有边。如果X中的每个顶点都与Y中的每个顶点相连，则该图称为完全二分图，记作Kₘ,ₙ，其中m和n分别是两个集合的大小。

The number of edges in Kₘ,ₙ is m × n. For example, K₂,₃ has 2 vertices in one set, 3 vertices in the other set, and therefore 2 × 3 = 6 edges. Bipartite graphs are used in matching problems: one set might represent workers and the other set tasks, with an edge showing that a worker can perform a task. A useful theorem is that a graph is bipartite if and only if it contains no odd cycle, meaning no cycle with an odd number of edges.

Kₘ,ₙ的边数是m × n。例如，K₂,₃在一个集合中有2个顶点，在另一个集合中有3个顶点，因此有2 × 3 = 6条边。二分图用于匹配问题：一个集合可以表示工人，另一个集合表示任务，边表示工人能够完成某项任务。一个有用的定理是：一个图是二分图当且仅当它不含奇圈，即不含边数为奇数的圈。

In an exam, you may be asked to decide whether a given graph is bipartite by attempting to split its vertices into two sets. If you find an odd cycle, the graph cannot be bipartite. Alternatively, you may need to draw Kₘ,ₙ or calculate its edge count using m × n.

在考试中，你可能需要通过尝试将顶点分成两个集合来判断给定图是否为二分图。如果找到一个奇圈，则该图不可能是二分图。另外，你可能需要画出Kₘ,ₙ，或者用m × n计算其边数。

4. Trees and Spanning Trees | 树与生成树

A tree is a connected graph with no cycles. Because it is connected and acyclic, a tree with n vertices has exactly n − 1 edges. This is a key property: if a connected graph has n vertices and n − 1 edges, it must be a tree. Conversely, any connected graph with n vertices and at least n edges must contain a cycle.

树是一种没有圈的连通图。由于树既连通又无圈，因此具有n个顶点的树恰好有n − 1条边。这是一个关键性质：如果一个连通图有n个顶点和n − 1条边，那么它一定是树。反过来，任何具有n个顶点且边数不少于n的连通图一定含有圈。

In a tree, there is exactly one path between any two vertices. Removing any edge disconnects the tree, and adding any edge between two existing vertices creates exactly one cycle. Trees are used to model hierarchical structures and minimal connection networks without redundancy.

在树中，任意两个顶点之间恰好有一条路径。删除任意一条边都会使树不连通，而在任意两个已有顶点之间添加一条边都会恰好产生一个圈。树用于模拟层次结构和没有冗余的最小连接网络。

A spanning tree of a connected graph is a subgraph that includes all the vertices of the original graph and is itself a tree. Every connected graph has at least one spanning tree. In a weighted network, a minimum spanning tree is the spanning tree with the smallest total weight. Kruskal’s algorithm and Prim’s algorithm are used to find a minimum spanning tree. In decision mathematics, you may be asked to find a spanning tree by deleting edges from cycles until no cycles remain.

连通图的生成树是原图的一个子图，它包含原图的所有顶点，并且本身是一棵树。每个连通图都至少有一棵生成树。在加权网络中，最小生成树是总权重最小的生成树。Kruskal算法和Prim算法用于求最小生成树。在决策数学中，你可能需要通过删除圈上的边来构造一棵生成树，直到图中不再有圈。

5. Eulerian Graphs | 欧拉图

A connected graph is Eulerian if every vertex has an even degree. If a graph is Eulerian, it is possible to start at a vertex, travel along every edge exactly once, and return to the starting vertex. Such a route is called an Eulerian circuit or Eulerian cycle. The key point is that an Eulerian circuit covers every edge exactly once, not every vertex.

如果一个连通图的每个顶点都具有偶数度，则该图是欧拉图。如果图是欧拉图，就可以从某个顶点出发，每条边恰好经过一次，最后回到起点。这样的路线称为欧拉回路或欧拉环游。关键点是欧拉回路恰好经过每条边一次，而不是每个顶点一次。

You must always check that the graph is connected before declaring it Eulerian. A disconnected graph in which every vertex has even degree is not Eulerian because you cannot travel between separate components without repeating edges. The condition is therefore: connected and all degrees even.

在判断一个图是否为欧拉图之前，必须始终检查它是否连通。一个每个顶点度数都为偶数的非连通图不是欧拉图，因为在不重复边的情况下你无法在不同分量之间移动。因此判定条件为：连通且所有顶点度数为偶数。

Eulerian graphs are central to the route inspection problem. If a network is Eulerian, every edge can be traversed exactly once without repeating any edge, so the optimal route length is simply the total weight of all edges. If the graph is not Eulerian, you need to repeat some edges to make all degrees even.

欧拉图是路径检查问题的核心。如果一个网络是欧拉图，每条边都可以恰好被遍历一次而不重复任何边，因此最优路线长度就是所有边的总权重。如果图不是欧拉图，则需要重复一些边，使所有顶点度数变为偶数。

6. Semi-Eulerian Graphs | 半欧拉图

A connected graph is semi-Eulerian if it has exactly two vertices with odd degree. In such a graph, there exists an Eulerian trail that starts at one of the odd-degree vertices, uses every edge exactly once, and ends at the other odd-degree vertex. A trail is like a path, but edges are not repeated; vertices may be repeated.

如果一个连通图恰好有两个奇度顶点，则该图是半欧拉图。在这样的图中，存在一条欧拉迹，它从一个奇度顶点出发，每条边恰好经过一次，最后到达另一个奇度顶点。迹类似于路径，但边不重复，顶点可以重复。

If a connected graph has more than two odd-degree vertices, it is neither Eulerian nor semi-Eulerian. In that case, an Eulerian trail is impossible without repeating some edges. The number of odd-degree vertices in any graph is always even, so you will never encounter a graph with exactly one odd vertex.

如果一个连通图有超过两个奇度顶点，那么它既不是欧拉图也不是半欧拉图。在这种情况下，如果不重复某些边，就不可能形成欧拉迹。任何图中奇度顶点的数量总是偶数，所以你不会遇到恰好有一个奇度顶点的图。

Semi-Eulerian graphs appear in route inspection when the optimal route can start and end at two different vertices. If a graph has exactly two odd vertices, the shortest route that covers every edge exactly once will begin at one odd vertex and end at the other, with no repeated edges.

半欧拉图出现在路径检查中，此时最优路线可以在两个不同的顶点开始和结束。如果一个图恰好有两个奇度顶点，那么覆盖每条边恰好一次的最短路线将从一个奇度顶点开始，在另一个奇度顶点结束，并且不重复任何边。

7. Hamiltonian Graphs | 哈密顿图

A Hamiltonian graph is a graph that contains a Hamiltonian cycle. A Hamiltonian cycle is a cycle that visits every vertex exactly once and returns to the starting vertex. A Hamiltonian path visits every vertex exactly once but does not return to the start. Unlike Eulerian graphs, which focus on edges, Hamiltonian graphs focus on vertices.

哈密顿图是包含哈密顿圈的图。哈密顿圈是一个圈，它恰好访问每个顶点一次并回到起点。哈密顿路径恰好访问每个顶点一次但不回到起点。与关注边的欧拉图不同，哈密顿图关注的是顶点。

There is no simple necessary and sufficient condition for a graph to be Hamiltonian at A-Level. You may need to find a Hamiltonian cycle by trial and improvement, or show that no Hamiltonian cycle exists by logical reasoning. Common reasons a graph cannot be Hamiltonian include having a vertex of degree less than 2, or having a cut vertex whose removal splits the graph into too many components.

在A-Level阶段，判断一个图是否为哈密顿图没有简单而充分的必要条件。你可能需要通过尝试和逐步改进来寻找哈密顿圈，或者通过逻辑推理证明不存在哈密顿圈。图不可能是哈密顿图的常见原因包括：存在度小于2的顶点，或者存在割点，删除该顶点后图分成过多分量。

The travelling salesman problem requires finding a Hamiltonian cycle of minimum total weight in a complete weighted graph. The classical problem is computationally hard, but for small graphs you can list all possible Hamiltonian cycles and compare their weights. In exam questions, you are often asked to find an upper bound or lower bound rather than a full solution.

旅行商问题要求在完全加权图中寻找总权重最小的哈密顿圈。经典问题在计算上很困难，但对于小图，你可以列出所有可能的哈密顿圈并比较它们的权重。在考试题中，通常要求你求上界或下界，而不是完整的解。

8. Planar Graphs | 平面图

A planar graph is a graph that can be drawn in a plane so that no edges cross, except at their shared vertices. If a graph can be redrawn without edge crossings, it is planar. The drawing with no crossings is called a plane graph. K₄ is planar because it can be drawn as a triangle with a vertex inside connected to all three corners without crossings.

平面图是可以在平面内画出且除公共顶点外没有边交叉的图。如果一个图可以重新画出而不出现边交叉，那么它就是平面图。没有交叉的画法称为平面嵌入。K₄是平面图，因为它可以画成一个三角形，内部放一个顶点并与三个角相连而不产生交叉。

For any connected planar graph, Euler’s formula holds: V − E + F = 2. Here V is the number of vertices, E is the number of edges, and F is the number of faces. The faces are the regions bounded by edges, including the outer infinite face. This formula is extremely useful for finding the number of faces when V and E are known.

对于任意连通平面图，欧拉公式成立：V − E + F = 2。其中V是顶点数，E是边数，F是面数。面是由边围成的区域，包括外部无限面。当已知V和E时，这个公式对于求面数非常有用。

Two important non-planar graphs are K₅ and K₃,₃. K₅ is the complete graph on five vertices, and K₃,₃ is the complete bipartite graph with three vertices in each set. A theorem by Kuratowski says that any non-planar graph contains a subgraph that is a subdivision of K₅ or K₃,₃. At A-Level you do not need the full theorem, but you should recognise these two graphs as non-planar.

两个

Published by TutorHao | A-Level Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）

Special Types of Graph | 特殊类型的图