顶点、边与度：远征地图的基本要素
顶点、边与度：远征地图的基本要素
「度」是图论里出场率最高的行话——七桥问题翻来覆去用的就是它。上一节我们靠历史直觉拼出了这个概念，本节把它连同整套地图语言正式立规：图如何形式化定义，边如何带方向与权重，度如何计算，通路与回路如何描述行军轨迹，子图如何切割战场。这些词以后每一节都要用，相当于远征队的制式术语手册。学完本节，读任何图论文献的前两页都不应再有生词。
形式化：从口语到符号
一个图记作 G 等于顶点集与边集构成的二元组。顶点集是研究对象的集合，边集是对象之间关系的集合。每条边连接一对顶点，称这对顶点互为邻居。
按边是否带方向，分成两类：
- 无向图：边没有箭头，关系对称。合作关系、双向通行的道路，都属于这类。
- 有向图：边从尾指向头，关系单向。网页超链接、任务先后依赖、食物链中的捕食关系，都必须用有向边刻画。
有向图里，度进一步细分为入度（指向该顶点的边数）与出度（从该顶点发出的边数），两者之和仍是该顶点的总度数。
按边是否带数值，又分无权图与加权图。权重可以表示距离、造价、耗时、容量、亲密度——图论本身不关心含义，算法只把它当数运算。第 5 章起权重将成为主角。
几个描述行军轨迹的词必须分清：
- 通路：沿边首尾相接的顶点序列。允许重复经过顶点的叫漫游，顶点不重复的叫路径。
- 回路：起点与终点相同的通路。七桥问题要求的正是"经过每条边恰一次的回路"。
- 连通：无向图中任意两顶点之间存在通路。有向图里"互相可达"的版本叫强连通，第 4 章专门处理。
- 子图：取原图部分顶点与部分边（保持端点一致）拼成的图。战役分析里"只看这片区域"就是取子图。
度与握手定理
度刻画顶点的连接活跃度。它看似平凡，却支撑着全册第一条普适定律：
握手定理：无向图中所有顶点的度数之和等于边数的两倍。
道理与七桥论证同源：每条边有两个端点，为每个端点各贡献一次度。换个角度想，聚会上每次握手都涉及两个人，把每个人的握手次数加总，必然是握手事件总数的两倍——定理因此得名。
推论同样有用：度数之和必为偶数，所以奇度顶点的个数一定是偶数。你不可能构造出恰有奇数个奇度顶点的图——数据录入出错时，这是最先该查的不变量。
用代码清点要素
下面这段代码构造一个带权有向图，全面读取它的要素，顺便验证握手定理的"有向版"——所有顶点入度之和等于出度之和，都等于边数。
import networkx as nx # 城际交通：有向、带通行耗时 G = nx.DiGraph() G.add_weighted_edges_from([ ("甲", "乙", 2.5), ("乙", "丙", 1.2), ("甲", "丙", 4.0), ("丙", "丁", 3.3), ("乙", "丁", 5.1), ("丁", "甲", 7.8), ]) print("顶点:", list(G.nodes)) print("边数:", G.number_of_edges()) for v in G.nodes: print(f"{v}: 出度={G.out_degree(v)} 入度={G.in_degree(v)} 度={G.degree(v)}") print(f" 邻居与权重: {dict(G[v])}") # 有向版握手定理：入度和 = 出度和 = 边数 in_sum = sum(d for _, d in G.in_degree()) out_sum = sum(d for _, d in G.out_degree()) print("入度总和 =", in_sum, " 出度总和 =", out_sum, " 边数 =", G.number_of_edges())
再写一个"地图体检"函数，把本节的概念串成可复用的检查器——以后拿到任何图数据，先跑它再干活。
def graph_checkup(G): """对无向图做要素体检：返回度分布、奇度顶点、连通性、悬挂点""" degrees = dict(G.degree()) odd = [v for v, d in degrees.items() if d % 2 == 1] return { "边数": G.number_of_edges(), "度数和": sum(degrees.values()), "握手定理": "通过" if sum(degrees.values()) == 2 * G.number_of_edges() else "失败(数据有误)", "奇度顶点数": len(odd), # 必为偶数 "连通": nx.is_connected(G) if not G.is_directed() else nx.is_strongly_connected(G), "悬挂点(度为1)": [v for v, d in degrees.items() if d == 1], } H = nx.Graph([("哨所1","哨所2"), ("哨所2","哨所3"), ("哨所3","哨所1"), ("哨所3","哨所4")]) for k, v in graph_checkup(H).items(): print(k, "→", v)
体检器的第一个客户就暴露了问题：奇度顶点个数若不是偶数，说明边表录入必然出错；悬挂点（度为一的顶点）则提示这条边可能是"断头路"，在连通性分析里要特别对待。把这种"不变量校验"养成习惯，收益贯穿全册——第 2 章检查邻接表的度数是否与边表吻合、第 4 章核对分量划分是否覆盖全部顶点、第 6 章验证生成树的边数恰为顶点数减一，本质上都是在用同一个思路：结构自带守恒律，违背即数据有诈。数据工程里这招尤其值钱，图数据的脏往往不是缺值，而是"悄悄多了一条边"——表面无害，却能让整张图的分量数、奇度配对全部走样，而握手定理就是最早拉响警报的那只哨兵。
术语的三层用途
这些定义不是背给考试听的。第一层用途是通信：后文的"Dijkstra 要求非负权""Kruskal 依赖边的排序与并查集"，离开本节词汇就无法表述。第二层用途是建模：拿到实际问题先问——对象是什么（顶点）、关系是什么（边）、关系是否对称（向）、是否有强弱（权）。第三层用途是约束推导：像七桥那样，从定义直接推出存在性结论。第 9 章证明欧拉回路判定、第 7 章推导最大流最小割定理时，用的正是这套语言。
💡 关键直觉：建模时"顶点放什么"是最重要的决定。七桥问题把陆地设为顶点、桥设为边，问题可解；反过来把桥设为顶点（边代表桥的衔接），会得到"线图"视角——两种建模都合法，但难度天差地别。多备几种视角，是图论建模的基本功。
术语手册已经备齐，远征队即将巡视图的整个家族：哪些地形有专名、各自适合什么战术，是下一节的内容。