图论基础：图的概念与同构

"本资源主要介绍了图的基本概念，包括图的定义、无向图与有向图、图的表示方法、图的一些基本术语，如顶点的度数、图的同构、完全图和正则图，以及子图与补图的概念。内容涉及离散数学，适用于中国地质大学本科生课程学习。" 在离散数学中，图是一种重要的数据结构，它广泛应用于网络分析、计算机科学、社会科学等多个领域。图的理论是图论的基础，本章节主要讲解了以下几个关键知识点： 1. **图的定义**：图可以分为无向图和有向图。无向图是一个有序的二元组 `<V, E>`，其中 `V` 是顶点集，`E` 是无序积 `V&V` 的多重子集，表示顶点之间的无向边。有向图同样是二元组 `<V, E>`，但 `E` 是笛卡尔积 `V×V` 的多重子集，表示有向边。 2. **无序积与多重集合**：无序积是集合 `A` 和 `B` 的元素组成的无序对集合，允许元素重复并可以自相连接。多重集合则是允许元素重复出现的集合，每个元素的重复度表示该元素出现的次数。 3. **图的表示**：可以用图形直观地表示图，顶点用圆圈或点表示，无向边用线段表示，有向边用带箭头的线段表示。 4. **图的一些概念**：如 `G` 通常代表无向图，而 `D` 代表有向图。`V(G)` 和 `E(G)` 分别表示图 `G` 的顶点集和边集。n 阶图指的是有 n 个顶点的图。 5. **顶点的度数**：在无向图中，顶点的度是与其相邻的边的数量。根据握手定理，无向图中所有顶点的度数之和等于边数的两倍。 6. **图的同构**：如果两个图的顶点和边可以一对一对应，且保持边连接关系不变，这两个图就是同构的，表示它们在结构上是相同的。 7. **完全图**：在无向图中，如果任意两个不同的顶点都由边相连，这样的图称为完全图。完全图的边数等于顶点数乘以 (顶点数 - 1) 再除以 2。 8. **正则图**：如果图中所有顶点的度数都相同，那么这个图是正则图。 9. **子图与补图**：子图是原图的一部分，包含原图中的一些顶点和这些顶点之间的一些边。补图是在原图的基础上，将所有未连接的顶点对添加边，或删除所有已连接的顶点对的边，得到的新图。 在实际应用中，这些概念不仅用于解决数学问题，还在算法设计、网络分析、社交网络研究等方面发挥着重要作用。理解并掌握这些基础知识对于进一步学习图论及其应用至关重要。