1 基本概念
无向图是图论中最基础的对象之一，用于描述由顶点及其相互连接关系构成的结构。在无向图中，边只表示两个顶点之间存在联系，不强调方向，因此常被用来刻画对等关系、网络连通以及结构组合等问题。
1.1 图的定义
图通常由顶点集合与边集合共同确定。顶点是图中的基本元素，边则连接两个顶点，表示它们之间存在某种关系。无向图中的边不区分起点和终点，因而边的两端具有对称性。
1.1.1 顶点与边
顶点是图中的节点，常用来表示对象、位置或状态；边是连接两个顶点的线段式抽象，表示对象之间的关联。若两个顶点被一条边连接，则称它们之间存在邻接关系。
1.1.2 邻接关系
在无向图中，若两个顶点由同一条边连接，则它们彼此邻接。邻接关系不具有方向性，因此“从一个顶点到另一个顶点”与“从后者到前者”在图的结构意义上没有区别。
1.1.3 关联关系
边与顶点之间存在关联关系。若某条边以某顶点为端点，则称该边与该顶点关联。对无向图而言，一条边总是与它连接的两个顶点同时关联。
1.2 无向图的表示
无向图既可以用集合方式抽象表示，也可以借助符号记号或图形示意来直观呈现。不同表示方法服务于不同场景：集合表示适合数学描述，图形表示便于观察结构，符号表示则利于计算与证明。
1.2.1 顶点集与边集
无向图通常写作由顶点集和边集组成的二元结构，其中顶点集记录全部节点，边集记录所有连接关系。边集中的每条边对应一个无序顶点对，因此一条边所连接的两个端点没有先后之分。
1.2.2 图的记号
图论中常用特定符号表示无向图，例如用大写字母指代整个图，用顶点集和边集分别记录其组成部分。若需要强调无向性，边常写作无序对，以体现其对称特征。
1.2.3 图的可视化表示
无向图的可视化通常采用点与线的方式：点表示顶点，线段表示边。在线图中，边没有箭头，能够直观反映结构的连通程度、局部聚集情况以及整体形态。
1.3 基本术语
无向图研究中包含若干常见术语，这些概念是后续讨论分类、性质与算法的基础。理解这些术语，有助于准确描述图的局部结构与整体特征。
1.3.1 相邻顶点
若两个顶点由一条边连接，则称它们为相邻顶点。相邻顶点之间直接相连，通常是路径构造与遍历分析中的基本单元。
1.3.2 自环
自环是指一条边的两个端点都落在同一个顶点上。它表示顶点与自身相连，在某些图模型中允许出现，但在简单图中通常被排除。
1.3.3 重边
重边是指连接同一对顶点的多条边。它反映同一关系的多次出现或多种连接方式，在多重图中较为常见，而在简单图中不被允许。
2 无向图的分类
无向图可以依据边的重复情况、连接完备程度以及顶点划分方式进行分类。不同类型的无向图在结构上各有特点，也对应不同的理论结论与应用场景。
2.1 简单图
简单图是无向图中最常见的一类，结构较为规整，便于分析和证明。它强调边的唯一性与顶点间连接的清晰性。
2.1.1 无自环图
简单图不允许自环，即任何顶点都不能通过一条边连接到自身。这一限制使图的局部结构更为规范。
2.1.2 无重边图
简单图也不允许重边，任意一对顶点之间最多只有一条边。这样可以避免同一连接关系的重复计数。
2.2 多重图
多重图允许某些边重复出现，因此比简单图更灵活。它适合描述具有多条平行连接的对象关系，例如多通道线路或重复联系网络。
2.2.1 平行边
平行边是指连接同一对顶点的多条边。它们在图形上可能彼此平行，也可能以其他方式并列出现，但逻辑上都对应同一对端点。
2.2.2 允许重复连接
多重图允许同一对顶点之间出现多次连接，这使得图可以表达更丰富的关系强度或连接次数。与简单图相比，它在建模上更具包容性。
2.3 完全图
完全图是一类连接最为充分的无向图。它的显著特征是任意两个不同顶点之间都存在边，因此结构高度密集。
2.3.1 完全无向图
完全无向图指每一对不同顶点都直接相连的无向图。若顶点数为固定值，则其边数也随之确定，具有典型的组合结构特征。
2.3.2 顶点对的全连接性
完全图体现了顶点对之间的全连接性，即任意顶点都与其余所有顶点相邻。这种性质使其成为研究极端密集图结构的重要模型。
2.4 二部图
二部图是一类可以按特定规则划分顶点集合的无向图。它在匹配、分配与关系建模中十分常见，结构上具有明显的分区特征。
2.4.1 顶点划分
二部图的顶点可以分成两个互不重叠的集合，并且边只连接不同集合中的顶点，而不连接同一集合内部的顶点。这种划分是二部图的核心特征。
2.4.2 完全二部图
完全二部图是二部图中的特殊形式，其中两个顶点集合之间的每一对顶点都相连。它常用于表示两类对象之间的全面对应关系。
3 无向图的性质
无向图的性质主要围绕顶点度、路径结构和连通性展开。这些性质既反映图的整体形态，也为算法设计和结构分析提供依据。
3.1 顶点的度
顶点的度是衡量一个顶点与外界联系紧密程度的重要指标。它在无向图中具有直观而重要的解释。
3.1.1 度数定义
在无向图中，某顶点的度是指与该顶点关联的边数。若存在自环，则通常按约定对度的计算作特殊处理，但在基本讨论中，度主要反映连接数量。
3.1.2 握手定理
握手定理表明，无向图中所有顶点度数之和等于边数的两倍。其原因在于每条边都会同时贡献给两个端点，因此总度数与边数之间存在固定关系。
3.1.3 奇度顶点与偶度顶点
按度数的奇偶性，顶点可分为奇度顶点和偶度顶点。握手定理推出，奇度顶点的个数总是偶数，这一结论在路径与回路分析中十分常用。
3.2 路径与回路
路径和回路用于描述图中顶点之间的经过顺序，是研究可达性与结构循环的重要概念。
3.2.1 通路
通路是指在图中沿边依次经过若干顶点形成的序列，允许顶点或边在一般意义下重复出现。它是描述连接关系最宽松的方式之一。
3.2.2 简单路径
简单路径指路径中除起点和终点可能相同的特殊情况外，其他顶点不重复出现。它比通路更严格，常用于寻找最短连接或分析无重复结构。
3.2.3 圈与回路
回路是起点与终点相同的路径，而圈通常强调除首尾顶点外其余顶点均不重复的封闭路径。它们描述了图中的闭合结构，是判断图性质的重要工具。
3.3 连通性
连通性反映图中顶点之间能否通过路径相互到达，是无向图研究的核心主题之一。许多算法和应用都以连通性为基础。
3.3.1 连通图
若图中任意两个顶点之间都存在路径，则称该图为连通图。连通图说明整个结构在路径意义上是统一的，没有彼此隔离的部分。
3.3.2 连通分量
连通分量是图中极大连通子图。若原图不是连通图，则可分解为若干个连通分量，每个分量内部连通，而分量之间彼此不相连。
3.3.3 割点与桥
割点是指删除该顶点后会使图的连通分量增加的顶点；桥则是删除后会使图连通性下降的边。它们是衡量图脆弱性与关键连接的重要概念。
4 典型特殊图
特殊图是无向图中的典型结构，往往具有明确的规则和较强的理论意义。它们在证明、构造和应用中都很常见。
4.1 树
树是一类结构简洁而重要的无向图，在层次关系、数据组织和最优连通结构中应用广泛。
4.1.1 树的定义
树通常指不含回路的连通无向图。它既保持整体连通，又避免形成闭合环路，因此结构最为稀疏而稳定。
4.1.2 树的基本性质
树具有多个等价特征，例如任意两点之间存在唯一简单路径，删除任意一条边都会破坏连通性等。这些性质使树成为图论中的基础模型。
4.1.3 生成树
生成树是包含原图全部顶点的树，且其边都来自原图。它在保持连通的同时尽量减少边数，常用于构造最小连接结构。
4.2 环图
环图是一类具有闭合循环结构的图，适合描述周期性连接或首尾相接的关系。
4.2.1 简单环
简单环是由若干顶点首尾相接形成的闭合路径，且除起终点外不重复顶点。它是最基本的环结构。
4.2.2 环图结构
环图整体呈循环排列，任意顶点通常与前后相邻的两个顶点相连。它具有明显的周期性，在建模循环过程时较为常用。
4.3 网格图
网格图由规则排列的顶点和边构成，常用于模拟平面空间中的离散结构。
4.3.1 平面网格结构
平面网格结构通常把顶点安排在行列式的位置上，边连接相邻网格点。其几何直观性较强，便于表示空间邻近关系。
4.3.2 邻接模式
网格图中的邻接模式多依赖于上下、左右等局部方向。不同方向上的连接规则构成了网格图的基本结构特征。
5 图的运算与结构
图的运算用于从已有图构造新图，并分析图之间的对应关系。这些操作有助于揭示图的局部与整体联系。
5.1 子图
子图是从原图中选取部分顶点和边构成的新图，能够反映原图的局部结构。
5.1.1 生成子图
生成子图通常保留原图的全部顶点，只在边的选择上有所限制。它适合观察在固定顶点集上的不同连接方式。
5.1.2 导出子图
导出子图是由原图中某个顶点子集及其间所有相关边组成的图。它强调从顶点集合出发自然派生出的结构。
5.2 图的并、交与补图
图的并、交与补图是常见的图运算，能够帮助比较和组合不同图的结构信息。
5.2.1 图的并
两个图的并可以理解为将它们的顶点和边集合合并，得到一个包含双方结构的新图。它常用于组合多个局部网络。
5.2.2 图的交
图的交保留两个图共有的顶点和共有的边，体现共同结构部分。它在比较图之间的重合程度时十分有用。
5.2.3 补图
补图是在给定顶点集上，将原图中不存在的边补充为边，而原有边则不再保留为缺失。补图常用于研究“非连接关系”的结构特征。
5.3 图同构
图同构用于判断两个图在结构上是否本质相同，只是顶点标号或排列方式不同。
5.3.1 同构的定义
若两个图之间存在一种顶点的一一对应关系，使得对应顶点之间的邻接关系完全保持一致，则称这两个图同构。换言之，它们的结构形态等价。
5.3.2 同构判定思路
同构判定通常从顶点数、边数、度序列、局部结构等特征入手，再进一步比较邻接关系是否可一致映射。实际判断往往需要综合多种不变量。
6 无向图的表示方法
无向图除了数学抽象表示外，还常用数据结构进行存储。不同表示方式各有优劣，适用于不同规模和不同类型的计算任务。
6.1 邻接矩阵
邻接矩阵是图的一种常见矩阵表示方法，结构清晰，便于判断两点之间是否相连。
6.1.1 矩阵构造
邻接矩阵通常以顶点为行列索引构成方阵。若两个顶点之间有边，则对应位置记为1或其他约定值；若无边，则记为0。
6.1.2 性质与特点
对于无向图，邻接矩阵通常是对称的，因为边没有方向。它便于快速查询边的存在性，但在稀疏图中可能占用较多空间。
6.2 邻接表
邻接表通过为每个顶点保存其相邻顶点列表来表示图，是实际编程中常见且高效的方式。
6.2.1 链式存储
邻接表通常为每个顶点建立一个链式或动态列表结构，记录其所有邻接点。该方法能直观反映局部连接关系，便于遍历。
6.2.2 空间效率
在边较少的图中，邻接表往往比矩阵更节省空间，因为它只存储实际存在的边。对于稀疏图，这种优势尤其明显。
6.3 关联矩阵
关联矩阵从顶点与边的对应关系出发进行表示，更强调边对顶点的影响方式。
6.3.1 顶点-边关系表示
关联矩阵的行通常对应顶点，列对应边。若某顶点与某边关联，则在相应位置标记特定值，以表明该顶点参与了这条边。
6.3.2 矩阵特征
关联矩阵能够直观表示每条边连接了哪些顶点。对于无向图，一条边通常对应两个非零位置，反映其两端同时关联的特性。
7 无向图的遍历与应用
遍历是图算法中的基础操作，借助遍历可以访问全部顶点、发现连通结构并解决各种实际问题。无向图的应用也往往依赖于遍历与搜索过程。
7.1 深度优先搜索
深度优先搜索是一种沿着图的分支尽可能深入访问顶点的遍历策略，常用于路径探索与结构分析。
7.1.1 递归遍历
深度优先搜索常借助递归实现，先访问当前顶点，再继续深入其未访问的邻接点，直至无法继续后再返回。
7.1.2 回溯过程
当某一分支无法继续深入时，算法会回退到上一个分叉点，继续探索其他未访问路径。这种回溯机制是深度优先搜索的重要特征。
7.2 广度优先搜索
广度优先搜索按照层次逐步扩展访问范围，适合处理分层结构和最短步数类问题。
7.2.1 分层遍历
广度优先搜索先访问起点的直接邻接顶点，再访问下一层邻接点，按距离逐层推进。它能够清晰呈现顶点的层次关系。
7.2.2 最短路径基础
在无权图中，广度优先搜索能够给出从起点到其他顶点的最少边数路径，因此常被视为最短路径问题的基础方法之一。
7.3 典型应用
无向图不仅是理论对象，也广泛服务于实际建模与计算任务。其应用范围覆盖通信、关系分析和组合优化等多个方向。
7.3.1 网络连通分析
无向图可用于分析网络是否连通、是否存在关键节点或关键边，以及网络在局部失效后的整体表现。
7.3.2 关系建模
在社交关系、合作关系或相互联系的场景中，无向图能有效表示对等连接，便于研究群体结构与关系密度。
7.3.3 组合问题求解
许多组合问题可以转化为无向图上的路径、匹配、覆盖或染色等问题。通过图模型，复杂问题往往能被更清晰地拆解与求解。