第5部分  图论

前言：图是我们日常生活中一个很常见的概念，我们学习时会画思维导图，思维导图有节点，有路线；生活中会用到地图导航，有起点有终点有路线。而图论中的图便是生活中以及数学中具象事物抽象化的体现。

前言的前言：若有错误之处或不完整之处希望指出，虚心接受任何批评和建议！

一. 图的基本概念

一个图可以简单地分成两部分：顶点集和边集。顶点集一般以V表示，边集以E表示，所以一个图G就以<V, E>表示。点是一个图里的最基本元素，一个只由一个点构成的图称为平凡图，点集的笛卡尔积或无序积就是边集，分为有向边和无向边。而边由有向边构成的图称为有向图，无向边构成的图称为无向图。一个点一般用v表示，一条边一般用e表示。下图是有向图和无向图的例子：

概念：

1. 顶点数称作图的阶，n阶图表示这个图有n个顶点。
2. 一条边也没有的图称为零图，n阶零图记作N_n，当n=1时，表示1阶零图，称作平凡图。
3. 空图的概念比较特殊，因为在定义图时规定的顶点集V是非空，而空图是顶点集为空集的图，这不就自相矛盾了吗？其实没有。因为空图是需要特定条件才能产生的。比如在图的运算中产生了空图，这时我们将空图记为∅。所以新规定顶点集为空集的图为空图。
4. 标定图：标定图的定义很宽泛，很多图都可以称为标定图。当用图形表示图时，如果给每个顶点和每一条边指定一个符号（字母或数字或带数字下标的字母），这样的图称为标定图。学过定向越野这门课程的同学可能更好理解，也更好体会。
5. 基图：简单理解成把有向图的边的箭头都去掉。

关于端点和关联次数，以及环：

由于一条边由两个端点相连构成，所以边可以由端点表示：e_k=（v_i，v_j）∈E。此时说e_k与端点关联。如果v_i，v_j不表示同一个点，则称e_k与v_i（v_j）关联次数为1，当关联次数为2时就形成了环。如图所示：

对有向图来说，端点和环与无向边很相似，但是端点多了方向。一条边箭头所指的点叫终点，另一个则叫做始点，类似于导航的起点和终点和方向。

图中没有边关联的顶点称作孤立点。

关于图的领域：

书上是这样写的：

书上没有具体举例，这里我直接拿图，其实用图就很简单理解了：

这里唯一要注意的是有向图的先驱和后继元集，先驱就是所求点作为终点时的元集，后继则是所求点作为始点的元集。

关于重数，度数和平行边：

　　重数指的是平行边的条数，而平行边在有向图和无向图中也有一定区别。

　　对无向图：

　　对有向图：

 　　含平行边的图叫多重图，不含平行边也不含环的图叫做简单图。

　　图中点作为边的端点的次数为该点的度数。

　　对无向图，度数不分出入；

　　对有向图，度数分为出度和入度，出度是点作为边的始点的次数，而入度是点作为终点的次数。出就是从该点出去的意思，入则是该点被指向被进入的点。

（要考试了，先做到这儿，后面的考完再加！）