图的连通性：点连通度与边连通度

"本文主要介绍了图的基本概念，包括无向图和有向图的定义，图的连通性，以及图的度数等相关知识。" 在离散数学中，图是一种重要的抽象数据结构，用于表示对象之间的关系。图由顶点（或节点）和边组成。无向图和有向图是图的两种基本类型。无向图中的边没有方向，而有向图的边具有方向性。 无向图是一个有序的二元组<V, E>，记作G，其中V是非空集合，称为顶点集，E是V与V的无序积的多重子集，代表无向边。例如，无向图G可能包含顶点{v1, v2, v3, v4, v5}，以及边{(v1, v1), (v1, v2), (v2, v3), (v2, v3), (v2, v5), (v1, v5), (v4, v5)}。在图形表示中，顶点通常用小圆圈表示，无向边用连线表示。 有向图同样是一个有序的二元组<V, E>，记作D，不同的是E是V与V的笛卡尔积的多重子集，表示有向边。例如，有向图D可能包含顶点{a, b, c, d}，以及边{<a, a>, <a, b>, <a, b>, <a, d>, <c, d>, <d, c>, <c, b>}。有向边在图形表示中用带箭头的线段表示。 图的连通性是衡量图中顶点间相互可达程度的属性。点连通度是指为了使图变得不连通，需要最少删除多少个顶点。边连通度则是指破坏图的连通性至少需要移除多少条边。这种“破坏连通性”的过程意味着要将原本可以互相到达的顶点分割成多个不相交的子集。 图的其他重要概念包括顶点的度数，即一个顶点与其他顶点通过边相连的数量。握手定理表明，在无向图中，所有顶点的度数之和等于边数的两倍。此外，完全图是每对顶点间都有一条边的图，而正则图是所有顶点具有相同度数的图。子图是原图的一个部分，包含原图的一部分顶点和这些顶点间的边；补图是通过在原图中取反边形成的图，即原图中相连的顶点在补图中不再相连，反之亦然。 在图论中，还有许多其他的概念和运算，如路径、回路、树、欧拉路径、哈密顿回路等，它们都是研究图的各种性质和应用的基础。图论广泛应用于计算机科学、网络设计、算法分析、社会网络分析等领域，对于理解和解决问题具有重要意义。