形式陈述
假设要记录四个人之间谁与谁认识。先列出全部人,再列出互相认识的二人组合,就已经确定了一张图;把姓名画在哪里,不改变记录的关系。本页先定义这样的顶点与边,图的表示 理路 图的表示 Graph representation · Adjacency-list and adjacency-matrix representations 依据图的类型与所需操作选择邻接表、邻接矩阵或边集表示的方法。 再讨论怎样把它保存成矩阵或邻接表。改用有向、带权或多重图时,则需要在对象中保留更多信息。
本条中的图专指有限、简单、无向图 。它是二元组 G = ( V , E ) ,其中顶点集 V 是有限集 理路 有限集 Finite set 与某个自然数初始段等势、因而能够在有限步内无遗漏编号的集合。 ,
E ⊆ ( V 2 ) = { { u , v } : u , v ∈ V , u ≠ v } . 这里 ( V 2 ) 是全部二元组合 理路 组合 Combination · k-subset 从有限集合中无序选取固定数量元素所得的子集。 构成的对象族,而不是一个整数;边是其中两个不同顶点组成的无序集合,因此 { u , v } = { v , u } ;同一对顶点之间至多有一条边,不允许顶点连向自己的自环。顶点不必出现在任何边中,这样的顶点称为孤立点。
记 n = | V | 、m = | E | 。本条允许 V = ∅ ;此时 E 也为空。有顶点而无边的图与空顶点图是不同对象。若 { u , v } ∈ E ,称两点相邻;顶点 v 的邻域和度数分别为
N G ( v ) = { u : { u , v } ∈ E } , d G ( v ) = | N G ( v ) | . 图同构表达“连接结构相同”。从 G = ( V , E ) 到 H = ( W , F ) 的同构是双射 理路 双射 Bijective function · One-to-one correspondence 让每个陪域元素恰有一个原像、等价于存在唯一双侧逆函数的映射。 h : V → W ,满足
{ u , v } ∈ E ⟺ { h ( u ) , h ( v ) } ∈ F . 保边与保非边一起保证结构完全对应。重新命名顶点通常得到一个同构 的图;若底层集合不同,它们并不是字面相等的二元组。
直觉
图把一个系统拆成“有哪些对象”和“哪些对象之间有联系”。顶点集负责保存全部对象,包括暂时没有联系的对象;边集只记录允许的成对关系。省略孤立点,会改变顶点数、连通性乃至算法输入,不能只从画出的线条反推整个图。
图画的位置、线段长度和弯曲方式通常不属于图本身。两条画线交叉,不会自动在交点产生新顶点;把顶点挪远,也不会改变它的度数。只有明确增加嵌入、距离或边权之后,这些额外数据才进入问题。
例子与边界
从一张小图读出结构
取
V = { a , b , c , d } , E = { { a , b } , { a , c } , { b , c } , { c , d } } . 前三个顶点构成三角形,d 通过一条边接在 c 上。邻域为 N ( a ) = { b , c } 、N ( b ) = { a , c } 、N ( c ) = { a , b , d } 、N ( d ) = { c } ,所以度数依次为 2 , 2 , 3 , 1 。
按 ( a , b , c , d ) 编号,使用邻接矩阵表示 理路 图的表示 Graph representation · Adjacency-list and adjacency-matrix representations 依据图的类型与所需操作选择邻接表、邻接矩阵或边集表示的方法。 得到
A = ( 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 0 ) . 读第三行时,三个 1 分别位于 a , b , d 对应的列,因此直接还原出 N ( c ) = { a , b , d } ;行和就是 c 的度数 3 。读第一行第四列的 0 ,则知道 a , d 没有直接边,但这没有排除经过 c 的间接连接。
无向性对应矩阵对称,无自环对应对角线为零,简单性对应非对角项只有 0 或 1 。换一种顶点编号会同时置换行和列,而不是改变连接结构。
度数能说明什么
每条边在两个端点各贡献一次度数,故
∑ v ∈ V d ( v ) = 2 m . 这就是握手恒等式 理路 握手引理 Handshaking lemma 有限无向图中所有顶点度数之和等于边数的两倍。 。例子中左边为 2 + 2 + 3 + 1 = 8 ,恰为四条边的两倍。进一步按度数奇偶拆分总和,可知奇度顶点的个数必为偶数;“只有一个奇度顶点”的有限无向图因此不可能存在。
度数序列却不能决定整张图。六顶点环 C 6 与两个互不相连的三角形,都有六个度数为 2 的顶点;前者连通 理路 图连通性 Graph connectivity 用顶点间是否存在路径定义无向图的连通性,并由此划分连通分量。 ,后者有两个非空连通分量,因而不连通;同构保留路径,所以这也证明两图不同构。相同的局部连接数量,不保证相同的全局路径结构。
改变模型,会改变允许的边
有向图 理路 有向图 Directed graph · Digraph 以顶点有序对为弧、能够保留连接方向的有限简单图结构。 把边的方向纳入数据;u → v 和 v → u 可以分别存在。多重图允许同一对端点间有不同边,需要为这些边保留各自身份。自环又会改变“度数如何贡献”的约定,不能继续把度数直接等同于不同邻居的数量。
例如 Cuckoo Hashing 的键—槽图可能有不同键对应同一对候选槽,因而自然得到多重边。这里的简单图提供基础语言,但要分析那种模型,必须保留重复边,不能把边集合去重后继续计数。类似地,给边附非负权重得到的是加权图;权重不是多重边数,零权边在组合连接与某些算子中也可能发挥不同作用。
本条的图也可视为每条超边大小都等于 2 的超图 理路 超图 Hypergraph 边可以连接任意多个顶点而非仅两个顶点的离散结构。 。这一包含关系保留顶点集,因此孤立点并不会在转换时消失。
推论与应用
由于边只能从所有无序顶点对中选择,
0 ≤ m ≤ ( n 2 ) = n ( n − 1 ) 2 . 达到上界的是完全图 K n 。这个上界依赖于简单且无自环;允许多重边后,固定顶点数不再限制总边数。
图中的路与圈 理路 路与圈 Path and cycle in a graph 用相邻顶点序列刻画图中的行走、简单路径与首尾闭合的简单圈。 追踪连接如何连续延伸,连通性 理路 图连通性 Graph connectivity 用顶点间是否存在路径定义无向图的连通性,并由此划分连通分量。 再把顶点划分为互相可达的部分。它们讨论的是边的组合结构,而不是画图时两点在平面上是否靠近。图与这些派生概念应分层定义,以免把“看上去是一整块”代替可达性证明。
表示会影响算法成本。邻接矩阵使用 Θ ( n 2 ) 槽位,在适当的 RAM 模型中可常数时间检查一对顶点是否相邻;邻接表使用 Θ ( n + m ) 空间,可用 Θ ( 1 + d ( v ) ) 时间枚举某个顶点的邻居,包含空邻居表的入口检查。邻接表若未另建索引,检查指定邻居不一定是常数时间。稀疏图和稠密图适合的表示不同,不能把数学对象与某一种存储方式绑定。
参考资料