Site Overlay

离散数学(图论)笔记

词汇

英文试卷,实在头大。

infinite graph:无限图

finite graph:有限图

simple graph:简单图

multiple edge:多重边

multigraph:多重图

pseudograph:伪图

undirected graph:无向图

directed graph:有向图

multiplicity:重数

Acquaintanceship Graph:表示人认识关系的向图

Friendship Graph:同 Acquaintanceship Graph

Influence Graph:表示人相互影响的向图

Collaboration Graph:表示协作关系的简单无向图

Call Graph:调用图,属于有向图。

Web Graph:属于有向图。

Citation Graph:引用图,有向,无多重边和圈。

underlying undirected graph:基本无向图,把有向图的方向忽略得到的图。

complete graph:完全图

cycle:圈图

wheel:轮图

n-cube:立方图

bipartite:二分图

complete bipartite graph:完全二分图

subgraph:子图

proper subgraph:真子图

subgraph induced:导出子图

edge contraction:通过合并点来构造新的图

基础概念

图(Graph)顶点(Vertex)加上顶点之间的连线(边(Edge))。

typora\20201129165240_ace7c65f9ae2ad51f126519c09af6751.png

记作: $G = (V,E)$ 。顶点记作: $G(V)$,边记作 $G(E)$

无限图:顶点或边有无数条

多重边:如果 $V_1\to V_2$ 有两条边,则是多重边。注意,下面这种情况不算多重边:

typora\20201226105424_e9048a0dd5a85fe22ae65ae733e2913a.png

多重图: 有 多重边 的图。

typora\20201129165229_f7b424adad10cb50e7f5ab9204c951d7.png

重数:两结点间平行边的条数称为平行边的重数。

伪图有环或者多重边的图

typora\20201129165258_12851fff782b6dc9fe9c8cf3347b3c01.png

上面的圈圈叫做

有向图

typora\20201129165344_8964bf2f681dc296bc78856cbf33a0f5.png

简单图:没有 多重边 的图。

简单有向图:没有 多重边 的有向图。

邻接、相邻:一条边的两个顶点相邻。

邻居:与 $v$ 相邻的所有点的集合。记作 $N(A)$

:进出 $v$ 的边数。比如环对度数的贡献是 2. 普通边的贡献是 1. (注意:无向图的边的度数贡献是 1,而不是当作双向的2)

孤立顶点:度数 0 的顶点。

悬挂顶点:度数 1 的顶点。

入度:进入顶点的边数。记作 $\operatorname{deg}^- (v)$

出度:离开顶点的边数。记作 $\operatorname{deg}^+ (v)$

完全图(Complete graph):任意对不同顶点都相连的简单无向图。根据顶点的个数 $k$ 记作 $K_n$

typora\20201129170527_ff8ed13e80c03a44ee15edd24856bdf1.png

圈图(Circle graph):自己看图就懂了:

typora\20201129170601_c3baac07e3043e87fbdaf72c8afae27b.png

记作 $C_n$

轮图(Wheel graph):中间带个轴心。

typora\20201129170630_17c0ea7cc113adb71109bc00cb7030e1.png

记作 $W_n$

立方图(Cubic graph)

typora\20201129170758_16e239dc6927d8a8ae08f017b065387b.png

记作 $Q_n$

二分图(Bipartite graph):说白了就是能构成映射的图。

  • 判断二分图的方法

完全二分图:

typora\20201129171032_51a7047b9f1f2c46f382d0c79d5e615a.png

$G(V,E)$ 为某一图。

子图:节点集和边集分别是 $G$ 节点集的子集边集的子集的图。

生成子图:含有 $G$ 所有顶点的子图。

导出子图:也称顶点导出的子图。给一组顶点,与这些顶点所带的边构成的图。

假设 $G$ 为:

typora\20201226112801_e5d98864137aff060315760299408d67.png

则顶点 e, c, b 的导出子图是:(不一定刚好构成路径哈,下面只是巧合)

typora\20201226112808_e1cc018e5ed51ac6462d26203646f351.png

主子图


匹配问题:

两个二分图的可能连线情况如下:

typora\20201129171844_551f567e52d05a5d46b35fb239002b62.png

匹配:一个连线方式是上面的所有连线可能性的子集,每个顶点都直连向一个对面的顶点,则这种连接方式是一个匹配。

最大匹配:连接的边数最大的那种匹配。

完全匹配:连接刚好构成一一对应(双射)的匹配。


霍尔定理:记 $N(A)$ 是 A 的所有邻居。存在 $V_1 \to V_2$ 完全匹配的充要条件是:对于所有 $V_1$ 的子集, $\left| N(A) \right| \leqslant \left| A \right|$

邻接表:一种通过每个顶点的邻居的图表示法。

邻接矩阵:类似关系矩阵。 $a_{ij} = 1$ 表示 $v_i \to v_j$ 的边存在。

关联矩阵:通过顶点和边的连接关系矩阵来描述无向图。

typora\20201129172818_c43d93185a2680a94e23bb5c4a99f398.png

图的同构:如果两个图能扭成一个模样就是同构。严谨点说是存在 $G_1 \to G_2$的映射 $f$ 使得顶点映射过去后,边的连接关系不变。

通路:经过一系列顶点的边的序列。

连通图和不连通图:看下面的图就懂了:

typora\20201129173245_ed9577299a1dd4165365e6ab2538c304.png

连通分支:看下面的图就懂了:

typora\20201129173305_44f931fbc573f6320bfb23a9c1dee182.png

割点:如果一个顶点连同它的相关边删除掉,会产生更多连通分支,这个点就是割点。

typora\20201129173438_6cfbeaed930616a764f99fbdb48fb34f.png

比如这个 $c$ 点。

不可分割图:没有割点的图。

连通度:最少删除 $k$ 个割点能变成不连通图,那么这个图连通度是 $k$

割边:如果一个边被删除之后,会产生更多连通分支,那么这个边就是割边。

边连通度:同理。

强连通:有向图任意 $a,b$ 两点均有 $a\to b, b\to a$ 的通路,则该图是强连通的。

弱连通:有向图去掉方向之后任意 $a,b$ 两点均存在通路,则是弱连通的。

强连通分支:有向图的极大强连通子图。

欧拉回路问题:能否从一个顶点出发,沿着图的边前进,恰好经过图的每条边一次并且回到出发点?

欧拉回路定理:连通多重图中存在欧拉回路当且仅当图中所有顶点的度数为偶数。

哈密顿回路问题:能否从一个顶点出发,沿着图的边前进,恰好经过图的每个顶点一次并且回到出发点?

加权图:给每条边赋予权重(例如表示距离)的图。

最短通路算法:就是寻找开销最小的路径的算法。(开销用权重之和表示)

  • Dijkstra 算法
  • Floyd 算法
  • A* 算法

平面图:如果一个图存在一种表示形式使得其可以铺平后没有交叉,则是平面图。

typora\20201208203809_7232b790338f51a872cd90263ddea347.png

平面图欧拉公式:设平面图 G,有 $e$ 条边,$v$ 个顶点,则 $v+r = e+2$。面数等于边数减顶点数加二。推荐阅读:经典证明:不用数学归纳法直接推导平面图的Euler公式。记忆的话可以用三角形这个特例,两面三点三边。

面的度:面的边界上的边数。

$e\leqslant 3v -6\ (v\geqslant 3)$

初等细分:通俗地说就是在平面图的某一条边上加个起到分割作用的顶点。

同胚:若 $G_1$,初等细分得到 $G_2,G_3$,则 $G_1, G_2, G_3$ 是同胚的。

库拉图斯基定理:一个图是非平面图 $\Leftrightarrow$ 它包含一个同胚于 $K_{3,3}$$K_5$ 的子图。(注:$K_5$ 是5阶完全图,$K_{3,3}$ 是各三个顶点的二部图)。

图着色:给每个顶点指定一种颜色,使得任意相邻顶点的颜色不同。

图着色数:给图着色所需的最少颜色数。记作 $\chi(G)$

四色定理:平面图的着色数不超过 4.

  • 完全二分图的着色数是 2.

常用算法

判断二分图

着色法:只用两种颜色,能否保证给所有点染色时,任何相邻两个点的颜色不同,可以的就是二分图。染色可以用广度优先和深度优先两种顺序。(原理:完全二分图的着色数是 2.)

Dijkstra 寻路算法的工作原理

详见此文。一句话解释就是:找到与起点相邻最近点,再把这个点与源点看做一个整体,作为新的起点,重复步骤,直到抵达目标。

Floyd 算法的工作原理

一句话解释就是:先用一个邻接矩阵,只存放相邻点的数据。不相邻的点记为 $\infty$。然后分别地使用各个点 $P_i$ 建立 $P_i$ 相邻点之间的线索,直到所有点完成这样的操作。可参考此文

TSP(行商)问题

问题描述可直接看此处

参考:https://zhuanlan.zhihu.com/p/161082172

2 thoughts on “离散数学(图论)笔记

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注