图的基本概念
- 图G是由顶点集V和边集E组成，记为G=（V，E），其中V（G）表示图G中顶点的有限非空集；E（G）表示图G中定点之间的关系（边）的集合。
- |V|表示图G中顶点的个数，也称图G的阶；|E|表示图G中边的条数。
图的分类
无向图：
- 无向边：V——W
- 无序对：（V，W）=（W，V）
v，w互为邻接点 - 表示：V={A，B，C，D}
E={（A，B），（C，D），（B，C），（A，D）}
有向图 - 有向边：V——>W V是弧头，W是弧尾
- 有序对：<V,W>
V邻接到W，或W邻接到V - 表示：V={A，B，C，D}
E={<A，B>，<C，D>，<B，C>，<A，D>}
简单图 - 无重复的边
- 不存在结点到自身的边
多重图 - 存在重复边
- 存在结点到自身的边
稠密图 - 边多 E >V * LogV
稀疏图 - 边少 E<V * LogV
完全图
无向完全图：任意两个顶点之间都存在边。n个顶点有n（n-1）/2条边
有向完全图：任意两个顶点之间都存在方向相反的两条弧。n个顶点有n（n-1）条边
子图 - 设两个图G=(V,E)和G'=(V',E')，若V‘是V的子集，E'是E的子集，则称G’是G的子图。
- 且若V(G)=V(G')则称G'为G的生成子图。
有向树 - 一个顶点的入度为0，其余顶点的入度均为1的有向图。
路径 - 图中顶点V到顶点W的顶点序列，序列中顶点不重复的路径称为简单路径。
路径长度 - 路径上边的数目，若该路径最短则称其为距离。
回路 - 第一个顶点和最后一个顶点相同的路径。
| 区别 | 无向图 | 有向图 |
|---|---|---|
| 连通和强连通 | 连通（若从顶点V到顶点W有路径存在，则称V和W联通） | 强连通（若从顶点V到顶点W和顶点W到顶点V都有路径存在，则称V和W是强连通） |
| 连通图和强连通图 | 连通图（任意连两个结点之间都是连通的）n个顶点的连通图最少有n-1条边 | 强连通图（任意两个结点之间都是强连通的）n个顶点的强连通图最少有n条边 |
| 连通分量和强联通分量 | 连通分量（极大连通子图）包含尽可能多的顶点和边 | 强连通分量（极大强连通子图）包含尽可能多的顶点和边 |
| 顶点的度 | 顶点V的度为以V为端点的边的个数；n个顶点，e条边的无向图中度的总数为2e | 出度：以V为起点的有向边的条数；入度：以V为终点的有向边的条数；度=入度+出度 |
生成树和生成森林
极小连通子图：连通子图且包含的边最少
极小连通子图.JPG
生成树
——连通图 包含全部顶点的极小连通子图
生成树.JPG
生成森林
——非连通图所有连通分量的生成树组成生成森林
生成森林.JPG
