离散数学--图论

1.简单概念

2.握手定理

3.点割集

4.边割集

5.点连通度和边连通度

6.Dijstra算法&&最短路径

7.有向图的连通性

8.图的矩阵表示

9.欧拉图问题

10.哈密尔顿图

1.简单概念

（1）这个里面的完全图比较重要，完全图是例如k3,k5这样的表示方法，角标表示的就是图上面的节点的个数；

（2）完全图定义是这个图上面的任何一个节点和其他的节点之间都有连接，但是这个节点自己没有形成环，在矩阵的表示上面矩阵对角线上面的元素是0，其他的元素都是1，这个0表示的就是节点自己没有形成环，1表示的就是节点和其他节点之间有一条连接边；

（3）图的同构：充要条件就是节点和边之间存在一一对应的关系，但是这个充要条件我们一般不是使用，因为这个充要条件还是无法进行判断两个图之间是否是同构的；

（4）在判断图的同构问题上面，我们使用的就是这个必要条件，就是两个图的节点的数量是相同的，边数也是相同的，度数相等的节点的数量也是相同的，因此我们在考试时候进行判断时，只需要这个判断节点数量和边的数量是否一样，一样的话看看读书相同的节点的数量是否是一样的，例如两个图1和2，图1和图2的节点数和边数都一样，我们就看看度数相同的节点的个数，如果图1和图2都是有3个5度的节点和2个3度的节点，这两个图就是同构的；

但是如果图1有一个3度的节点，但是图2的节点都是2度的，说明对于3度的节点而言，两个图的节点个数不相同，一个是1个，还有一个是0个，这个就不满足必要条件，这个时候的图1和图2就是不同构的；

2.握手定理

（1）节点的度数的和是这个图的边数的2被，例如这个图16个节点，我们就可以推断出来这个这个图有8条边；

（2）这个推论是经过证明的，所以我们可以直接进行使用，这个推论就是主要用来判断一串度数序列是否可以构成无向图，这个要求解释奇数度节点个数是偶数个；

大概就是说这个，例如1 3 5 7 6这个序列，是否可以构成无向图，奇数度节点个数就是1 3 5 7这四个节点，上面的1 3 5 7表示的是节点的度，表示这个图有5个节点，这五个节点的度分别是1 3 5 7 6，因为这里的奇数度结点个数是4，是偶数个，所以这个序列就可以构成这个无向图；

但是像1 3 9 6这样的序列，技术度节点只有3个，所以这个序列就无法构成无向图，所以我们通过这个握手定理的推论是可以进行一些直观的判断的；

3.点割集

（1）点割集实际上就是一个集合，里面可以有多个元素；

（2）简单的理解就是对于一个具有连通性的图，删除掉某个节点或者某些节点之后这个图就不联通，我们称这个节点或者这些节点就是点割集；

（3）示例图片的图割掉v3之后就不联通，所以v3就是一个点割集，割掉v5之后也不联通，v5也是一个点割集；

需要注意的就是这个割掉某个点之后，和这个节点相连的所有的边就会消失，割掉v2和v4之后，这个图就不会联通了，所以这个v2,v4在一起的这个集合就是点割集；

但是如果仅仅割掉v2或者v4可以发现这个图依然是联通的，这个时候我们就可以说单独的v2或者v4这个集合就不是点割集，只有v2,v4在一起的这个集合才是一个点割集；

4.边割集

（1）这个边割集和点割集都一样，就是一个普通的集合，删除这个集合里面的元素之后这个图就不再联通了；

（2）点割集和边割集的不同点就在于这个点割集删去的是点，边割集删去的是边，其他的规则就本上都是一样的；

（3）在数学符号语言里面，通常使用的是 V大写代表的是点（Vertex）,使用大写的E代表边（Edge）这个为了记住这个表示方法，我们可以使用英文单词进行辅助记忆；

5.点连通度和边连通度

（1）删除某个或某些节点之后就不在连通的点，我们称之为点割集，这个过程中，可能在某些图里面，我们删除一个点就可以让这个图不再连通，可能我们要删除2个3个或者更多的点才能让这个图不再具有连通性；

这个多种途径里面，我们把这个删除最少的点就可以破坏连通性的点的个数称之为点连通度；点连通度使用K进行表示；

（2）一些推论

非连通图，因为这个图本来就不是连通的，所以我们规定非连通图的点连通度是0；

完全图的点连通度是n-1,n表示的就是这个完全图里面的节点的个数；

存在割点的图的点连通度是1,因为我们只要删去这个割点就可以破坏这个图的连通性；

（3）边连通度的定义和推论，类似于点连通度，边连通度使用λ进行表示；

（4）图的最小度表示的就是这个图的所有节点的度里面最小值，最小度是使用德塔（输入法无法敲打）；

一般这个点连通度和边连通度和这个最小度之间的关系就是点连通度<=边连通度<=最小度；

6.Dijstra算法&&最短路径

（1）这个图论的算法在许多的领域里面都是有这个应用的，在这个离散数学里面学习的图论，我们在计算机的核心课程数据结构里面的图也是大同小异的，包括这个算法迪杰斯特拉算法在这个数学建模的比赛里面也是经常使用的，所以我们在这里是有必要介绍一下的；

（2）这个算法的本质就是这个贪心算法，简单的讲就是只会顾及眼前的利益，而不会去管这个后面的结果，在这个常规的算法介绍里面，通常都是这个使用两个集合来不断的更新（这个就是我第一次学习的时候看网上的博主讲的），但是这个我感觉很难理解，下面介绍一种新的方式（这个方式是从数学建模的角度）；

（3）单源最短路径的子路径都是这个最短路径，我们这个实例是使用的1到3的最短路径，到底应该如何理解这个迪杰斯特拉算法呢？我们首先选取这个1节点作为源节点，1可以直接到达的节点就是2,5节点，到其他节点都是无法直接到达的，所以我们记作无穷大，12距离就是10，15距离就是5，然后我们找出这个里面的最短路径，就是1---5的5这个距离，然后在这个左边画上一个小图，表示1------5的情况；

（4）接下来，我们以15作为这个新的起始区域，相当于是把这个15看作为一个整体，把他们捆绑在了一起，这个整体可以直接到达的节点就是243节点，152长度是8,153长度是14,154长度是7，这个里面最短的就是7了，再把这个新的路径进行更新，补充在右边的这个小图上面；

（5）接下来就是把这个154捆绑在一起，作为一个新的整体，这个时候就出现了初学者们肯能会不理解的问题，就是在这个里面，154整体可以直接到达的就是23了，到达2的话，就是这个152，路径的长度就是8，到达3的话，就是这个153或者是1543这两条路径分别是14,13，总上来看最短路径长度就是8，这个时候我们就会添加上2这个节点；

（6）接下来就是把这个1542作为一个新的整体，然后找到这个整体到达3这个节点的最短距离，通过比较我们就可以发现这个1523就是这个最短的路径距离，我们就结束了这个整个的查找的过程，这个时候我们想要的1到3的最短路径就已经呼之欲出了，我们不仅找到了13之间的最短路径，这个路径上面的任意的子路径都是最短路径；

7.有向图的连通性

（1）这个里面我们会分别介绍一下这个强连通图，单向连通图，弱连通图这三种类型的图；

（2）这个强连通的意思就是这个图上面的任意的两个节点之间都是可以双向奔赴的，就是我有办法沿着有向的路径找到你，你有办法沿着有向的路径找到我，这个就是强连通性；

（3）单向连通实际上就是一个简单的中间状态，要求可能没有那么的苛刻，就是对于一个图里面的任意的两个节点，只要我们两个之间可以单向的找到就可以了，例如中间的这个图里面的13节点，1可以找到3，但是3没有办法找到1，1可以找到4，但是4没有办法找到1,5可以找到3，但是3可以找到5（这样肯定就会更好了），因为我们的要求是只要有一种方式找到对方，就满足这个单向连通的定义了，这个两个双向奔赴的情况肯定是单连通的，这样的图就属于单向的连通关系；

（4）弱连通就是，以上面的右边的图片为例，对于1这个节点，任何节点想要到达他都是不可能能的，因为这个节点只有初度，没有入度，这样的图就是这个弱连通图，其实判断弱连通图我们就可以观察这个图上面是不是有某个节点只有初度没有入度（1节点），或者只有入度但是没有初度（2节点），但是去掉方向之后这个图依然是连通的，这个时候我们就可以说这个图就是一个弱连通图

（5）通过上面的阐述相信你也发现了，强连通图一定是这个单向的连通图，单向的连通图一定是弱连通图；