图的基本语言:顶点、边、度、路、圈、连通
图论的全部词汇都建立在两样东西上:一组 顶点 (vertex) 与一组连接顶点的 边 (edge)。本页把最常用的一批基础概念,全部落到同一张能换样本的图上——切换下面的「透镜」,同一张图就被分别按度数、连通分支、割点与桥、二部性重新点亮。先把这套语言说顺,后面所有定理才有词可讲。
一个顶点的 度 (degree) = 与它相连的边数。一条 walk 是顶点边交替的序列;不重复顶点的 walk 叫 path(路);首尾相接的 path 叫 cycle(圈)。两点间存在路即连通;图按连通关系裂成若干连通分支 (connected component)。无圈的连通图是树 (tree),无圈图(可不连通)是森林 (forest)。
握手引理 (handshake lemma): ——每条边给它两个端点各贡献 1 度,所以所有度数之和恰好是边数的两倍。一个直接推论:奇数度的顶点个数必为偶数(度数总和是偶数,奇数项不能凑出奇数个)。在「度数」透镜里,奇度顶点被标橙,数一数总是偶数个。
割点 (cut vertex) 与桥 (bridge): 删掉它就会让连通分支变多的顶点 / 边。它们是图的「咽喉」——网络里的单点故障、关节路由都对应于此。判定方式很直接:试删它,看分支数是否增加(本页用的就是这个朴素判据;大图上则用 Tarjan 的 low-link 一次 DFS 求出)。
二部图 (bipartite): 顶点能分成两组、使每条边都跨组。等价刻画极漂亮:一张图是二部图 ⟺ 它不含奇圈。「二部判定」透镜用 BFS 交替染两色,一旦遇到「同色相邻」就说明撞上了奇圈,染色失败——切到「含奇圈」样本看它如何卡住。完全图 K_n、完全二部图 K_{m,n}、多重图 multigraph(允许重边 / 自环)都是在这套语言上再加约束或放宽得到的。