图的基本概念：通路与回路的表示方法

"本文介绍了图的基本概念，包括通路和回路的简单表示法，以及图的分类如简单图、多重图、有向图和无向图。文中还涉及了顶点的度数、图的同构、完全图、正则图、子图和补图等相关概念。" 在离散数学中，图是一种重要的数据结构，用于表示对象之间的关系。图的基本概念包括图的定义、图的类型以及相关属性。图可以分为无向图和有向图，无向图中的边没有方向，而有向图中的边具有方向。 14.1 图的基本概念 无向图是一个由顶点集V和边集E组成的二元组<V, E>，其中E是V与V的无序积的一个多重子集。有向图同样由顶点集V和边集E组成，但E是V与V的笛卡尔积的多重子集。在无向图中，边用顶点之间的连线表示，而在有向图中，边用带箭头的线表示。 14.2 通路与回路 通路和回路是图中的路径。通路是一系列相邻的边，使得每条边的起点是前一条边的终点，但第一个顶点和最后一个顶点不相同。回路则是一个通路，它的起始和结束顶点是相同的。在简单图中，通路和回路可以用顶点的顺序来表示。对于非简单图，如果仅用顶点顺序无法完全描述某些通路或回路，可以采用混合表示法，即在顶点序列中加入一些边（平行边或环）。 14.3 图的连通性 图的连通性是指图中任意两个顶点间是否存在路径。如果图中任何两个不同的顶点都存在通路相连，则称该图为连通图。反之，如果存在至少两个顶点之间没有通路，则称该图不连通。 14.4 图的矩阵表示 图可以使用邻接矩阵或邻接表等数据结构进行存储和操作。邻接矩阵是一个二维数组，其中的元素表示对应顶点之间是否存在边。邻接表则是为每个顶点存储其相邻顶点的列表。 14.5 图的运算 图的运算包括图的生成树、最短路径计算、图的遍历（如深度优先搜索和广度优先搜索）等。 在图论中，顶点的度数是指与该顶点相邻的边的数量。握手定理指出，在无向图中，所有顶点的度数之和等于边数的两倍。图的同构是指两个图在结构上是相同的，只是顶点的标记可能不同。完全图是每个顶点与其他所有顶点都有一条边相连的图，而正则图是所有顶点具有相同度数的图。子图是从原图中选取一部分顶点及其相邻边构成的新图，补图是原图中所有未连接的顶点对都用边连接，已连接的顶点对去除边后的图。 这些基本概念构成了图论的基础，广泛应用于计算机科学、网络分析、社会网络、生物信息学等领域。理解并掌握这些概念有助于解决各种实际问题。