Graph Theory | 图论

📚 Graph Theory | 图论

Graph theory is a fundamental branch of mathematics that studies networks of vertices connected by edges. It underpins many real-world optimisation problems, from route planning to circuit design, and forms a core topic in the Edexcel A-Level Further Mathematics Decision Mathematics syllabus.

图论是数学中研究由边连接的顶点网络的基础分支。它支撑着从路线规划到电路设计等众多现实世界中的优化问题，也是 Edexcel A-Level 进阶数学决策数学考纲中的核心内容。

1. What is a Graph? | 什么是图？

A graph G consists of a set of vertices (or nodes) V and a set of edges E that connect pairs of vertices. Formally we write G = (V, E). Vertices are usually drawn as dots, and edges as lines or arcs joining them. Graphs are used to model networks such as roads, flights, social connections and electrical circuits.

图 G 由顶点集 V 和边集 E 组成，边连接一对顶点。形式上写作 G = (V, E)。顶点通常画成圆点，边画成连接两点的线段或弧线。图可用于模拟道路、航班、社交关系和电路等网络。

In the Edexcel D1 specification, you will encounter simple graphs (at most one edge between any two vertices and no loops), digraphs (edges have direction) and weighted graphs (each edge carries a numerical value). Understanding the precise definitions is the first step to success in examination questions.

在 Edexcel D1 考纲中，你会遇到简单图（任意两个顶点之间至多一条边且无环）、有向图（边具有方向）和赋权图（每条边带有数值）。准确理解定义是在考试中取得成功的首要步骤。

2. Key Terminology | 关键术语

Two vertices are adjacent if they are joined by an edge; the edge is then said to be incident to each of them. An edge that joins a vertex to itself is called a loop. Parallel edges are multiple edges connecting the same pair of vertices. A simple graph is one with no loops and no parallel edges.

如果两个顶点由一条边连接，则称它们相邻；此时称该边与这两个顶点相关联。连接顶点到自身的边称为环。连接同一对顶点的多条边称为平行边。没有环且没有平行边的图称为简单图。

The order of a graph is the number of vertices |V|, and the size is the number of edges |E|. A complete graph Kₙ has every possible edge: Kₙ has exactly n(n−1)/2 edges. These basic definitions appear frequently in short-answer questions.

图的阶是顶点数 |V|，图的大小是边数 |E|。完全图 Kₙ 包含所有可能的边：Kₙ 恰好有 n(n−1)/2 条边。这些基本定义经常出现在简答题中。

3. Types of Graphs | 图的类型

A graph is connected if there is a path between every pair of vertices; otherwise it is disconnected and splits into connected components. The complete graph Kₙ is connected and has every vertex of degree n−1.

如果图中任意一对顶点之间都存在一条路径，则称该图是连通的；否则称其为不连通的，并分解为若干连通分量。完全图 Kₙ 是连通的，且每个顶点的度均为 n−1。

A bipartite graph has its vertex set partitioned into two parts A and B such that every edge joins a vertex in A to a vertex in B. The complete bipartite graph Kₘ,ₙ joins every vertex of A (with m vertices) to every vertex of B (with n vertices). A directed graph (digraph) uses arcs with arrows to indicate one-way relationships, while a weighted graph assigns costs, distances or times to edges — essential for optimisation algorithms.

二部图的顶点集被划分为两个部分 A 和 B，每条边均连接 A 中一个顶点与 B 中一个顶点。完全二部图 Kₘ,ₙ 将 A 中每个顶点（共 m 个）与 B 中每个顶点（共 n 个）相连。有向图使用带箭头的弧来表示单向关系，而赋权图为每条边赋予成本、距离或时间——这对优化算法至关重要。

4. Degree and the Handshaking Lemma | 度与握手引理

The degree (or valency) of a vertex v, written d(v), is the number of edges incident to v, with loops counted twice. A vertex of degree 0 is isolated, and a vertex of degree 1 is a leaf.

顶点 v 的度（或价）记作 d(v)，是与 v 相关联的边的条数，其中环计两次。度为 0 的顶点称为孤立点，度为 1 的顶点称为叶子。

The handshaking lemma states that in any graph the sum of all vertex degrees equals twice the number of edges:

握手引理指出，在任何图中，所有顶点度之和等于边数的两倍：

Σ d(v) = 2|E|

A crucial consequence is that the number of vertices of odd degree is always even. This result underlies the existence criteria for Eulerian trails and circuits.

一个关键推论是：奇度顶点的个数总是偶数。这一结论是欧拉迹与欧拉回路存在性判定的基础。

5. Connectedness and Paths | 连通性与路径

A walk is a sequence of vertices and edges, each edge joining the preceding and following vertices. A trail is a walk with no repeated edges; a path is a trail with no repeated vertices. If a path starts and ends at the same vertex and has no other repeated vertices, it is called a cycle.

通路（walk）是顶点和边的交替序列，每条边连接前一个与后一个顶点。迹（trail）是不重复经过任何边的通路；路径（path）是不重复经过任何顶点的迹。若一条路径的起点与终点相同且没有其他重复顶点，则称其为圈（cycle）。

A connected graph contains a path between any two of its vertices. A bridge is an edge whose removal disconnects the graph — recognising bridges helps in understanding the structure of a network, and is useful when applying algorithms such as Fleury

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

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