图论 (Graph Theory) 是离散数学中的一个重要分支，它研究的是图（Graph）这种抽象的数学结构。图是由一些被称为“点”的实体和连接这些“点”的“线”组成的，能够以直观且强大的方式表示现实世界中各种复杂的连接关系、网络结构和相互依赖性。从社交网络中的人际关系，到城市间的交通路线，再到计算机网络中的数据流向，乃至生物学中的基因相互作用，图论都提供了强大的建模工具和分析框架。

1. 图 (Graph) 的基本概念

1.1 什么是图？

在图论中，一个 图 (Graph) G 是一个数学对象，它由两个相互关联的有限集合构成：

• 顶点集 (Vertex Set) V(G) 或简写为 V：这是一个非空集合，包含图中的所有“点”，这些点被称为 顶点 (Vertices)。顶点是图的基本组成单元，代表着我们所研究的实体。它们通常用 v1,v2,v3,… 或 a,b,c,… 等字母来标记，也可以是更具描述性的名称，如“北京”、“张三”或“路由器A”。
• 边集 (Edge Set) E(G) 或简写为 E：这是一个集合，包含图中的所有“线”，这些线被称为 边 (Edges)。每条边本身是 V(G) 的一个基数 (cardinality) 为2的子集，表示它连接的两个顶点，这两个顶点被称为这条边的 端点 (Endpoints)。边代表了顶点之间的某种关系或连接。

图的特性（普通图的限制）： 普通图（也称为简单图）是最常见的图类型，它有一些特定的限制：

1. 无自环 (No Loops)：由于每条边必须连接两个不同的顶点（基数为2的子集），因此在普通图中，任何一条边都不能以单个顶点作为它的两个端点。换句话说，一个顶点不能通过一条边连接到自身。例如，在社交网络中，你不能自己和自己是“好友”（除非是特殊的“关注”关系，那通常会用多重图或有向图来建模）。
2. 无多重边 (No Multiple Edges)：由于 E(G) 是一个集合，集合中的元素是唯一的，这意味着任意两个不同的顶点之间最多只能有一条边。例如，在城市交通网络中，如果只考虑普通图，那么任意两个城市之间最多只有一条直达的道路连接，不能有两条或更多条不同的直达道路。

边 (Edge) 的表示法： 一条以 v 和 w 为端点的边通常表示为集合 {v,w}，因为它是一个无序对。但为了简便，更常见的简写是 vw 或 wv。由于是无向图，边的顺序不重要，即 vw 和 wv 指的是同一条边。

1.2 图的表示 (Representing Graphs)

图通常以图示法 (Diagrammatically) 表示为由小圆点（顶点）和连接这些点的线段或曲线段（边）组成。这种视觉化表示是图论学习和应用中非常重要的一部分。值得注意的是，顶点和边的相对位置（例如，顶点画在左边还是右边，边是直线还是曲线，顶点间距大小）在大多数情况下并不重要，重要的是它们之间的连接关系（即哪些顶点通过边相互连接）。

示例： 考虑一个简单的社交圈，有四个朋友：A、B、C、D。

• A和B是朋友
• A和C是朋友
• A和D是朋友
• B和C是朋友
• C和D是朋友

这个社交圈可以用图 G 来表示，其顶点集 V(G)={A,B,C,D}，边集 E(G)={AB,AC,AD,BC,CD}。 这个图可以有多种不同的画法，例如一个正方形 ABCD 加上一条对角线 AC，或者将顶点重新排列成三角形 ABC 并在 A,C 处分别连接到 D。无论怎么画，只要保持了这些朋友之间的连接关系不变，它们都代表同一个图。这种灵活性使得图论能够专注于抽象的连接结构，而不受具体几何布局的限制。(参考图：Lecture_5.01_Graph_Theory_and_Multigraph_Terminology.pdf 第4页的图示示例)

1.3 图的基本术语 (Basic Terminology)