离散数学笔记第五章（图论 ）

图论包括，图的基本概念，欧拉图与哈密顿图，树，平面图，支配集等等，照例我只学了图的基本概念，欧拉图与哈密顿图，和树

IMG20191130204702.jpg

欧拉图

1.无向连通图 G 是欧拉图，当且仅当 G 不含奇数度结点( G 的所有结点度数为偶数)； 2.无向连通图G 含有欧拉通路，当且仅当 G 有零个或两个奇数度的结点； 3.有向连通图 D 是欧拉图，当且仅当该图为连通图且 D 中每个结点的入度=出度； 4.有向连通图 D 含有欧拉通路，当且仅当该图为连通图且 D 中除两个结点外，其余每个结点的入度=出度，且此两点满足 deg-(u)-deg+(v)=±1 。（起始点s的入度=出度-1，结束点t的出度=入度-1 或两个点的入度=出度）； 5.一个非平凡连通图是欧拉图当且仅当它的每条边属于奇数个环； 6.如果图G是欧拉图且 H = G-uv，则 H 有奇数个 u,v-迹仅在最后访问 v ；同时，在这一序列的 u,v-迹中，不是路径的迹的条数是偶数。 弗勒里算法 弗勒里(B.H.Fleury) 在1883 年给出了在欧拉图中找出一个欧拉环游的多项式时间算法，称为弗勒里算法(Fleury’salgorithm)。这个算法具体表述如下： 输入：一个连通偶图 G 和 G 中任意一个指定项点 u 输出：从 u 出发的 G 的一个欧拉环游 1、令 W：=u，x：=u，F：=G 2、while 3、选一条 中的边 e，其中 e 不是 F 的一条割边；如果 中的边都是割边，那么任选一条边 e 4、用 替换 ，用 y 替换 x ，用 替换 F 5、end while 6、返回 W 其算法核心就是沿着一条迹往下寻找，先选择非割边，除非这个点的邻边都是割边。这样得到一条新的迹，然后再继续往下寻找，直到把所有边找完。遵循这样一个原则就可以找出图的一个欧拉环游来。 在有向图中也可以类似地定义有向环游、有向欧拉环游、有向欧拉图和有向欧拉迹的概念。 类似地，有如下定理：一个有向图是有向欧拉图当且仅当这个图中每个顶点的出度和入度相等。 [1]

哈密顿图

与欧拉图的情形不同，还未找到判断一个图是否是哈密顿图的非平凡的充要条件。事实上这是图论中尚未解决的主要问题之一。哈密顿图有很多充分条件，例如， （1）若图的最小度不小于顶点数的一半，则图是哈密顿图； （2）若图中每一对不相邻的顶点的度数之和不小于顶点数，则图是哈密顿图。 另外，还有很多用度序列、度和、图的坚韧度等参数给出的充分条件。 [2] 哈密顿图的充分条件和必要条件 定理1： 设无向图G是哈密顿图，V1是V的任意的非空子集， p(G-V1)≤|V1| 其中，p(G-V1)为从G中删除V1(删除V1中各顶点及关联的边)后所得到的图的连通分支。 定理2： 设G是n(n≥3)阶无向简单图，如果G中任何一对不相邻的顶点度数之和都大于等于n，则G是哈密顿图。 定理3： 在n(n≥2)阶有向图D=中，如果所有有向边均用无向边代替，所得无向图中含生成子图Kn，则有向图中存在哈密顿图。 推论： n(n≥3)阶有向完全图为哈密顿图。 哈密顿路径也称作哈密顿链，指在一个图中沿边访问每个顶点恰好一次的路径。寻找这样的一个路径是一个典型的NP-完全(NP-complete）问题。后来人们也证明了，找一条哈密顿路的近似比为常数的近似算法也是NP完全的。

废江博客 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权 转载请注明原文链接：离散数学笔记第五章（图论 ）