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

"本章介绍了图的基本概念，包括无向图、有向图、顶点的度数、图的同构、完全图、正则图、子图与补图等。此外，还提到了无序积、多重集合以及图的一些特殊类型如零图、平凡图和空图的概念。" 在离散数学中，图是一种重要的结构，用于表示对象之间的关系。图的基本概念分为无向图和有向图。无向图G由顶点集V(G)和边集E(G)组成，其中边是顶点之间的无序连接，而有向图D则进一步增加了边的方向，边集E(D)包含的是V(D)的笛卡尔积V(D)×V(D)的多重子集。 1. **图的定义**：无向图G=<V,E>是一个二元组，V是非空的顶点集，E是V与V的无序积的多重子集，表示无向边。有向图D=<V,E>类似，但E是V×V的多重子集，表示有向边。 2. **图的阶**：如果一个图G的顶点数|V(G)|等于n，那么称此图为n阶图。 3. **零图与平凡图**：当边集E(G)为空时，G称为零图，若同时是n阶的，记作Nn。特别地，N1称为平凡图，它只有一个顶点，没有边。 4. **无序积与多重集合**：无序积是两个集合的元素配对形成的集合，允许元素重复且顺序无关。多重集合允许元素有重复度，即元素可以出现多次。 5. **顶点的度数**：在无向图中，顶点v的度是与v相连的边的数量。在有向图中，分为入度（进入顶点的边数）和出度（离开顶点的边数）。 6. **握手定理**：在一个无向图中，所有顶点的度数之和等于边数的两倍，这是因为每条边连接两个顶点，对总度数贡献了2。 7. **图的同构**：如果两个图可以互相映射，保持顶点间边的关系不变，那么它们是同构的，意味着它们在结构上是相同的。 8. **完全图**：在n阶图中，如果任意两个不同的顶点都由边连接，那么这个图称为完全图，记为Kn。 9. **正则图**：如果图中所有顶点的度数都相同，那么这个图是正则图。 10. **子图与补图**：子图是由原图的一部分顶点和这些顶点间的边组成的图；补图是原图中去掉所有已存在的边，添加所有未存在的边得到的新图。 以上是图论基础中的关键概念，它们在算法设计、网络分析、数据结构等多个领域都有广泛应用。理解并掌握这些概念对于深入研究图论及其应用至关重要。