Question

Graph

Graph 中文翻做“图”。此处谈及的“图”并不是指图片或者图形。“图”是一种用来记录关联、关係的东西。

一张图由数个点（vertex）以及数条边（edge）所构成。点与点之间，得以边相连接，表示这两点有关联、关係。

点的大小形状和线的粗细长短是无所谓的，我们只在乎它们如何连接。只要连接的关係对了，要怎麽画都行，简约、雅观、平易近人即可！

两点之间也可以有很多条边，甚至有自己连到自己的边。两点之间有很多条边，代表这两点有很多项关联。一个点有自己连到自己的边，表示自己和自己有项关联。

Isomorphism / Isomorphic

Isomorphism 中文译作“同构”，Isomorphic 中文译作“同构的”。如果两张图的连接方式一模一样时，则称作“同构”。

图上的边可以是直的，也可以是弯弯曲曲的，也可以是交错的。不论边的形状如何，都不会改变点与点之间的关联、关係，终究都会是同构的图。

图上的点可以任意移动位置。不论点的位置如何，都不会改变点与点之间的关联、关係，终究都会是同构的图。

同构的图拥有相同的资讯，所以不管选择哪一张图都是可以的，只要清楚易懂就可以了！

Directed Graph（Digraph）

边甚至可以拥有方向性，用来表示两点间的关係是单向的，并非双向的。无向边代表双向关係，有向边代表单向关係。

一张图若都是没有方向性的边，称作“无向图”；一张图若都是有方向性的边，则称作“有向图”。如果图上有一些边是单向的，有一些边是双向的，那我就不知道那该叫做什麽图了。

替点和边加上权重

图上的点可以拥有权重，可做其他用途。

图上的边可以拥有权重，可做其他用途。

替点和边取名字、代号

点和边上面可以取名字、代号，方便辨认。名字、代号可以写在点和边的旁边，也可以写在点的裡面、边的上面，只要能表达清楚就好。

名字可以随便取，简单明瞭就好。书上通常是用英文字母及数字居多。

Graph 资料结构

Edge List

来谈谈如何利用程式语言来储存一张图吧！

最简单的方式，就是用个阵列，记录所有点与点之间的边。这种方式相当直观，也非常节省空间，但是却不适合用于计算（请各位读过图论其他主题后，再来思考看看）。所以这裡要介绍其他类型的方法。

储存一张图的方式有许多种，这裡介绍其中两种最常见的方法：adjacency matrix、adjacency lists。adjacency 为“相邻”之意，以边相连接的两个点，则称这两个点“相邻”。

Adjacency Matrix

把一张图上的点依序标示编号，然后建立一个方阵，来记录连接资讯。方阵中的每一个元素都代表著某两点的连接资讯。例如元素(0,1) 记录著第 0 点到第 1 点的连接资讯、元素(4, 2) 记录著第 4 点到第 2 点的连接资讯。如此一来，任意两个点之间的资讯，都有对应的地方可用于记录，纤悉无遗。

连接资讯可以是边的数目，也可以是边的权重，也可以储存其他的资讯。

值得一提的是，adjacency matrix 可以用来记录边的权重。但是它却没办法记录点的权重，它也没办法同时记录点和边的权重。不过，要记录点的权重，其实只要另外开一条阵列就行了，也不是什麽难事。

另外，当两点之间的边超过一条的时候，adjacency matrix 没办法记录权重，因为 adjacency matrix 的一个格子只能存入一个数字，没办法同时间存入多个数字。我们可以修改 adjacency matrix 的构造以存入更多数字，只是这不在讨论范围之内，各位可自行研究。

程式码可以写成这样：

Adjacency Lists

把一张图上的点依序标示编号。每一个点，后方串连所有相邻的点。例如第 4 列之中所列的数字，即是与第 4 点相邻的点。

第一种，是古板的实作方式，自行实作 list：

第二种，是轻鬆的实作方式，利用程式语言内建的 list 或 vector：

第三种，是简约的实作方式，适用于边数不多时：

第四种，是奇妙的实作方式，把边依序放入阵列：

如果还要记录边的权重，就变成这样：

如果还要记录点的权重，那就另外再开一条阵列吧。

Graph Traversal

Graph Traversal

给你一张图，要怎麽读出它的资讯呢？

用人眼来观察一张图，很快的就能看出点和线，一点一点釐清关係。要是一张图能够画得漂亮一点，上个鲜明的颜色，那就更好了。

电脑则不然。要以电脑来读取一张图的资讯（这资讯想必会以图的资料结构来妥善储存），唯一的方法就是透过程式语言，以及良好的演算法囉！

Traversal 中文称作“遍历”。图的遍历，也就是指通盘地读取图的资讯：决定好从哪裡开始读，依照什麽顺序读，要读到哪裡为止。详细地设计好流程，始能通盘地读取图的资讯；如果设计得漂亮，在解决图的问题时，还可以一边读取图的资讯，一边顺手解决问题呢！

利用最简单的资料结构 queue 和 stack，就能制造不同的遍历顺序，得到两种遍历演算法：Breadth-first Search 和 Depth-first Search。这两个演算法充分了利用程式语言的特性，简约而美丽，成为资讯领域不可不知的演算法。

Graph Traversal: Breadth-first Search

Breadth-first Search（BFS）

（依照编号顺序）不断找出尚未遍历的点当作起点，进行下述行为：
　一、把起点放入 queue。
　二、重複下述两步骤，直到 queue 裡面没有东西为止：
　　甲、从 queue 当中取出一点。
　　乙、找出跟此点相邻的点，并且尚未遍历的点，
　　　　通通（依照编号顺序）放入 queue。

教科书都有一步一步的示意图，这裡不再重画，只做额外补充。

运用 BFS 遍历整张图，最后得到许多棵树。单一的树称作 BFS Tree，所有的树称作 BFS Forest。

不同的起点，形成不同的 BFS Forest。我们习惯按照编号顺序选择下一个要拜访的点，得到唯一一种 BFS Forest。

遍历顺序示意图：每个点进入与离开 queue 的时刻

每个点进入 queue 的时刻以左上深色数字表示，每个点离开 queue 的时刻以右下浅色数字表示。每个点都会进入 queue 一次、离开 queue 一次，不会再有第二次。

遍历顺序示意图：每个点离开 queue 的时刻

只观察离开 queue 的时刻，可以发现 BFS 优先走遍距离起点最近之处，优先让 BFS Tree 变得宽广，因而得名 Breadth-first Search。这个遍历顺序能够解决许多图论问题！

时间複杂度

使用的资料结构为 adjacency matrix 的话，可以以 O(V^2) 时间遍历整张图；使用 adjacency lists 的话，可以以 O(V+E) 时间遍历整张图。V 是图上的点数，E 是图上的边数。

程式码（adjacency matrix）

Graph Traversal: Depth-first Search

Depth-first Search（DFS）

DFS 与 BFS 大同小异，只是把 queue 换成了 stack 而已。

遍历顺序示意图：每个点进入与离开 stack 的时刻

每个点进入 stack 的时刻以左上深色数字表示，每个点离开 stack 的时刻以右下浅色数字表示。每个点都会进入 stack 一次、离开 stack 一次，不会再有第二次。

遍历顺序示意图：每个点离开 stack 的时刻

只观察离开 stack 的时刻，可以发现 DFS 优先走遍距离起点最远之处，优先让 DFS Tree 变得深远，因而得名 Depth-first Search。这个遍历顺序能够解决许多图论问题！

递迴版本程式码（adjacency matrix）

DFS 的程式码也可以写成递迴形式。程式语言中的递迴，其实就是利用 stack 来实作的。

Graph Property

先看个图片

图片中省略了点的编号。

degree

一个点的“度”：一个点的边数量。

有向图，细分成入边数量 in-degree、出边数量 out-degree。

neighbor

一个点的“邻居”：一个点连往的点。可能有许多个、零个。

无向图，邻居数量是边数量。有向图，邻居数量是出边数量。

顺便补充几个常见形容词。

adjacent：相邻、邻接。只走一步，可以抵达。
connected：相连、连通。不限步数，可以抵达。

distance

两个点的“距离”：从起点走到终点的边数量，数量必须最低。

如果两点之间不连通，距离是无限大。约定成俗。

指定起点，实施 Breadth-first Search，就可以算出起点走到图上各点的距离。利用这种方式，可以算出两点之间的距离。大家可以试试看！

额外补充一下。当数量必须最低，改成了数量必须最高，则无法透过遍历演算法求得答案，只能透过 backtracking 穷举所有路线，一一判断答案。数量必须最高，已被证明是 NP-complete 问题，目前没有（以后大概也不会有）快速的演算法。

Graph Manipulation

Intersection Graph

图用来表达两两之间的关係。例如一群人，我们可以建立“朋友关係”的图，两个人是朋友就连一条边，两个人不是朋友就没有边。只要是两两之间的关係，就得以转化成图，运用图论知识来分析问题。

其中有个值得一提的关係是“交集关係”，是联集交集的那个交集。两个东西有交集就连一条边（交集不是空集合）、没交集就没有边（交集是空集合），最后得到的图叫做“交集图”。

例如一堆线段，把互相接触的线段，表示成图：

例如一堆集合，把有交集的集合，表示成图：

比较特别的交集图，数学家会特地取名。例如一堆硬币，平铺在桌上，把互相接触的硬币，表示成图，称作 Coin Graph。数学家发现硬币图和平面图两者完全等价，每一种平面图都可以利用硬币接触兜出来。

例如行程表，把撞期的行程，表示成图，称作 Interval Graph，有著很特别的数学性质。

例如一张图论的图，把共用端点的边，表示成图，就是先前提到的 Line Graph。

为什麽数学家特别重视交集图呢？我也不知道。

很多人把交集图看做是一个物品。但是交集图其实是一种变换的概念，可以看做是一个函数。

Dependency Graph【尚无正式名称】

除了“交集关係”之外，数学家也很重视“依赖关係”。把各个东西的仰赖对象表示成图，最后得到的图叫做“依赖图”。

例如一堆不等式，把变数大小关係，表示成图：

比较特别的依赖图，数学家会特地取名。例如专案管理领域，把工作先后次序，表示成图，称作“ Activity Network ”。

例如 2-SAT 问题，把各个 clause 裡面的两个变数的取捨关係，表示成图，称作“ Implication Graph ”。

交集图是无向图、依赖图是有向图，刚好一对。

Subgraph / Supergraph

一张图，删除一些点、一些边，得到的图称作“子图”。

原图（没有删除）、空图（完全删除），也算是“子图”。

一张图，增加一些点、一些边，得到的图称作“父图”。

原图（没有增加）也算是“父图”。

subgraph 和 supergraph 是相对的。如果 A 是 B 的子图，那麽 B 就是 A 的父图。我们习惯只讲子图，讲一个就等于两个都讲了。

Induced Subgraph / Induced Supergraph

一张图，保留一些点、以及这些点之间的所有边，得到的图称作“导出子图”。

一张图，增加一些点、一些边，但是不在原本的点之间增加边，使得原本的图是导出子图，得到的图称作“导出父图”。

induced subgraph 和 induced supergraph 是相对的。如果 A 是 B 的导出子图，那麽 B 就是 A 的导出父图。我们习惯只讲导出子图，讲一个就等于两个都讲了。

Minor / Subdivision

一张图，收缩一些边、合併一些点，得到的图称作 minor。

收缩的边，有人视情况删除，也有人视情况不删除、而变成连向自己的边。

一张图，在边上植入点，得到的图称作 subdivision。

minor 和 subdivision 是相对的。一般只讨论 minor。

ICPC 4023

Oriented Graph / Underlying Graph

一张无向图，无向边改成有向边，称做“定向图”。

一张有向图，有向边改成无向边，称作“底图”。

定向图和底图是相对的。一般只讨论定向图。

Complement Graph（Complement）

一张图，两点之间没边变有边、有边变没边，称作“补图”。

原图暨补图的所有边，合起来是完全图。

朋友变仇人、有关变无关，整个相反颠倒，就是补图的用处。

Reverse Graph（Transpose）

一张有向图，边的方向颠倒，称作“反向图”。

主动变被动、前进变后退，整个相反颠倒，就是反向图的用处。

Line Graph

一张图当中，观察边与边关係，相邻的边表示成一张图，称作“线图”。

UVa 10988 11175

Dual Graph

一张平面图当中，观察面与面关係，共边的面表示成一张图，称作“对偶图”。详情请参考“ Planar Graph ”。

Hypergraph

Hypergraph

“图”是谈两个东西之间的关係，“超图”则是谈多个东西之间的关係，例如三个东西之间的关係。

超图的资料结构，不适合採用 adjacency matrix，因为矩阵必须变成多个维度，浪费记忆体空间。比较好的方式是採用 incidence matrix。

一般的图就很够用了，通常不会用到超图。