1.图的定义
- 图（graph）由顶点集V（Vertex）和边集E（Edge）组成，记为G = （V，E）
- 图（顶点集）不能为空，但是图的边集可以为空
2.有向图
边带方向，E = <v, w>：使用<>表示，v为弧尾，w为弧头
E = {<1, 2> <2, 1> <2, 3>}
3.无向图
边不带方向，E = (v, w)：使用()表示，v和w的元素可以互换
E = {(1,2) (1,3) (1,4) (2,3) (2,4) (3,4)}
4.简单图、多重图、完全图
- 不存在重复边
- 不存在顶点到自己的边
满足1、2条件为简单图，反之则为多重图；如果任意两个顶点之间都存在边，则为完全图，共n(n-1)/2条边
，（有向图中，则需要任意两个顶点中都存在方向相反的两条边，共n(n-1)条边
）
5.顶点的度、入度和出度
无向图——度：
- 度为该顶点的边数
- 无向图的度的总数为2倍边数（2E）：一条边为两个顶点的度数分别+1
有向图——入度、出度：
- 入度：指向该顶点的边数（终点为该顶点）记为ID(v)
- 出度：指出该顶点的边数（起点为该顶点）记为OD(v)
- 有向图中的入度=出度=边数（E）：每有一条边，一个顶点的入度+1，另一个顶点的出度+1
6.路径、回路、路径长度
路径：一个顶点到另一个顶点的顶点序列
路径长度：路径上经过的边的数量
点到点的距离：如果一个顶点到另一个顶点的最短路径存在，则为两点之间的距离；如果不存在，则该距离为无穷
回路：第一个顶点和最后一个顶点相同的路径（环）
简单路径：路径中不存在重复出现的顶点
简单回路：除了第一个顶点和最后一个顶点外，回路中没有重复出现其他顶点
7.连通、强连通
无向图——连通：
- 两个顶点之间路径存在，则这两个顶点连通
- 如果整个无向图中任意两个顶点都是连通的，则为连通图
- n个顶点的无向图G：
- 若G为连通图，最少为n - 1条边
- 若G为非连通图，最多为
条边
有向图——强连通：
- 顶点a到顶点b路径存在，且顶点b到顶点a路径存在，则这两个顶点强连通
- 如果整个有向图中任意两个顶点都是强连通的，则为强连通图
- n个顶点的有向图G：若G为强连通图，最少为n条边（构成回路）
8.子图、生成子图
设有两个图G = (V, E)和G1 = (V1, E1)，若V1是V的子集，E1是E的子集，则G1是G的子图；当V1和V1相等时，G1为G的生成子图（E未必相等）
9.连通分量、强连通分量
- 无向图中极大连通子图为连通分量：子图必须连通、且包含尽可能多的边和顶点
- 有向图中极大强连通子图为强连通分量：子图必须强连通、且包含尽可能多的边和顶点
10.生成树、生成森林
连通图中，包含图中全部顶点的极小连通子图：边尽可能少，但是是连通的
非连通图中，连通分量的生成树组合而成生成森林
11.边的权、带权图
边的权：边上带有某种意义的数值
带权图：边上带有权值的图
带权路径长度：一条路径上所有边的权值之和
