学习目标：
理解图的基本概念
各种图的定义
图的顶点与边的关系
连通图的介绍
学习内容：
👁🗨👁🗨1. 图的基本概念
1.1
图（Graph）是由顶点的有穷非空集合和顶点之间边的集合组成。
1.2
通常表示为G（V,E） ，G表示一个图，V是图G中顶点的集合，E是图G中边的集合。
1.3
线性表中把数据元素叫元素，树中将数据元素叫结点，在图中数据元素叫做顶点。
1.4
在线性表中可以没有数据元素，称为空表。
树中可以没有结点，称之为空树。
但是在图中不能没有顶点。这在定义中也有体现：V是顶点的有穷非空集合。
1.5
在线性表中相邻的数据元素之间具有线性关系。
在树的结构中，相邻两层的结点具有层次关系。
在图中，任意两个顶点之间都有可能有关系，顶点之间的逻辑关系用边来表示，边集可以是空集。
👁🗨👁🗨2. 各种图的定义
2.1
无向边：顶点vi 到vj 之间的边没有方向，则这条边为无向边，用无序偶对（vi，vj）来表示。
2.2
无向图：如果图中任意两个顶点之间的边都是无向边，则该图称为无向图。
如图下图所示：
从A到D的边是无向边，所以可以表示成无序对（A,D）或者·（D,A）。
2.3
有向边：从顶点vi到vj 的边有方向，则称这条为有向边，也·称为弧。用有序偶<vi.vj> 来表示，vi称为弧尾（tail），vj称为弧头（head）。
2.4
有向图：图中任意两个顶点之间的边都是有向边，则称图为有向图。
如下图所示：
从A到B的边就是有向边（弧），A是弧尾 B是弧头。<A,B>表示弧。（不能写成<B，A>）
2.5
无向完全图：在无向图中，如果任意两个顶点之间都存在边，则称为无向完全图。（也就是每个顶点除了它自身之外都要有一条边与其它顶点相连）
如下图所示：
含有n个顶点的无向完全图有n*(n-1)/2 个边。
上图也就是有43/2 =6 条边。
2.6
有向完全图：在有向图中，如何任意两个顶点之间都存在方向互为相反的两条弧，则称为有向完全图。
如下图所示：
其中含有n个顶点的有向完全图有n(n-1) 条边。
得出结论：
对于n个顶点和e条边数的图
无向图—0<=e<=n(n-1)/2
有向图—0<=e<=n*(n-1)
2.7
稠密图与稀疏图：
稠密图—有很多条边或弧的图
稀疏图—有很少条边或弧的图
这里稀疏图和稠密图的概念是相对而言的。
2.8
网：带权的图称为网
带权指的是图的边或者弧具有与它相关的数字
如下图所示：
2.9
子图：假设有两个图G=（v,{e}）和G1=（v1,{e1}），如果v1属于而且e1属于e，则称G1是G的子图。
如下图所示：右边的图都是左边图的子图
👁🗨👁🗨3. 图的顶点与边的关系
3.1
对于无向图G=（v,{E}），如果存在边（v,v1）属于E，则顶点v与v1互为邻接点，边（v,v1）依附于顶点v和v1，或者是（v,v1）与顶点v，v1相关联。
顶点v的度是和v相关联的边的数目，记为TD(v）。
通过以上面的图，我们可以不难发现各个顶点的度之和=所以边数之和*2
3.2
对于有向图G=（v,{E}），如果弧<v,v1>属于E，则称则顶点v邻接到顶点v1，顶点v1邻接自顶点v。弧<v,v1>和顶点v，v1相关联。
以顶点v为头的弧的数目称为v的入度，记为ID(V)；
以顶点v为尾的弧的数目称为v的出度，记为OD(V);
所以顶点v的度为出度+入度，即TD(V)=ID(V)+OD(V)；
3.3
在树中根结点到任意结点的路径是唯一的，但是图中顶点与顶点之间的路径却不是唯一的。
3.3.1 路径的长度：是路径上的边或弧的数目之和。
3.3.2 回路/环： 第一个顶点到最后一个顶点相同的路径。
3.3.3 简单路径：序列中顶点不重复出现的路径。
3.3.4 简单回路/简单环：除了第一个顶点和最后一个顶点之外，其余顶点都不重复出现的回路。
👁🗨👁🗨4. 连通图的基本概念
4.1连通图：在无向图中，如果从顶点v到顶点v1有路径，则称为v和v1是连通的。如果图中任意两个顶点vi,vj 属于E，vi和vj都是连通的。则称图G是连通图。
如下图所示就是一个连通图：
如下图所示，就不是连通图，
因为，中间的两个顶点和外面的四个顶点都互不相连。
4.2 连通分量
无向图中的极大连通子图称为连通分量。
连通分量强调：
1.是子图
2.子图要是连通的
3.连通子图有极大顶点数
4.具有极大顶点数的连通子图包含依附于这些顶点的所有边
4.3 强连通图
在有向图G中，如果对于每一对vi，vj属于V，vi不等于vj，从vi到vj和从vj到vi都存在路径，则G是强连通图.
有向图的极大强连通子图称为有向图的强连通分量。
上面这个图就不是强连通图，因为在A和D之间，D到A就没有路径。
此图就是强连通图，它是上一个图的极大强连通子图，即是它的强连通分量。
4.4 无向图中连通且n个顶点n-1条边叫生成树。
有向图中一顶点入度为0其余顶点入度为·1的叫做有向树。
一个有向图由若干棵有向树构成生成森林。
