咱们开始先看一个著名的格斯堡七桥问题：

能否从任一陆地出发通过每座桥恰好一次而回到出发点？

你要是自己做过，就会显而易见的发现这道题是没有答案的（遵守规则以及图形规定的情况下）

欧拉就这个问题说过：如果每块陆地所连接的桥都是偶数座，则从任一陆地出发，必能通过每座桥恰好一次而回到出发地。

经过此次引导我们回到图论的基本概念

首先先看图论的定义：

一个有序二元组(V,E)称为一个图,记为G= (V,E)

其中：

①V或V(G)称为G的顶点集,其元素称为顶点或结点,简称点;

②E或E(G)称为G的边集,其元素称为边,它联结V中的两个点,如果这两个点是无序的,则称该边为无向边,否则,称为有向边.

tip:可以用|V|或者|E|表示图G的定点数和边数

且如果V= {v1,v2, … ,vn}是有限非空点集,则称G为有限图或n阶图.

如果E的每一条边都是无向边,则称G为无向图

如果E的每一条边都是有向边,则称G为有向图;

否则,称G为混合图.

可以参考一下图形实例

如图，左图为无向图，右图为有向图

记E= {e1,e2, … ,em}(e(k)=v(i)v(j)).

但在之后学习的过程中，你最后可能会找到一些不一样的图，但最终的话图解是相同的

例如以下的图：

为了方便处理，我没有在上面进行标号端点，但实际上两个图虽然看上去不一样，但实际图解是相同的

这就可以衍生到之前说过的

对于一个图G= (V,E),人们常用图形来表示它,称其为图解.

凡是有向边,在图解上都用箭头标明其方向.

一个图会有许多外形不同的图解，它们之间称做同构，如图G同构图H记作G~=H

那么我们接下来：(都是一些最基本的概念理论，可能有一点枯燥)

称点v(i),v(j)为边v(i)v(j)的端点.

在有向图中:

称点v(i),v(j)分别为边v(i)v(j)的始点和终点.

称边v(i)v(j)为v(i)的出边,v(j)的入边.

称v(j)是v(j)的后继或子顶点，称v(i)是v(j)的前驱或父顶点。

有边联结的两个点称为相邻顶点,

有一个公共端点的边称为相邻边.

边和它的端点称为互相关联.

有向图中的关联又分出关联和入关联。

常用d(v)表示图G中与顶点v关联的边的数目,

d(v)称为顶点v的度数.

与顶点v出关联的边的数目称为出度，记作d+(v),

与顶点v入关联的边的数目称为入度，记作d-(v)。

用N(v)表示图G中所有与顶点v相邻的顶点的集合.

两个端点重合的边称为环。

无向图中有相同端点的边称为平行边,

有向图中有相同的头与尾的边称为平行边。

没有关联边的顶点称为孤立点。

恰有一条关联边的顶点称为悬点，

与悬点关联的的边称为悬边。

tip:在计算与顶点关联的边时，环算作两条边

有向图G略去边的方向，得到一个无向图，此时这份新的图称为图G的基础图。

有n个顶点m条边的图称为(n,m)图。

（n,0）图叫零图。（1,0）图叫平凡图

没有环与平行边的图称为简单图.

任意两顶点都相临的简单图称为完全图.

有n个顶点的完全图记为Kn

tip:若顶点V(G)能分解成两个不相交的子集V(1)和V(2),即V(2)并V(2)为V，V(1)交V(2)=空

且V(i)自身的顶点不相邻，则称G为偶图（两部图）。

而不在同一顶点子集的任意两个顶点都相邻的简单偶图就被称为完全偶图

那么接下来大家可以靠图论的知识解决狼羊渡河问题（虽说心算也可以）：

但这可以说是入门级别的图论应用之一了：

一摆渡人欲将一只狼，一头羊，一篮菜从河西渡过河到河东，由于船小，一次只能带一物过河，并且，狼与羊，羊与菜不能独处，给出渡河方法。

用四维0-1向量表示（人，狼，羊，菜）的在西岸状态，（在西岸则分量取1，否则取0.）

共=16种状态，

由题设，状态（0,1,1,0）,(0,0,1,1),(0,1,1,1)是不允许的，

从而对应状态（1,0,0,1），(1,1,0,0),(1,0,0,0)也是不允许的，

以十个向量作为顶点，将可能互相转移的状态连线，则得10个顶点的偶图。

那么此题就不过多赘述了；

若将图G的每一条边e都对应一个实数F(e), 则称F(e)为该边的权, 并称图G为赋权图(网络), 记为

G= (V,E,F).

设G= (V,E)是一个图,v0,v1, … ,vk∈V, 且“1≤i≤k,vi-1vi∈E, 则称v0v1 …vk是G的一条通路.称为v0-vk通路.称其长为k，起点与终点重合的通路称为闭通路，不重合的称为开通路。

如果通路中没有相同的边, 则称此通路为道路.(迹)

如果通路中没有相同的顶点, 则称此通路为路径, 简称路.

始点和终点相同的路称为圈或回路.

有向图中边的方向与通路，道路，路的方向一致。

顶点u与v称为连通的，如果存在u-v通路，任二顶点都连通的图称为连通图，否则，称为不连图。

极大连通子图称为连通支。

连通而无圈的图称为树, 常用T表示树.

树中最长路的长称为树的高

树的度为1的顶点称为树叶。

其余的顶点称为分枝点。树的边称为树枝。

设G是有向图，如果G的基础图是树，则称G是有向树，也简称树：

设T是有向树，若存在顶点v0可达其余的每一顶点，则称T为外向树，v0为始根。若存在顶点v0，其余的每一顶点都可达v0，则称T为内向树，v0，为终根。外向树与内向树统称为有根树。

设G是有向图，如果G的基础图是树，则称G是有向树，也简称树。

设T是有向树，若存在顶点v0可达其余的每一顶点，则称T为外向树，v0为始根。若存在顶点v0，其余的每一顶点都可达v0，则称T为内向树，v0为终根。外向树与内向树统称为有根树。

图的矩阵表示 ：⑴ 邻接矩阵 )n×n

以下为例题：

答案：

⑵ 权矩阵A= (aij)n×n

例题如下：

答案：

⑶ 关联矩阵A= (aij)n×m：

有向图：

无向图：

今天的笔记就到这里了，下期再见，拜拜