图的家族图谱：常见图类型巡礼

图的家族图谱：常见图类型巡礼

什么样的地形才值得专门命名？答案是：会在反复出现的那种。完全图、二分图、树、有向无环图……这些名字不是数学家的收藏癖，而是工程与竞赛里反复现身的"制式地形"——认出地形，往往就直接决定了该用哪套战术。本节把常见图类逐一巡礼，说明各自的定义、判别方法与典型出处，并给出对应的构造代码。它是全册的"地形图例"：后面每一次战役开始前，我们都要先看一眼脚下踩的是哪种图。

从约束较少的图说起

最普通的图叫简单图：无自环（边的两端是同一顶点）、无平行边（两顶点间至多一条边）。允许平行边的叫多重图——七桥问题里两岸之间的多座桥就是平行边；再允许自环，就成了伪图。社交平台的关注网络常有平行边吗？通常没有，但电信网络里两机房之间的多条光缆、分子里的双键，都必须用多重图表示。

正则图是所有顶点度数相同的图。每个顶点度数都达到顶点数减一的极端情形，就是完全图：任意两顶点之间都有边。完全图的边数增长极快——顶点数翻倍，边数近似翻两番，这种"稠密"在存储（第 2 章的邻接矩阵）与着色（第 8 章）里都会带来麻烦。

与之相对的极端是稀疏图：边数与顶点数同阶。现实中的大网络（道路、社交、网页链接）几乎都是稀疏的，这也是邻接表成为工业标配的原因。

二分图：阵营分明的战场

二分图的顶点能划分成两个阵营，所有边都横跨阵营、阵营内部无边。它是最重要的图类之一，因为大量实际问题天然两方对垒：任务与工人、学生与课程、用户与商品、左括号与右括号。

二分图有个漂亮的判别定理：图是二分图，当且仅当它不含奇回路——不存在边数为奇数的环。直觉来自"交替染色"：从一个顶点出发把它染成阵营甲，邻居必然属于阵营乙，邻居的邻居又回到甲……若途中某个顶点被要求同时加入两个阵营，矛盾恰好发生在奇回路上。这个"交替染色"过程本身就是算法，第 3 章的广度优先搜索会让它落地。

二分图还是"图论问题变简单"的头号福地：第 7 章的匹配问题在一般图上很曲折，在二分图上却有多项式算法；第 8 章的着色在二分图上退化为"判断是否二分"。

树与森林：最精简的连通

树是连通且无环的图；若干棵互不相邻的树构成森林。树拥有一个近乎完美的性质：边数恰为顶点数减一，而且"连通""无环""边数等于顶点数减一"三者两两可推。树还是"保持连通的最省钱结构"——每多一条边都会引入环，每少一条边都会断开。第 6 章的最小生成树战役打的正是这个主意：在带权图里挑出总造价最小的那棵树。

有向世界里的明星是 DAG（有向无环图）：边带方向、不许出现有向环。任务依赖、课程先修、表达式求值、版本提交历史，全是 DAG。它最著名的性质是可以拓扑排序——把顶点排成线性序列，使所有边从先指向后。第 6 章第 3 节专讲这项调度技术。给 DAG 的边加上"容量"，就得到第 7 章网络流的舞台（流网络还要求单源单汇）。

加权图与带权家族

前面所有图类都可以叠加权重。加权完全图的典型出场地是"任意两地皆有直达线路"的运价表；加权 DAG 常出现在任务调度里，权重代表工期——求关键路径（最长路）就是项目管理里的要害问题。第 5 章最短路径默认在加权图上作战，负权边在那里会掀起一场风波。

用代码点验编制

下面把家族成员逐个构造出来，并现场演示二分图的交替染色判定。

import networkx as nx
from itertools import combinations

# 完全图：任意两点相连
K5 = nx.complete_graph(5)
print("K5 边数 =", K5.number_of_edges(), "（等于从5个点里选2点的组合数）")

# 完全二分图：两阵营内部无边，跨阵营全连
B = nx.complete_bipartite_graph(3, 4)
print("K(3,4) 边数 =", B.number_of_edges(), " 顶点数 =", B.number_of_nodes())

# 树：取完全图的一棵生成树
T = nx.minimum_spanning_tree(K5)   # 权全为1时任意生成树都行
print("树：边数 =", T.number_of_edges(), " 顶点数 =", T.number_of_nodes(), "→ 边数=顶点数-1 成立")

# DAG：表达"先修课"约束
dag = nx.DiGraph([("离散数学","图论"), ("Python基础","图论"),
                  ("图论","算法设计"), ("线性代数","机器学习")])
print("是DAG吗:", nx.is_directed_acyclic_graph(dag))
​

接着是交替染色判定器，它同时回答"是不是二分图"和"阵营怎么分"：

def bipartition(G):
    """交替染色判定二分图；返回 (是否二分, 阵营划分)"""
    color = {}
    for start in G.nodes:                      # 处理非连通：每个分量都染一遍
        if start in color:
            continue
        color[start] = 0
        queue = [start]
        while queue:
            u = queue.pop(0)
            for v in G[u]:
                if v not in color:             # 邻居染上相反颜色
                    color[v] = 1 - color[u]
                    queue.append(v)
                elif color[v] == color[u]:     # 同色相邻 → 奇回路现身
                    return False, None
    side0 = [v for v, c in color.items() if c == 0]
    side1 = [v for v, c in color.items() if c == 1]
    return True, (side0, side1)

G1 = nx.Graph([("任务A","工人甲"), ("任务B","工人甲"), ("任务B","工人乙"), ("任务C","工人乙")])
ok, parts = bipartition(G1)
print(ok, parts)

# 含三角形（奇回路）的图必然失败
G2 = nx.Graph([(1,2),(2,3),(3,1)])
print(bipartition(G2))    # False, None —— 与定理"二分当且仅当无奇回路"吻合
​

注意判定器里外层的 for 循环：图未必连通，每个连通分量都要单独染色（连通分量的正式讨论见第 4 章）。染色结果的两阵营，正是第 7 章二分匹配问题需要的输入格式。

⚠️ 常见坑：把"树"理解成"看起来像树的图"。树只看结构（连通无环），与画出来的形状无关——一条链是树，一颗星形也是树；反过来，画成放射状的图若藏着环，就不是树。

💡 关键直觉：拿到问题先归图类，等于医生先看科室挂号。着色难题在一般图上，到了二分图就变成染色判定；匹配难题在一般图上，到了二分图就有成熟解法。识别地形，常常就解决了问题的一半。

家族图谱点验完毕。下一章远征队要解决行军的第一件实务：这么多顶点和边，如何存进计算机、才能让后续的算法跑得动。