📚 Definitions and Properties of Graphs | 图的定义与性质
Graph theory is a branch of mathematics that models pairwise relations between objects. A graph consists of vertices (or nodes) connected by edges. Understanding the fundamental definitions and properties of graphs is essential in IB Mathematics for solving real-world problems such as network routing, scheduling, and social network analysis. This article outlines the core concepts you need to master, including vertex degrees, types of walks, connectivity, special graphs, and matrix representations.
图论是数学的一个分支，用于模拟对象之间的成对关系。图由顶点（或节点）和连接它们的边组成。理解图的基本定义和性质对于解决IB数学中的实际问题至关重要，如网络路由、调度和社交网络分析。本文将概述你需要掌握的核心概念，包括顶点度、路径类型、连通性、特殊图以及矩阵表示。
1. Graphs: Vertices and Edges | 图：顶点和边
A graph G = (V, E) is defined by a non-empty set V of vertices and a set E of edges, where each edge connects either an unordered pair (undirected) or an ordered pair (directed) of vertices. The endpoints of an edge e linking u and v are u and v; we say e is incident with u and v, and that u and v are adjacent.
图 G = (V, E) 由一个非空的顶点集 V 和一个边集 E 定义，每条边连接一对无序顶点（无向）或有序顶点（有向）。连接 u 和 v 的边 e 的端点是 u 和 v；我们称 e 与 u、v 关联，并且 u 与 v 相邻。
2. Directed and Undirected Graphs | 有向图和无向图
In an undirected graph, edges are unordered pairs {u, v} and have no orientation; the relation is symmetric. In a directed graph (digraph), each edge is an ordered pair (u, v) called an arc, where u is the tail and v is the head. Mixed graphs contain both types of edges. Unless stated otherwise, ‘graph’ usually implies an undirected simple graph in IB contexts.
在无向图中，边是无序对 {u, v}，没有方向性，关系是对称的。在有向图中，每条边是一个有序对 (u, v)，称为弧，其中 u 是起点，v 是终点。混合图包含两种边。除非特别说明，在IB语境中“图”通常指无向简单图。
3. Simple Graphs, Multigraphs, and Loops | 简单图、多重图和环
A simple graph has neither loops (edges connecting a vertex to itself) nor multiple edges between the same pair of vertices. A multigraph allows multiple edges (parallel edges). A pseudograph permits both loops and multiple edges. Most theorems studied at IB level refer to simple graphs, but it is important to recognise the extended definitions.
简单图既没有环（连接顶点自身的边），也没有在同一对顶点之间的多条边。多重图允许多条边（平行边）。伪图允许环和多重边。IB阶段研究的大多数定理针对简单图，但识别这些扩展定义很重要。
4. Degree of a Vertex and Handshaking Lemma | 顶点的度与握手引理
The degree of a vertex v, denoted deg(v), is the number of edges incident with v, with loops counted twice. An isolated vertex has degree 0. The minimum degree is δ(G) and the maximum degree is Δ(G). A fundamental result is the Handshaking Lemma:
顶点 v 的度，记为 deg(v)，是与 v 关联的边的条数，环计为2。孤立点的度为0。最小度记为 δ(G)，最大度记为 Δ(G)。一个基本结果是握手引理：
∑v∈V deg(v) = 2|E|
This holds because each edge contributes exactly two to the sum of degrees. An immediate corollary is that any graph has an even number of vertices of odd degree.
该引理成立是因为每条边恰好为度数总和贡献2。一个直接推论是：任何图中奇度顶点必有偶数个。
5. Walks, Trails, Paths, and Cycles | 途径、迹、路径和回路
A walk is an alternating sequence of vertices and edges v0, e1, v1, e2, …, vk where each edge is incident with the vertices before and after it. A trail is a walk with no repeated edges. A path is a trail with no repeated vertices (except possibly the endpoints in some contexts). A closed walk starts and ends at the same vertex. A cycle (or circuit) is a closed walk with no repeated vertices except the start-end vertex, and length at least 1.
途径是顶点和边的交替序列 v0, e1, v1, e2, …, vk，其中每条边关联于其前后的顶点。迹是没有重复边的途径。路径是没有重复顶点的迹（某些语境中允许首尾重合）。闭途径起点和终点相同。回路（或圈）是除起点与终点重合外无其他重复顶点的闭途径，且长度至少为1。
The length of a walk is the number of edges traversed. A path of n vertices is denoted Pn; a cycle of n vertices is Cn. In IB problems, distinguishing walks, trails, paths, and cycles is essential for solving routing and connectivity questions.
途径的长度是经过的边数。n个顶点的路径记作 Pn；n个顶点的回路记作 Cn。在IB问题中，区分途径、迹、路径和回路对于解决路由和连通性问题至关重要。
6. Connected Graphs and Components | 连通图与连通分量
An undirected graph is connected if there is a path between every pair of vertices. Otherwise, it is disconnected. The maximal connected subgraphs are called connected components. A vertex whose removal increases the number of components is a cut-vertex (articulation point); an edge whose removal does the same is a bridge (cut-edge).
无向图中若任意两个顶点之间存在路径，则图是连通的；否则是不连通的。极大的连通子图称为连通分量。移除后会导致连通分量数增加的顶点称为割点；移除后产生同样效果的边称为桥（割边）。
For directed graphs, strong connectivity requires directed paths in both directions between any two vertices, while weak connectivity considers the underlying undirected graph.
对于有向图，强连通要求任意两个顶点之间存在双向有向路径，而弱连通仅考虑底层的无向图。
7. Subgraphs and Spanning Subgraphs | 子图与生成子图
A subgraph H = (V’, E’) of G satisfies V’ ⊆ V and E’ ⊆ E, with every edge in E’ having its endpoints in V’. If V’ = V, H is a spanning subgraph. An induced subgraph is obtained by taking a subset of vertices and including every edge of G whose both endpoints lie in that subset.
图 G 的子图 H = (V’, E’) 满足 V’ ⊆ V 且 E’ ⊆ E，并且 E’ 中每条边的端点都在 V’ 中。如果 V’ = V，则 H 是生成子图。导出子图是通过取一个顶点子集并包含 G 中两端点均在该子集中的所有边而得到的。
Key examples: a spanning tree is a spanning subgraph that is a tree; removing a vertex from a graph induces a subgraph on the remaining vertices.
重要例子：生成树是树状的生成子图；从图中移除一个顶点会在剩余顶点上导出一个子图。
8. Adjacency and Incidence Matrices | 邻接矩阵与关联矩阵
The adjacency matrix A of a simple graph with n vertices is an n × n matrix where Aij = 1 if vertices i and j are adjacent, and 0 otherwise. For undirected graphs, A is symmetric. Powers of A count walks: (Ak)ij gives the number of walks of length k from i to j.
具有 n 个顶点的简单图的邻接矩阵 A 是一个 n × n 矩阵，其中若顶点 i 和 j 相邻，则 Aij = 1，否则为0。对于无向图，A 是对称矩阵。A 的幂可对途径计数：(Ak)ij 给出了从 i 到 j 长度为 k 的途径数目。
The incidence matrix M relates vertices to edges: for an undirected graph, Mve = 1 if vertex v is incident with edge e, and 0 otherwise. For digraphs, entries are -1 (tail) and +1 (head).
关联矩阵 M 关联顶点和边：对于无向图，若顶点 v 与边 e 关联，则 Mve = 1，否则为0。对于有向图，条目为 -1（起点）和 +1（终点）。
9. Bipartite Graphs and Trees | 二分图与树
A graph is bipartite if its vertex set can be partitioned into two disjoint sets U and W such that every edge connects a vertex in U to a vertex in W. There are no edges inside U or inside W. A complete bipartite graph Km,n has all possible edges between two partite sets of sizes m and n. A graph is bipartite if and only if it contains no odd cycles.
若一个图的顶点集可以划分为两个互不相交的集合 U 和 W，使得每条边连接 U 中的一个顶点与 W 中的一个顶点，则该图是二分图。U 或 W 内部没有边。完全二分图 Km,n 在大小为 m 和 n 的两个部分集之间包含所有可能的边。一个图是二分图当且仅当它不含奇圈。
A tree is a connected acyclic graph. For a tree with n vertices, the number of edges is exactly n – 1. Any two vertices are connected by a unique simple path. Removing any edge disconnects a tree. A leaf is a vertex of degree 1. Trees are fundamental in data structures and spanning tree algorithms.
树是连通的无环图。对于 n 个顶点的树，边数恰为 n – 1。任意两个顶点之间存在唯一的一条简单路径。移除任意一条边都会使树不连通。度数为1的顶点称为树叶。树在数据结构和生成树算法中起着根本作用。
10. Graph Isomorphism | 图同构
Two graphs G1 and G2 are isomorphic if there exists a bijection f: V(G1) → V(G2) such that any two vertices u and v are adjacent in G1 if and only if f(u) and f(v) are adjacent in G2. In other words, isomorphic graphs are structurally identical but may be drawn differently.
如果存在双射 f: V(G1) → V(G2)，使得 G1 中任意两个顶点 u 和 v 相邻当且仅当 f(u) 与 f(v) 在 G2 中相邻，则两个图 G1 和 G2 同构。换句话说，同构图在结构上完全相同，只是画法可能不同。
Isomorphism invariants are properties preserved under isomorphism: number of vertices, number of edges, degree sequence, presence of cycles of given lengths, and connectivity. Checking invariants helps to prove two graphs are not isomorphic, but finding a bijection is necessary to confirm isomorphism.
同构不变量是在同构下保持不变的性质：顶点数、边数、度序列、特定长度圈的存在性以及连通性。检查不变量有助于证明两个图不同构，但要确认同构，必须找到一个双射。
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply