图论基础：图的概念与性质

"本章介绍了图的基本概念，包括无向图和有向图的定义，图的同构、完全图、正则图、子图、补图等概念，以及连通性和度数等相关性质。此外，还涉及无序积、多重集合、顶点的度数和握手定理的应用。" 在离散数学中，图是一种重要的数据结构，用于表示对象之间的关系。图的基本概念是理解和应用图论的关键。 1. **图的定义**：无向图是一个由顶点集V和边集E组成的有序二元组<V, E>，其中E是V的无序积V&V的多重子集，表示顶点间的关系。有向图则是由顶点集V和边集E组成的有序二元组<D, E>，其中E是V的笛卡尔积V×V的多重子集，边带有方向。 2. **无序积与多重集合**：无序积是两个集合A和B的所有可能的无序对组成的集合，而多重集合允许元素重复出现，重复度表示元素出现的次数。 3. **简单图与多重图**：简单图中每对顶点之间至多有一条边，不允许自环（边的两个端点相同）和多重边（同一对顶点间有多条边）。多重图则允许多重边和自环。 4. **顶点的度数与握手定理**：在无向图中，一个顶点的度是与其相邻的边的数量。握手定理指出，无向图中所有顶点的度数之和等于边数的两倍。 5. **图的同构**：两个图是同构的，如果它们之间存在一个一一对应的顶点映射，保持了边的关系不变。 6. **完全图与正则图**：完全图是每个顶点都与其他所有顶点相连的图。正则图是所有顶点具有相同度数的图。 7. **子图与补图**：子图是原图中一部分顶点及其连接的边组成的图。补图是通过去掉原图中所有边形成的新图，或者在原图的顶点集上添加所有原图中不存在的边。 8. **图的连通性**：无向图的点连通度是使得图不连通所需的最小顶点删除数，边连通度则是使得图不连通所需的最小边删除数。有向图的连通性分为强连通（任何两个顶点都有双向路径）和弱连通（去掉边的方向后成为连通的无向图）。 9. **表示方法**：图可以用图形方式表示，顶点用圆圈或点，无向边用直线，有向边用带箭头的线。 10. **应用**：图论广泛应用于网络分析、算法设计、社会网络、生物信息学等领域，如最短路径问题、网络流问题等。 掌握这些基本概念和性质对于深入学习图论和应用图论解决实际问题至关重要。在实际问题中，例如在社交网络分析中，人们可以用图来表示用户之间的关系；在网络设计中，可以利用图论找到最佳路由策略。通过熟练运用图的性质和关系，可以解决许多复杂的问题。