📚 Special Types of Graph | 特殊图类型
In the study of graph theory, graphs can be classified into several special types based on their structure and properties. Understanding these special graphs is essential for solving problems in networks, routing, matching, and optimisation. This article explores the most common special types of graph that appear in the Edexcel A-Level Decision Mathematics syllabus.
在图论的学习中，根据结构和性质的不同，图可以被分为几种特殊类型。理解这些特殊图对于解决网络、路径、匹配和优化问题至关重要。本文探讨了Edexcel A-Level决策数学大纲中最常见的特殊图类型。
1. Complete Graphs | 完全图
A complete graph is a simple graph in which every pair of distinct vertices is connected by a unique edge. A complete graph with n vertices is denoted by Kₙ.
完全图是一种简单图，其中每一对不同的顶点都由一条唯一的边连接。具有n个顶点的完全图记为Kₙ。
In Kₙ, each vertex has degree (n – 1) because it is adjacent to all other vertices. The total number of edges is n(n – 1)/2. For example, K₃ is a triangle with 3 edges, K₄ is a tetrahedron with 6 edges, and K₅ has 10 edges. Complete graphs are often used to model fully connected networks.
在Kₙ中，每个顶点的度数为(n – 1)，因为它与所有其他顶点相邻。总边数为n(n – 1)/2。例如，K₃是一个三角形，有3条边；K₄是一个四面体，有6条边；K₅有10条边。完全图通常用于建模完全连通的网络。
Complete graphs are also regular graphs (specifically (n – ltonian for n ≥ 3. They are not planar for n ≥ 5 because K₅ is a classic non-planar graph.
完全图也是正则图（具体来说是(n – 1)-正则图），并且对于n ≥ 3是哈密顿图。当n ≥ 5时，它们不是平面图，因为K₅是经典的非平面图。
2. Bipartite Graphs | 二分图
A bipartite graph is a graph whose vertex set can be partitioned into two disjoint sets U and V such that every edge connects a vertex in U to a vertex in V. There are no edges connecting vertices within the same set.
二分图是这样一种图：它的顶点集可以划分为两个不相交的集合U和V，并且每条边都连接U中的一个顶点和V中的一个顶点。在同一集合内部没有边相连。
A useful characterisation: a graph is bipartite if and only if it contains no odd cycles. This property allows us to test bipartiteness by attempting a 2-colouring of the vertices. Common examples include matching problems (e.g. jobs to workers) and social networks.
一个有用的特征是：一个图是二分图当且仅当它不包含奇圈。这个性质允许我们通过尝试对顶点进行二着色来测试是否为二分图。常见的例子包括匹配问题（例如工作与工人）和社交网络。
3. Complete Bipartite Graphs | 完全二分图
A complete bipartite graph, denoted by Kₘ,ₙ, is a bipartite graph where |U| = m, |V| d every possible edge between U and V is present. There are no edges within U or within V.
完全二分图，记为Kₘ,ₙ，是一种二分图，其中|U| = m，|V| = n，并且U和V之间所有可能的边都存在。U内部和V内部都没有边。
n. The degree of each vertex in U is n, and each vertex in V has degree m. For example, K₂,₃ has 2 vertices in one part and 3 in the other, giving 6 edges. K₃,₃ is well known as a non-planar graph and is the minimal complete bipartite graph that is non-planar.
Kₘ,ₙ中的总边数为m × n。U中每个顶点的度数为n，V中每个顶点的度数为m。例如，K₂,₃在一个部分有2个顶点，另一部分有3个顶点，共有6条边。K₃,₃是著名的非平面图，也是最小的非平面完全二分图。
4. Trees | 树
A tree is a connected graph with no cycles. Equivalently, a tree is a connected acyclic graph. A tree with n vertices has exactly n – 1 edges. Removing any edge disconnects the tree, and adding any edge creates a cycle.
树是一种没有环的连通图。等价地说，树是连通且无环的图。具有n个顶点的树恰好有n – 1条边。删除任意一条边都会使树不连通，添加任意一条边都会产生一个环。
Trees play a fundamental role in graph algorithms, such as minimum spanning tree algorithms (Kruskal, Prim) and network routing. There is exactly one unique simple path between any two vertices in a tree. A rooted tree has a designated root vertex, often used in decision trees and data structures.
树在图算法中起着基础性的作用，例如最小生成树算法（克鲁斯卡尔、普里姆）和网络路由。树中任意两个顶点之间恰好存在一条唯一的简单路径。有根树有一个指定的根顶点，通常用于决策树和数据结构中。
5. Directed Graphs (Digraphs) | 有向图
A directed graph (or digraph) consists of vertices and directed edges, often called arcs. Each arc has an initial vertex (tail) and a terminal vertex (head), represented by an arrow. This models one-way relationships such as traffic flow or precedence constraints.
有向图由顶点和有向边（通常称为弧）组成。每条弧都有一个起点（尾部）和终点（头部），用箭头表示。它可以模拟单向关系，如交通流或先后顺序约束。
In a digraph, we distinguish between in-degree (number of arcs entering) and out-degree (number of arcs leaving). A directed graph is strongly connected if there is a directed path from every vertex to every other vertex. Directed acyclic graphs (DAGs) are used to represent dependencies and scheduling problems.
在有向图中，我们区分入度（进入的弧数）和出度（离开的弧数）。如果从一个顶点到其他每个顶点都存在有向路径，则称该有向图为强连通的。有向无环图（DAG）用于表示依赖关系和调度问题。
6. Eulerian Graphs | 欧拉图
An Eulerian graph is a connected graph that contains an Eulerian circuit – a closed trail that traverses every edge exactly once. For an undirected graph, the necessary and sufficient condition is that every vertex has even degree. If exactly two vertices have odd degree, the graph is semi-Eulerian and contains an Eulerian trail but not a circuit.
欧拉图是包含一条欧拉回路的连通图——一条恰好经过每条边一次的闭合迹。对于无向图，存在欧拉回路的充要条件是所有顶点的度数均为偶数。如果恰好有两个顶点的度数为奇数，那么该图是半欧拉图，它包含一条欧拉迹但没有欧拉回路。
The classic 'Seven Bridges of Konigsberg' problem was solved by Euler using these concepts. Eulerian graphs are useful in routing problems like the Chinese Postman Problem, where the goal is to traverse all edges of a network efficiently.
经典的“柯尼斯堡七桥问题”就是欧拉利用这些概念解决的。欧拉图在路径规划问题（如中国邮递员问题）中很有用，该问题的目标是高效地遍历网络中的所有边。
7. Hamiltonian Graphs | 哈密顿图
A Hamiltonian graph is a graph that contains a Hamiltonian cycle – a cycle that visits every vertex exactly once (except the start/end vertex). Unlike Eulerian graphs, there is no simple necessary and sufficient condition for Hamiltonicity; it is an NP-complete decision problem in general.
哈密顿图是包含一条哈密顿回路的图——一条恰好访问每个顶点一次（起点/终点除外）的回路。与欧拉图不同，判断哈密顿图没有简单的充要条件；一般来说这是一个NP完全判定问题。
Sufficient conditions include Dirac' ertices has minimum degree at least n/2, then it is Hamiltonian. The Travelling Salesman Problem (TSP) seeks a minimum-weight Hamiltonian cycle in a weighted graph, a central problem in combinatorial optimisation.
充分条件包括狄拉克定理：如果具有n≥3个顶点的简单图的最小度数至少为n/2，那么它是哈密顿图。旅行商问题（TSP）旨在寻找加权图中权重最小的哈密顿回路，这是组合优化中的一个核心问题。
8. Weighted Graphs | 加权图
A weighted graph is a graph (directed or undirected) in which each edge (or arc) is assigned a numerical value, called its weight. Weights typically represent cost, distance, time, or capacity. Many algorithms, such as Dijkstra's shortest path and Kruskal's minimum spanning tree, operate on weighted graphs.
加权图是将每条边（或弧）赋予一个数值（称为权重）的图（有向或无向）。
Published by TutorHao | A-Level Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
或截图后用「扫一扫 → 相册」选择本图