图论基本概念 图论是数学中研究图的结构及其性质的学科。图由顶点和连接顶点的边构成，用于表示物体之间的关系。下面从最基础的定义开始，逐步介绍图论的核心概念。 1. 什么是图？ 一个图 \( G \) 由两个集合构成： 顶点集 \( V \) ：表示研究对象，例如城市、人物或网络节点。 边集 \( E \) ：表示顶点之间的关系，例如道路、社交关系或连接线。 每条边连接两个顶点（可能相同，即自环）。例如，用 \( V = \{A, B, C\} \) 和边 \( E = \{(A, B), (B, C)\} \) 可以表示三个顶点及其连接关系。 2. 图的类型 根据边的性质，图可分为两类： 无向图 ：边没有方向，例如友谊关系（如果A认识B，则B也认识A）。 有向图 ：边有方向，例如网页链接（A链向B，但B未必链向A）。 3. 基本术语 邻接 ：若两个顶点被同一条边连接，则称它们相邻。例如，边 (A, B) 使A和B邻接。 度数 ：在无向图中，一个顶点的度数是与其相连的边的数量。有向图中分为 入度 （指向该顶点的边数）和 出度 （从该顶点指出的边数）。 路径 ：顶点序列，其中相邻顶点由边连接。例如路径 A-B-C 表示从A经B到C。 连通图 ：若图中任意两个顶点间至少存在一条路径，则图是连通的。否则称为非连通图（由多个连通分量组成）。 4. 图的表示方法 为便于分析，图常通过以下方式表示： 邻接矩阵 ：用矩阵 \( A \) 记录边，若顶点i与j之间有边，则 \( A[ i][ j ] = 1 \)（无向图矩阵对称）。 邻接表 ：为每个顶点维护一个列表，存储与其直接相邻的顶点，节省空间。 5. 简单应用示例 图论可解决实际问题，如： 最短路径问题 ：在地图导航中，寻找两个地点间的最短路线（使用Dijkstra算法等）。 社交网络分析 ：用顶点表示用户，边表示关注关系，分析社群结构。 以上内容涵盖了图的基本定义、分类、术语和表示方法。理解这些概念是进一步学习图论算法（如遍历、着色或网络流）的基础。