图的基本概念：无向图与有向图

"本章介绍了图的基本概念，包括无向图和有向图的定义，图的同构，子图与补图，以及图的运算。定义了无序积和多重集合的概念，并通过实例展示了如何表示和绘制图。此外，还提到了图的阶数，即顶点的数量，以及边的数量。" 在离散数学中，图是一种重要的数据结构，它由顶点和边组成。标题提到的"定义的说明-图的基本概念"是第14章的核心内容，主要探讨了图的基本定义和性质。首先，定义14.1和14.2分别阐述了无向图和有向图的概念。无向图是顶点集V和边集E的二元组，其中边集E是V的无序积的多重子集，表示两个顶点之间的连接；而有向图的边集E是笛卡尔积V×V的多重子集，每条边具有明确的方向。 图的运算在描述中有所提及，比如并、交、差和环的和。如果两个图G1和G2有相同的顶点集且它们的边没有重叠，那么G1-G2表示去除G1中属于G2的边得到的新图，反之亦然。空图的概念是为了处理这种特殊情况，使得任何图与空图的并、交、差运算都有特定的结果。当G1和G2的边不重合时，它们的交集为空，而各自的边集不变。 图的环和可以用并、交、差来表示，公式G1⊕G2=(G1∪G2)-(G1∩G2)表明环和是包含在G1和G2所有边中的，但去除共同的边。这个运算在分析图的结构和性质时非常有用。 图的一些基本概念还包括顶点的度数，即一个顶点与其他顶点相连的边的数量，以及握手定理，它指出在一个无向图中，所有顶点的度数之和等于边的数量的两倍。此外，图的连通性、矩阵表示、子图和补图也是图论中的关键概念，它们分别涉及图中任意两个顶点是否存在路径、图的矩阵形式表示、包含原图所有顶点但边集不同的图，以及原图中所有不相邻边构成的新图。 本章还介绍了无序积和多重集合的概念，无序积是由两个集合的元素组成的无序对的集合，多重集合允许元素重复出现，且记录每个元素的重复度。这些概念在定义图的边集时尤为关键，因为边可能是重复的，并且可以是无方向的。 最后，图的阶数是顶点的数量，而边的数量反映了图的密度。对于无向图，如果每对顶点之间都有一条边，那么这样的图被称为完全图；如果图中所有顶点的度数都相同，那么它是正则图。这些概念帮助我们理解和分类不同类型的图，对于图算法的设计和分析至关重要。