顶点（图论）
dǐng diǎn (tú lùn)
在图论中,顶点是图中一个基本的节点或点,通过边与其他顶点相连。
Definition
在图中，顶点（复数：vertices）就是其中的一个点；顶点代表对象或位置，顶点之间的边代表连接关系，顶点是图论中的"名词"，而边是"动词"。严格地说，图 $G = (V, E)$ 中的一个顶点 $v$ 是顶点集 $V$ 中的一个元素；度 $\deg(v)$ 是与 $v$ 相关联的边的数目（在有向图中，入度和出度分别计数），握手引理指出所有顶点的度数之和等于 $2|E|$。在谱图理论中，邻接矩阵 $A$ 满足：若 $\{i,j\}$ 是一条边，则 $A_{ij} = 1$；它的特征值（$G$ 的谱）编码了图的结构性质，拉普拉斯矩阵 $L = D - A$ 的第二小特征值是代数连通度，用来衡量图的连通程度。
Example
在一张地图图中，每个城市都是一个顶点；在一个社交网络中，每个人都是一个顶点。在一个顶点为 $\{A,B,C,D\}$、边为 $\{AB,AC,BC,BD\}$ 的图中：$\deg(A)=2$，$\deg(B)=3$，$\deg(C)=2$，$\deg(D)=1$，总和为 $8 = 2 \times 4$ 条边。对于完全图 $K_n$，每个顶点的度数都是 $n-1$，它的邻接矩阵的特征值为 $n-1$（一次）和 $-1$（$n-1$ 次），得到代数连通度 $n$，反映出最大的连通程度。
Key Insight
顶点是被研究的对象，握手引理蕴含着度数为奇数的顶点个数总是偶数，这一奇偶性约束被用于许多证明中。费德勒特征向量（对应拉普拉斯矩阵第二小特征值的特征向量）提供了一种最优的图划分方式，被用于谱聚类和图形绘制算法。