Walk/Trail/Path/Circle

在图中，途径(Walk)是指如下形式的 边序列

  • 边的数量是迹的长度
  • 简单图可以表示为
  • 起始点initial vertex：
  • 终点final vertex：
  • 内部点internal ertex：

特别地，我们称边集相异的途径称为 迹(trail)

我们称顶点集相异的迹称为路(path)

  • 所有的点为,可能存在
  • 记作

对于顶点和终点相同的路称作圈(circle);

  • 所有的点为,
  • 记作
  • 长度为3的圈记作三角形(triangle)

Theorem

对于顶点集为和邻接矩阵,邻接矩阵的幂

表示间长度为的迹的数目；

proof :归纳法

Theorem

对于所有点度数至少为2的图，必定包含一个圈;

proof:考虑最长路；

Lemma

对于简单图,,那么包含一条长度至少为的路；

连通图

称图是连通的(connected)，当且仅当对于点集中任意点对,存在到的路；

连通分量的数目记作;

Theorem

对于具有个顶点的简单图 ,其有个连通分量，边的数目满足以下不等式约束：

proof: 下界显然，上界只需注意以下引理

Corollary

任意具有个顶点的简单图，若其边数大于, 则一定是连通的； proof：这意味着连通分量个数小于2；

Distance

对于图上两点

  • 距离：从到的最短路的长度；
  • 离心距:对于点,遍历可能的顶点,使得最大化的距离值；
  • 图的直径:使得最大化的离心率值；
  • 图的半径:使得最小化的离心率值；
  • 图的围长:图的最短圈的长度；
  • 图的周长:图的最长圈的长度；

Theorem(Konig)

图是二部图当且仅当图中不含有奇圈； proof: 反证法；

Edge-Connectivity

断集(disconnecting set)是指对于连通图上的一组边，满足其消失导致图变得不连通；

对于，,如果两个点集之间的边，其顶点各在不同的两个点集之中，记作;

边割(edge cut)就是指这样一种;这样的边割定义蕴含着某种对称差性质，记作;

称图的最小非空边割为键(bond)；

若一个边割只包含一条边，我们称这条边为割边(cut edge)/桥(bridge)；

image-20250113175050077

对于连通图，其边连通性（edge connectivity）定义为最小边割的大小，也就是我们使图不连通所需要删除的最少边数，记作; 换句话说，若,称是边连通的，但不是边连通的；

note:边连通性描述了图到底有多么连通的性质，删除多少条边才能使得图变得不连通，暗示着图两点之间的独立路径数；

Lemma

对于图上的顶点子集，满足

proof:统计贡献；

Corollary

图是偶图(每个顶点的度为偶数)，当且仅当对于任意的非空顶点子集, 为偶图； proof：充分性显然，必要性只需要取一个顶点构成的点集即可；

Lemma

对于图,其点集的子集，有

proof:如下图 image-20241104183459892

Theorem

对于连通图，一个边割是键当且仅当恰好有两个个连通分量；一个边集是边割的充分必要条件是是若干键的不相交并； proof：利用键的最小性即可；

Lemma

对于图，一条边是桥当且仅当不在图的圈中； proof：反证法；

Vertex-Connectivity

对于连通图，称一组顶点为点割(vertex cut)，如果删除这组顶点会导致图不连通；若点割只包含一个顶点，则称这个点为割点（cut vertex）;

类似定义点连通性为点割的最小大小，记作，也就是使得图不连通的最少删除点数 若，称作图是点连通的，但不是点连通的；

Theorem

对于简单图,有; proof：考虑度最小的点，尝试删除与其关联的边，有; 取一组最小的边割,完全图的情况平凡，考虑非完全图，取出； 构造

这是一组点割，容易观察到; image-20241104183524845

2-连通图

称两条路内部不相交(internally disjoint),如果他们没有共同的内部顶点；

2-连通图意味着它既是2-边连通的，也是2-点连通的；

Theorem

对一个至少有3个顶点的图，若是2-连通的，当且仅当对于每一个点对,均存在两条内部不相交的路将他们相连；

proof:充分性：删去一条边/点仍有另一条路径将之连通；

必要性：对距离归纳，相邻情况平凡；考虑最短路径前面一个点，构造不相交路径，删去该点仍然存在一条路径将之连通，如下图，选择最后一次与先前构造的两条路径交汇的顶点即可；

image-20250113183629667

Theorem(Menger,vertex version)

拥有至少条路经的图是-点连通的当且仅当对于每一个点对存在条内部无公共点的路径；

Theorem(Menger,edge version)

图是-边连通的当且仅当对于每一个点对存在条内部无公共边的路径；

Eulerian Graph

欧拉迹(Eulerian trail)定义为包含图中所有边的迹；若这个迹闭合，称为欧拉圈（Eulerian circuit）； 若图包含一个欧拉圈，称该图为欧拉图(Eulerian graph)；若图不包含欧拉圈，但是包括一个欧拉迹，称该图为半欧拉图(semi Eulerian graph)；

Lemma

若图是图，每个顶点的度至少为2，那么图包含圈； proof:对于非简单图，结论平凡，对于简单图，考虑最长路即可；

Theorem

若连通图是欧拉图当且仅当每个顶点的度数为偶数； proof：配对；

Theorem

若连通图是半欧拉图，当且仅当恰好存在两个顶点的度数为奇数； proof：除开迹首尾两个顶点外配对，迹首尾两个顶点为奇点；

Fleury Algorithm

构造欧拉圈可按照如下算法：

  1. 从一个顶点开始，选择与之关联的，未被遍历的一条边；
  2. 若选择的边是桥，改选其他边，若没有别的选择，就选择桥；选择这条边的另一个顶点为;
  3. 将这条边加入迹中，擦除这条边
  4. 若产生了新的孤立点，同时擦除这个孤立点；
  5. 将更新为，选择下一条边；

Hamilton Graph

一个哈密顿圈是指一个遍历图中所有顶点的圈； 一个图为哈密顿图当且仅当图包含一个哈密顿圈；

  • 对于，是哈密顿图
  • 当且仅当时，是哈密顿圈
  • Peterson图不是哈密顿图

由此定义图的哈密顿闭包:通过在不相邻的点对上增加边，达到不存在不相邻的点对使得的状态，也就是无法继续加边；这样的加边是顺序无关的；

image-20241105150112268

Theorem

若均是哈密顿图，那么是哈密顿图; proof:对于为偶数，构造如下：

image-20241105145856010

对于为奇数，构造如下：

image-20241105145925675

Theorem

对于哈密顿图，取顶点集的非空真子集，有

proof:取的哈密顿圈，至多个分量；意味着至多个分量；

Theorem(Erdos)

对于具有个顶点的简单图，若，则图是哈密顿圈； proof：反证法，增加边使得成为没有哈密顿圈的最大图，取图中的最长路;由假设 注意到

Ｓ

image-20241105150019504 则存在哈密顿圈; 注：可进一步加强为对任意不相邻的点对成立，这说明在简单图上哈密顿闭包是良定义的；

Lemma(Bondy)

对于简单图，是哈密顿图当且仅当的闭包是哈密顿图；

Theorem(Chvatal)

对于简单图的度序列为，，，则图G是哈密顿图;

Theorem（Chvatal-Erdos）

若，则是哈密顿图，除非

Claw-free Graph

称图是**无爪的(**claw-free)，当且仅当其不含

在无爪图中，任何顶点的邻居的生成子图只有两种类型，从而将顶点分为两类：

  • Type1:连通图
  • Type2:仅有两个连通分量，并且分量都是完全图；

对于Type1的顶点，定义操作：在邻居中添加原本没有的边；只要邻居不构成团，操作就可以进行；

定义Ryjáček闭包：对于无爪图,反复应用上述操作使得每一个Type1顶点邻居都能导出团，增边结束后生成图；

Theorem

是哈密顿的当且仅当是哈密顿的；

Theorem

设是2-连通图，顶点数,和是的不同点。若

则具有哈密顿圈。

Shortest Path Problem

Gravity法

Making a model of the map by knotting together pieces of string whose lengths are proportional a length of the roads. To find the shortest length, take hold of the knots corresponding to A to L–and pull tight !

Dijkstra算法

The idea is to move across the graph from left to right, associating with each vertex X a number l(X) indicating the shortest distance from A to X. This means that, when we reach a vertex such as Kin the figure, then l(K) is either l(H) + 6 or l(I) + 2, whichever is smaller.

Chinese Postmen Problem

邮递员希望投递信件，尽可能短的总距离并回到他的起点。显然，他必须至少穿过路线中的每条道路一次。

image-20241105161909715

在一个具有非负权的带权连通图中，找出一条总权重最小的环游，这种环游称为最优环游。

若为欧拉图，任意欧拉圈都是最优环游；

考虑为非欧拉图，其必然包含偶数个奇度顶点；并且， 对于任意一个环游必定通过某些边不止一次，选取重复边按相同权值加入图中，问题等价描述为一个最优化问题：

添加重复边求一个欧拉赋权母图，最小化

同时找到的欧拉圈；

Theorem

上述欧拉赋权母图拥有最小权值的欧拉圈当且仅当

  • 的每一条边至多被添加一次
  • 对于的每一个圈,均有

Ttravelling Saleman Problem

一位旅行推销员希望参观一些城镇，然后返回他的家。鉴于城镇之间的距离，他应该如何规划路线，以便他只访问每个城镇一次，并最大限度地减少总旅行距离？

该问题可形式化描述为最小化带权完全图的哈密顿圈权值，称问题的解为TSP环游；

这是一个NP-hard问题；

Aheuristicapproach:2-edge-exchange: 如果一个可以通过删除两条边并添加两条边从另一个获得，则两个TPS路径称为2-相邻；

image-20241105165412898

通过上述边的对换， 我们可以迭代地挖掘出最优路径；