图论概览

摘要

是一个二元组

其中 称为顶点集, 称为边集,它们亦可写成

的元素是一个二元组数对,用 表示,其中


分类

图含有多个分类的标签:

  1. 有向 / 无向(Directed/Undirected)
  2. 有环 / 无环(Ring/Acyclic)
  3. 连通 / 非连通(Unicom/Non-Unicom)
  4. 简单 / 多重(Simple/Multiple)
  5. 加权(Weighted)

常见图结构:

  1. 有向无环图(Directed Acyclic Graph,DAG)
  2. 树(Tree)
  3. 简单图(Simple Graph,不包含重边和自环)
  4. 多重图(Multi-Graph,可能包含重边和自环)
  5. 加权图(Weighted Graph,通常指边带权)

图的存储

图的存储大体分邻接矩阵,邻接表,链式前向星三种。

方式 存储 空间复杂度 边的存在性判断 边的遍历
邻接矩阵 二维数组
邻接表 vector 或二维数组
链式前向星 结构体

玄学的度

  • 无向图中,定义 表示结点的,则 ,

  • 有向图的结点分入度( )和出度( ): ,

度序列 -Sequence Degree

度序列 - 形式化定义

  • 对于 ,则称非负整数序列 为图 G 的度序列.
  • 简单图的度序列称为图序列.

前置定理

推论 1:任何图中,奇度点的个数为偶数。

推论 2:非负整数序列 是某个图的度序列, 当且仅当 是偶数。

Erdos-Gallai 定理

序列 图序列当且仅当:

  1. 是度序列(见前置定理 - 推论 2
  2. .

序列可图性

可图(化)- 定义

一个序列是某个无向图的度序列,则该序列是可图的,也称该序列可图化。进一步,一个序列是某个无向图的图序列,称该序列可简单图化

Havel-Hakimi 定理

对于非递增序列

可简单图化,当且仅当:

可简单图化。

分析 & 简略的感性证明

先分析 的结构:

  • 一共有 个元素,比 少了一个
  • 个数都减了 1,后面有 个数不变。

从序列 中产生 ,相当于将 对应的无向图中度为 的点删除(并且把与这个点连接的边也删掉),这样相当于删除了元素 ,又让其他的 个元素的度分别减 1(之所以是 ~ 的度减 1,因为这是构造出来的).

如果这么理解的话,那么 可简单图化,则把 补回去,就是 对应的无向图——显然也是简单图。

定理的使用

本文来自 YY-Captain 的 CSDN 博客 ,全文地址
判断序列 是否可图。
按照定理一个个删点;如果 出现了负度,则 不可简单图

  1. 删除首元素 6,将后面的 6 个元素减一,得到:
  2. 删除首元素 4,将后面的 4 个元素减一,得到:
  3. 删除首元素 2,将后面的 2 个元素减一,得到:
  4. 重新排序:
  5. 删除首元素 1,将后面的 1 个元素减一,得到:

则最后得到的是非负序列,所以序列 可简单图化。

判断序列 是否可图。

  1. 删除首元素 7,将后面的 7 个元素减一,得到:
  2. 删除首元素 6,将后面的 6 个元素减一,得到:

最后得到的是存在负数的序列,所以序列 不可简单图化!

图的遍历

BFS-CF1037D

判断序列是否为 BFS 遍历

同一深度的点在序列中应是连续的,且这连续的子段用到的数的排列顺序等价

直接模拟即可

DFS 生成树

HDU5215

先 DFS 搜索,通过返祖边确定简单环,通过深度差确定环的奇偶性。

对于相交的环,因为只用判断奇偶性,所以分别考虑两者即可

任意两条返祖边相交,都会产生偶环

CF295E

欧拉回路

欧拉回路作为图的子图,满足:(充要条件)

  • 无向图:每个点的度数为偶数
  • 有向图:每个点的入度 = 出度

链表 +DFS 求欧拉回路

图的生成树

定义:图的生成树是它的一颗含有其所有顶点无环连通子图。

最小生成树 -MST

加权图 G 中,边权和最小的生成树。

Kruskal 算法

利用贪心的思想,每次选择权值最小的(且两个端点没有同时在 MST 中,否则就不是树了)边,加入到 MST 的边集中。排序实现贪心,并查集 实现验证可用性。

复杂度

Prim 算法

仍然是贪心,不过改成每次往 MST 中加点(距离 MST 最小的那个点)

堆实现贪心,复杂度

斐波那契堆实现贪心,复杂度

最小瓶颈生成树

加权图 G 中,最大边权值最小的生成树。最小生成树是最小瓶颈生成树,因此可通过求 MST 求得最小瓶颈生成树。或着二分边权,判定图是否连通:

  • 对于二分的边权 ,如果图连通,则继续考虑 的边
  • 否则,把连通的分量缩点,考虑剩下的 的边
  • 期望复杂度 .

生成树计数

Cayley 定理:完全图的生成树个数为

如果每个点的度数为 ,那么生成树个数为

每个连通块大小为 ,那么添加一些边将这些连通块连通的生成树个数为

最短路

最短路算法 ·ShortestPath

特殊子图

前置概念

  1. 偏心距:
  2. 直径:
  3. 半径:
  4. 中心:半径对应的
  5. 绝对中心:可以是边上的点(把边分成两部分)

最小直径生成树

绝对中心的最短路生成树

如何证明?

对绝对中心来说,一棵树 有直径为半径的两倍。如果最小直径生成树 不包含绝对中心,那么取 的绝对中心 ,显然矛盾。

拓扑排序

每次去掉图中入度为 0 的点,时间复杂度 O(n+m)。

如果最后不为空集那么这个图不为 DAG,每个点入度不为 0,即每个点可以选择一个前趋,沿着前趋走根据抽屉原理一定能找到相同点,也就是一个环。

字典序最小的拓扑序

  • 堆拓扑即可。

拓扑序变种

HNOI2015 菜肴制作

连通分量

Tarjan 之有向图 SCC
Tarjan 算法之无向图


  转载请注明: Sshwy's Blog 图论概览

 上一篇
Vbox 代理全局 Vbox 代理全局
在 Deepin 下使用 shadowsocks?你会发现一个叫做 aec-128-gcm 的加密方法是不被支持的 于是,搭建 Vbox-Win7 虚拟机. 配置好 ss 后,在网络 -NAT 的高级选项中的端口转发: 配置一下主机域名
2018.10.04
下一篇 
矩阵加速 矩阵加速
简介 矩阵加速,用于计算数列的第 n 项(当 n 的数值过大,线性算法超时时)。 这里的数列限指 K 阶常系数线性递推式 原理矩阵快速幂 大致分三步: 将原式化为矩阵 矩阵乘法分离,建立矩阵递推关系 找到起始项,建立常数矩阵幂关系(可用
2018.10.03
  目录