[音乐] Hi，欢迎回来。
从这一章开始呢我们来讨论这个图论。
进入到图论的部分。
那我们首先来看看图论是如何被创立的。
那么我们说呢，图论的创立它是从解决一个叫柯尼斯堡七桥问题， 才开始创立的。
那么柯尼斯堡呢是欧洲的一个美丽的城市，有一条河，
横穿这个城市，那么河中间呢有两座小岛， 那么人们为了交通方便呢，在两座小岛和河岸之间
建了这个七座桥，就像我们左下角的这样的一个七座桥。
那么长久以来呢，人们总希望知道说
我能不能从任何一个地点出发，穿过这个七座桥只恰好一次？
能不能把这个整个的道路，七座桥都能够遍历一遍？
那么经过很多人无数次的尝试，人们发现呢似乎好像没有人
能够走出这样的一个路子来，能够只走一遍能穿越七座桥。
那么最终的问题的解决呢是在1736年，由欧拉
他在发表论文当中证明了这个七桥问题是没法解决的，也就是说
没有办法仅走一遍就能够遍历七座的桥。
那么他是如何做的呢？他首先呢在 把这个七座桥抽象成河岸，
然后小岛和，小岛、 河岸之间的一个连接。
然后呢再把这个桥变成一个平面上的节点，
把桥和桥之间的这个通路变成了这个边。
然后呢最终呢他讨论这个奇偶性来解决这个问题。
而且呢他的这个论文里头，还提出，并且解决了 一个一笔画的问题，一笔画呢我们在小学或者是
幼儿园里头，大家都喜欢做这种游戏，就是如何你 的笔不离开这个纸面，能够一笔把这个图画给它画出来，当然也
边是不能够重复的，对吧？那么所以呢，最终欧拉呢他是把我们现实当中的问题
抽象成平面上的点和线的这种组合，
然后呢通过讨论这个点的奇偶性，也就是说这个点它连接了几条线？
那么它是奇数根线，还是偶数根线，最终呢来判定能否遍历。
所以我们说欧拉呢他是第一个把现实当中的问题 抽象成节点和节点之间连接的边，
然后呢并且构造出图这么一个结构，然后最后发展 为一套这样的一个图论来解决这些问题的。
那么图到底是一个什么结构呢？我们说
具体的定义是这样的，图呢是由结点和连接结点的边所构成的一个离散结构。
那么我们既然这个离散结构呢它有分成两个部分， 一个呢是结点，一个呢是由结点连接的边，
那么我们就会把这个结点的集合和边的集合呢，做成一个二元有序组。
然后呢把它记作是图，所以呢我们有说
图G等于V,E，然后它是一个二元有序组，然后其中这个V呢就是结点集合。
结点集合它首先是一个非空集。
然后第二个这个E呢是一个边的集合， 那么边的集合呢它可能是一个多重集合，
那么这里头这个所谓的多重集也就是说，这个集合当中啊它可能会存在相同的元素，
当然如果按照我们初始的这个集合的定义来说，
这个集合当中的元素是不应该重复的，如果重复的话，就不符合这个 集合它本身的这个概念。
所以呢我们当然也可以从另外一个角度来理解，
比如说如果出现了相同元素呢，我们就为这个元素加一个附带的一个属性。
这个属性标明它重复了几次，那这样的话，这个元素还是这个元素，只不过它附带了一个
表示重数的这个属性，所以我们可以通过这种方法来构造一个所谓的多重集合。
那么边集如果是一个多重集合，就表示说这个图当中可能包含 有多条相同的边。
那所谓的相同边呢也就是 它们共有相同的这个连接的结点，是吧？
最后呢，我们来看看这个边和结点之间的关系。
顶点呢，或者叫做结点，它的集合只要是一个非空集就可以了，这个没有什么太多的讲究。
但是对于边来说，就有讲究了，那么边呢有分为 有方向的边，从一个结点到另外一个结点，有方向的，
和没有方向的边，就是只是连接两个结点，表示这两个结点之间有关联，
这么一个边，那么所以区分出这两个来呢，我们就来看看它们之间这个定义的差别。
首先呢是叫做有向边，那么有向边如何来表示呢？ 那既然它有顺序，那么我们就请出我们的这个有序结构。
有序结构呢就是二元有序组，那么有向边呢就是用结点的二元有序组来表示的。
我们把第一分量称之为起点， 第一分量呢每一个分量都是结点，那么第一分量就称作为起点。
把第二分量呢称作为终点，那么这个呢就是表示一条有向边。
如果是无向边的话，那么这两个结点之间的地位呢它就无所谓起点或者终点了，它们是平等的。
那么所以呢我们可以用结点的两元素的多重集来表示。
那么无向边如果是，可以是一个多重集，
那么也就是说这个结点在这个集合里是重复的，比如说一个结点1，1号结点到1号结点
那么如果它能够构成一个无向边的话，那就说明
我们允许在这个图里头有一个结点到自身的一个环， 叫做无向环。
那么这样呢， 我们就有了两大类的边，一个是有向边，一个是无向边。
我们把这个只包含有有向边的这种 图就称作有向图。
反过来，如果图里头全都是无向边的话， 那么就称作为无向图。
那么我们把这个 无向边的这个两边这个地位平等的端点就称作为不再像有向边那样，
称作为起点或者终点了。
我们就把这个端点呢就称作为是两个邻接的结点， 邻接的结点。
我们来看看两个图的例子，左边这个呢是无向图，右边呢是有向图。
它们的这个V是一样的，都是a,b,c三个元素， 但是呢这个E不一样，就是它的边集是不一样的。
在这个左边这个无向图里边， 它有这个无向边，有四条无向边，
有a,c，然后呢再有一个相同的a,c，所以呢它这两条边呢，我们可以
后面会定义它称作为平行的边，是一样的，所以呢它在
边集这里头它是一个多重集，是一个双重集合，都是a,c，我们可以看到有两个a,c。
然后呢第三条边呢是b,c，第四条边呢是c的自身的一个环。
所以呢它是c,c放进去，那么同样呢，它是一个 二重集，有一个两重集，两个都是c。
当然这样的一个表示方法来表示集合肯定是不标准的，当然我们可以从另外
一个刚才我们说的，给这个元素附加一个重数这么一个属性， 来避免说产生这种不合格的集合。
那么右边， 这个有向图，那么就清晰得多了。
它V呢同样还是a,b,c。
但是它这个E，这个边呢有从a到c的，所以呢a,c这样的一个有序组。
然后还有从c到a的，就是c,a这么一个有序组。
然后有b,c 然后呢还有c到自身的这个环，这个是有一个有向环，所以呢它是c,c的有序组。
当然c,c这个有序组呢，是完全没有问题的，它并不涉及到多重集合问题。
因为它是一个二元有序组，对吧？所以呢右边这个是一个有向图，
而且呢它是没有多重边，也是有一个有向环的这么一个有向图。
左边呢它是一个带有多重边和自身环的一个无向图。
这就是我们举的两个图的例子。
陈斌副教授
