离散数学图论
10.1 图与模型
这里讨论的都是有限图（finite graph）。
本文适用于bupt的离散数学，或了解学习图论相关知识。
在代码框中的内容是我认为不太重要的内容。但如果能记住就更好。
图可以被看作一个群，记号为G=(V, E)。图的顶点（vertex）之间的二元关系可以看成是E中的元素，也就是图里的边（edge）。图的边是否有序则分为有序图和无序图。
在无序图中，简单图（simple graph）被定义作：没有两条边是连着相同顶点的。而如果有这样的边（称为multiple edge），那么这个图就应被称为multigraph。图里的环（loop）即为字面意义，指向自身。在这里定义pseudograph：允许环和多重边存在的图即为pseudograph。
在有向图中，简单有向图也和上述定义相差无几，即没有同终点和起点的弧。但值得注意的是，在两个vertices而他们相互指向的时候，这也是一个简单图。此处的多重图称为directed multigraph。当有向图里的一对顶点u,v的重边数为m，则称(u,v)的multiplicity为m。下面有表格帮助记忆，但这些概念理解起来不必麻烦去记，较好理解。
10.2 特殊的图及其相关定义
在无向图中，我们称两个顶点是adjacent/neighbors当且仅当是被边e连起来的。这条边e被称为incident with the vertices u and v。
引入一个记号：N（v），其中v是某个顶点，这表示v的所有neighbors的总集合，称为v的neighborhood。对此有一个显而易见的结论，N(A) = ⋃v∈A N(v)，即对图的子图A，求它的neighborhood就是子图所有顶点的neighborhood的并集。
定义无序图的度（degree）为顶点的相连边的数目，记号为deg（v）。度=0的顶点称isolated，度=1的顶点称pendant。
在无序图中有一个关于度的和的定理，即任何无序图的所有顶点的度之和=2m，其中m为边数，这称为handshaking theorem（定理名称不用记，但十分形象）。
另一个在无序图中的定理：度为奇数的顶点必有偶数个。这是上一个定理的推论。
有序图稍比上述介绍的定义复杂。当（u，v）是一条有向图的边（注意方向），我们称u是adjacent to v的，而v是adjacent from u的。u被称为initial vertex，v被称为terminal/end vertex。
degree在有序图中则被分得更细，分为in-degree和out-degree。in-degree为顶点被指向的次数，记号为 deg−(v) （-号在deg右上角），而out-degree是顶点指出的方向数，记号为deg+（v）。同时还有一个定理，有向图的入度之和与出度之和相等，且等于边的总数|E|。
下面介绍特殊图：complete graph：完全两两顶点连接的图，记号为Kn（n为下标），n是顶点数。不是完全图的简单图则称为noncomplete。
cycle：如字面意义。记号为Cn。
wheels：即Cn的中间加上一个中心点，且这个中心点和四角相连。记号为Wn，且切记，Wn是由Cn和中心点构成的，共n+1个vertices。
n-cubes：即n维超立方体，记号为Qn。通常我们只用前三个，且这个立方体具备格雷码特性。如图所示（切记Q1是一根线）
一个图被称为bipartite（可二分的）当且仅当顶点集合V可被分为两个不相交的V1、V2集合，即两个集合内部的元素之间没有边，这一二分操作是完全分开的，即对整个图操作而非部分。值得注意的是，V1、V2之间不一定全都有关系，只要满足可以分开就是bipartite的。我们称（V1，V2）是V的bipartition。
一个图是bipartite当且仅当G能被小于等于两种颜色着色。这一方法能快速对G进行二分。
完全二分图（complete bipartite graph）可以看作bipartition模型在图中的直接样子，记号为Km,n（m，n是下标），具体形式如图，不细述。
定义matching的概念：matching是边的总集合E的子集，即图里的某些边，且matching里的边相关的端点全都不一样，记号写为M。一个端点是matching里相关的端点则称为be matched in M，否则就称unmatched。maximum matching就是尽其所能地获得最大的matching。在bipartite图里，如果V1里所有端点都是和matching相关的，也就是|M| = |V1|，这时的M称为complete matching。
对于一个bipartite图，有关于complete matching的一个等价条件，即如果这个bipartite图有complete matching等价于|N(A)| ≥ |A|，其中A是任意V1的子集，这一条件均成立。
定义subgraph（子图）这一概念：对(V,E)的子图(W,F)，其中W是V的子集，F是E的子集。直观来说对一个图去掉某些边或者点得到的都是它的子图。
subgraph induced（导出子图）是子图的一种特殊情况。导出子图的性质是，如果一条原来的边在导出子图中，那么这条边对应的顶点也一定在导出子图中；且反过来也成立，即两相邻点在导出子图中，那么这个对应的edge也在导出子图里。
对图的元素作边的增加或减少，记号分别为G − e = (V, E − {e})和G + e = (V, E ∪ {e})，这里记号的都是集合运算。顶点的增加和减少记号也类似。
当我们将某些边从图里去掉了，且有isolated的点的时候，我们同时会将这些隔离起来的点也去掉。
图的并集过于简单，不再阐述。
10.3 图的表示及同构
当我们可以对图作平移、翻转某些点和边使得两个图长得一样的时候，我们称这两个图是同构（isomorphic）的，记号为Ｇ1 ≅Ｇ2。
图的adjacency list表示法：列出图的所有顶点在左侧，右侧列出相邻的顶点。有向图中则左侧列出起始点，右侧为终点。
adjacency matrix表示法：matrix元素（i，j）表示为i与j相连。值得注意的是，当图不是简单图的时候，这个matrix不是0-1矩阵，具体的边数则反映在（i，j）位置上，如有三条边则这一位置的元素=3。容易知道，无向图的这个matrix一定对称。
incidence matrix表示法：对图的顶点和边标号，当顶点和边相关联时对应元素为1，例子如下：
当图是稀疏（sparse）的时候，我们常用邻接列表表示图；当图稠密（dense）的时候，我们常用邻接矩阵表示图。
图的同构有一些非常好的性质。图的graph invariant（不变量）在图的同构下是不变的。也就是，顶点和边的连接在同构变换下是等价的。这就推出了，如果两个图的某些顶点的度不一样，或者边相连的点的性质不同，这两个图不同构。如下图，
中央的两个三度顶点，他们相连的两个两度顶点性质不一样，左侧的两个两度顶点是分开的，而右侧的是连起来的，因此不同构。但这一方法往往难以便捷使用。我们希望有其他的算法去实现判断。
引出来：判断图的同构要用邻接矩阵表示。然后对两个矩阵分别按行计次和按列计次（记!=0的元素个数），分别得到h1，l1，h2，l2为行向量/列向量。将h1和h2、l1和l2通过交换方法在原矩阵中交换行或者列使h1=h2，l1=l2。得到这两个新的矩阵后再通过行列交换，如果怎么交换都不能让这两个矩阵相同就是不同构的。这里的交换是要在行次和列次都相同的情况下交换的，如果行向量/列向量元素有相异的则直接判断为不同构。
10.4 图的连通性
引入一系列概念：path（路径）在图里就如字面意思，是点的序列。而circuit就是起点和终点相同的path。path和walk相近，walk就是在这个序列之间插入对应的边。closed walk就是circuit对应的walk。当walk没有重复的边的时候则可称为trail。（只需记住path和circuit即可）
当path没有边相同时，称为simple path。对应的我们也有simple circuit。当path没有顶点相同时，称为element path；对应地，除了起点终点之外顶点不相同的circuit称element circuit。
在连通无向图中，每两个点都有simple path。在一个不完全连通的无向图中，connected component指极大的连通子图，这可以有多个。
当去掉某个顶点的时候，可能会使图的连通分量多起来。这个顶点（可以有很多这样的顶点）就被称作cut vertices。这里要同vertex cut区分，vertex cut是能令G不连通的顶点集合。类似地，去掉某条边使图的连通分量多起来，这些边被称为bridge或者cut edge。
没有cut vertices的图称为nonseparable graph。我们有时希望移除某些顶点使一个图不连通。𝜅(G)被定义为vertex connectivity的记号，就是将当前这个图变得不连通要移除的最小顶点数目。其中，我们知道Kn是无论如何都是连通的。这里定义κ（Kn）= n-1，故任何非Kn的图G，都有0 ≤ 𝜅(G) ≤ n − 1。
我们定义一个图是k-connected的，这等价于κ（G）≥k，切记是大于等于而不是等于的。可以举些例子，比如G是1-connected就说明它是连通且不为单一顶点的那种图；2-connected/biconnected就说明这是nonseparable graph且G至少有三顶点。
同样地，我们可以定义edge cut和edge connectivity。记号为λ（G）。有一条不等式描述了λ和κ的关系：𝜅(G) ≤ 𝜆(G) ≤ minv∈V deg(v)，其中最右侧是图的单一顶点最小度。
有向图里的任意两点可达称为strongly connected。而如果将有向图的方向忽略时，这是个连通无向图则称这个有向图为weakly connected。容易知道，strongly connected是weakly connected更强的条件。有向图里的connected component称为strong component。
path还可以用来判断isomorphic证伪。如果感觉可能是同构，其实可以把同构函数定义出来来判断isomorphic。
用邻接矩阵乘法可以判断路径。A^n对应位置（i，j）的元素就是在原来图中i到j的路径，n是路径长度。例如，n=2时矩阵里的不为0的元素对应的就是i到j长度=2的路径数目。这里的幂次是数学定义的矩阵幂次，不是布尔值的。将B=A+A^2+A^3+……+A^n称G的可达性矩阵。有向图中，如果B里元素全不=0则为强连通；将A赋值为Ａ∨ＡT，如果此时的B全不=0则为弱连通。
10.5 欧拉道路和哈密顿道路
Euler circuit就是把所有边遍历一遍、不重复的circuit；Euler path同理。在walk这种记号下，Euler circuit被称为Euler tour，Euler path被称为Euler trail；有欧拉回路的图叫欧拉图。
对于一个连通的、顶点数至少=2的多重图，它有欧拉回路当且仅当每个顶点的度都为偶数。而这样的多重图有欧拉道路而非欧拉回路则当且仅当它有两个度为奇数的顶点。而且，这样的欧拉道路必定起始于一个奇度的点，并终止于另一个奇度点。
在有向图中，有欧拉回路的充要条件是图的每个节点入度=出度。
不含孤立顶点的有向图有欧拉道路的充要条件是：1.弱连通 2.只有exactly两个顶点，一个入度=出度+1，另一个出度=入度+1。这很形象地可以理解为，它要出去，同样也要回来。
在寻找欧拉回路的时候，如果从某点开始有多个选择，则优先选择不是bridge的边，这样才更有可能找到。
Hamilton path就是把所有顶点遍历一遍、不重复的path；Hamilton circuit同理。在walk这种记号下，Hamilton circuit被称为Hamilton tour。有哈密顿回路的图叫哈密顿图。
Dirac’s theorem: 对于n(n>=3)个顶点的简单图，如果每个顶点的度都≥二分之n，那么这个图有哈密顿回路。
Ore’s theorem：对于n(n>=3)个顶点的简单图，如果两个不相邻顶点u，v满足deg(u) + deg(v) ≥ n，那么这个图有哈密顿回路。
Kn（n≥3）一定有哈密顿回路。
还有个不那么好记的结论：对于边数=m的图G，如果m≥(n^2-3n+6)/2，那么这个图有哈密顿回路。
在Ore定理有一个相近的定理，即：对于n(n>=3)个顶点的简单图，任一对顶点满足deg(u) + deg(v) ≥ n-1，那么这个图有哈密顿道路。
对哈密顿图，如果将它某些顶点（将这些顶点的集合记为V1）和相连的边删除，得到G-V1的子图，那么这个子图的连通分量的数目必定≤|V1|。用这条性质常用来对一个图是哈密顿图的证伪。
10.6 最短路径问题
最短路径问题要求dijkstra’s algorithm的运用。
dijkstra算法可以求出当前节点到所有节点的最短路径。其核心实现为：先将当前路径标为0，其他节点的距离=无穷。在当前已确认的顶点中要找到下一个最小权值的顶点，将这个顶点拿到已确认的集合里，然后将已确认顶点集合到未确认部分的所有距离都按最小（由最开始的顶点出发得到的距离里的最小值）来更新一遍，直到走完整个图。示例如下：
这个算法的时间复杂度是n^2。
另一种算法，利用矩阵进行最短路径求解。这通常在有向图中使用。对所有顶点进行编号，然后分别写出各阶的邻接矩阵，即对于长度=k（k=1，2，……，n）的路径对应权值之和写入矩阵相应起点终点对应的位置，不可达的路径记为正无穷。同时这里要记得，这里的矩阵的幂次不符合矩阵乘法，这里是完整走一次warshall算法则增一阶，并将前一阶的结果清除，以此得来的各阶矩阵。将1阶到n阶的矩阵同一个位置元素取最小值作为最终结果，这样得到的矩阵就是最短路径矩阵，这个矩阵对应的ij就是i到j的最短路径长度。但我感觉这一方法并没有dijkstra方法简便，仅作为介绍。
旅行商问题：在给定无向有权图寻找权值和最小的哈密顿回路。值得注意的是，这个路径不一定存在，但这个无向图是完全图的时候（Kn）则必存在。这里直接给出最佳算法，省略过多引入和介绍。
解法比较直观，即找到权值最小的边的两个顶点出发，每一步都是贪心取最小权值直到走完这个图并且回到顶点。将这两个顶点的路径对比，权值较小的那一个就是权值和最小的哈密顿回路。应当注意，第一步一定是从当前顶点走到最小权值边的另一个顶点。这里从任一顶点出发每步都贪心的走法的算法称为approximation，最近邻域算法。
10.7 平面图
平面图（planar graph），指的是一个图在平面上没有交点（crossing），这里的crossing指的是在两条edge处交叉，不是两edge有相同顶点的交叉。
在平面图中，把平面分割成若干份，其中这些被切割出来的区域称region或者face。region的数目是不随着平面图的画法改变的。值得注意，如果图的外围是闭合的，那么图外面还有一个region。如下图所示。
平面图里的region的degree被定义成region的边界的边数。这个概念课本仅作为引入。同时，平面图的所有region的度之和也等于2*边数。
欧拉公式：对于连通平面图，e为边数，v为顶点数，r是region数，满足关系v+r-e=2。
欧拉公式往往和顶点的度结合起来问问题，要记得顶点的度之和=2e这一基本事实。
关于平面图有一些不那么好记的结论：对于连通简单平面图，如果v ≥ 3，那么满足e ≤ 3v-6。
对于连通简单平面图，它一定有一个度不超过五的点。
对于连通平面图，如果每个面的度都≥a,那么满足e ≤ a*(v-2)/(a-2)。
对于连通简单平面图，如果v ≥ 3且没有长度=3的回路（可以有长度更多的回路），那么e ≤ 2v-4。
下面在引入kuratowski’s theorem之前先作几个定义。定义一个操作称elementary subdivision，就是在当前平面图的边上插入若干个顶点。通过这样的操作得到的一系列平面图都互为homeomorphic，同胚的。（注意这个单词和homomorphic很像但又不完全像）换句话说，对一个平面图，插入或删除一些2度节点，如果操作之后的图和原图能同构，则两图同胚。
引出来：kuratowski’s theorem:一个图是非平面的，当且仅当它包含K3,3或K5的同胚图。这常用于对判断一个图不是平面图。
下面介绍对偶图。一个平面图的对偶图指在平面的所有region内各取一点，然后让这些点的连线都经过原图的所有边，且仅经过一次。一般的做法是，取最外面的region里的点汇集内部的所有点，其中必须保证所有原图的边都有被经过。然后其他region的点应尽可能地汇集到最外面的这一点。如图所示是很典型的例子，其中环是一条边，故仅经过一次即可；左侧有一条单边，则应该经过后直接返回。
10.8 图着色问题
对一个map，如果用本节的图来表示，则称这个图为dual graph。
简单图的着色的定义就是将图里的顶点着色，且最终没有相邻的顶点是同一颜色的。
这里定义一个概念，图的chromatic number（要记得这个拼写），就是最小颜色数目，记号为𝜒(G)。
著名的四色定理：在平面图中，𝜒（G） ≤ 4。
但其实对图判断其𝜒的大小可以比较方便地用观察法得出。在观察时，我通常将第一步放在度最多的节点上。
图的着色主要用于调度问题，即子元素之间不能共存，可以用图着色思想解决问题。
图的着色多项式：用来求解𝜒(G)的系统性方法，和观察法相异。其列出方法为：将图中一个点的着色方法数记为x，然后逐个地对其周围点的着色方法数进行列举直到所有的顶点列举完毕。然后将这些着色方法数乘起来=Pg(x)（g为下标），Pg(x)即为着色多项式的记号。
得到图的着色多项式之后，Pg(x)的x代入式子中的含义就是可以用最多x种颜色对当前图着色的方法数。举个例子，对K5,Pk5(x) = x(x-1)(x-2)(x-3)(x-4),则𝜒(K5) = 5!。
对于有多个连通分量的图，这个图的着色多项式就是各连通分量的着色多项式的乘积。
关于图的着色多项式还有一个定理：在图中任选一边e，原图的着色多项式 = 将这条边去掉的子图的着色多项式 - 将这条边两个端点合并成一个端点的子图的着色多项式。
下面介绍最大流算法。课程中仅涉及ford算法。
这里的最大流指的是在当前各个路径的限制下让source，源头流出最多的水。我们得到一个待计算的图，每条边上会有相应的最大容许流量（称capacity）和当前流量。建议从所有管道当前流量=0开始，而不是从当前状态（有可能部分管道当前已有流量）开始。然后把每一条管道上的数字改为initial vertex到end vertex还能再流多少水的数目（在第一步时，这和原图一模一样）。我们从这里开始寻找从source到sink（终点）的一条路径，找到这条路径之后获得路径这多条弧上（记得其方向性，反方向的不在路径上）的最小数字m，将路径上所有按原方向的弧的数都减去m，与此同时，将反方向的弧的数都加上m，这里如果弧不存在则应创造这条弧，若某些弧在-m的时候=0则应删去。
重复寻找路径、删去和加上m这一步骤，直到source无论如何都不能到达sink，此时达到最大流。将当前这个图的边上的数变回当前已有流量（而不再是还能再流多少水的数目），最大流的数目就是以source为initial vertex的弧上数目的总和。
在最大流算法涉及到的图中，我们有cut（割集）的一些性质。cut指的是画一笔经过图的一些边，让这个图分成若干个互不相连的部分，cut被定义成这一笔经过的边的集合。这里cut的性质为，cut一定包含从source到sink的某些边。
另一个性质，定义cut K的capacity = K中元素的capacity之和，记为c（K）。那么任一条管道中的流量都 ≤ c（K）。
在这里还有一个定理，最大流的值等于最小割集capacity。
至此，离散数学的图部分介绍完毕。