图的基本概念思维导图

|V|表示图G的顶点个数，也称图的阶

|E|表示图G中边的条数

边的两头一定各有1个顶点

V一定是非空集，E可以是空集

此时必有(v,w) = (w,v)，其中v、w是顶点

(v,w)是边，可以说w、v互为邻接点；边(v,w)依附于顶点v、w；边(v,w)与v、w相关联

<v,w>未必＝<w,v>，<v,w>是边

v是弧尾，w是弧头，<v,w>称为从顶点v到顶点w的弧，也称v邻接到w，或w邻接到v

不存在重复边

不存在顶点到自身的边

数据结构只讨论这个

G中某两个顶点边数多于1条

又允许顶点通过同一条边和自己关联

无向图全部顶点度的和 = 边数2倍

入度为以顶点v为终点的有向边条数，ID(v)

出度为以顶点v为起点的有向边条数，OD(v)

顶点v的度即为入度与出度之和，即TD(v) = ID(v) + OD(v)

各顶点入度之和 = 各顶点出度之和 = 总边数

顶点v1和顶点v2之间一条路径指顶点序列v1,vi1,vi2,...,v2

第1个顶点和最后1个顶点相同的路径称为回路或环

路径序列中顶点不重复出现的路径

除了第一个顶点和最后一个顶点外，其余顶点不重复出现的回路

路径上边的条数

u到v最短路径若存在，称该路径长度为u到v的距离

若u到v不存在路径，距离为∞

对于n个顶点的图G

若G是连通图，则最少有n-1条边（树），反过来说，若|E|< n -1 必不连通

若G是非连通图，则最多有C(2,n - 1)条边（让其余n-1个结点为完全图）（排序数，上标2下标n-1，知道那意思就行）

n个顶点有向图G，若G强连通，最少n条边（回路）

V'是V的子集，E'是E的子集，则G’是G的子图，必须满足G‘满足图的特性

连通分量：无向图的极大连通子图

强连通分量：有向图的极大强连通子图

连通图的生成树：包含图中全部顶点的极小连通子图

非连通图中连通分量的生成树

带权图一条路径上所有边的权值之和

无向图中任意两点之间都存在边

边数范围[0,n(n-1)/2]

有向图中任意两个顶点都存在方向相反的两条弧

边数范围[0,n(n-1)]

稀疏图的边数远远小于顶点数的平方

无回路且连通的无向图

n个顶点必有n-1条边

若|E| > n - 1必有回路

有向树：一个顶点入度为0，其余顶点入度全为1的有向图

以n=51，m=19为例

51个顶点->51个连通分量->问题转化为添加19条边使连通分量最多：令其接近完全图

7个顶点，21条边构成完全图，故选择7个顶点为其添加19条边使其成为1个连通分量，其余结点自成1个连通分量

共有51 - 7 + 1 = 45个连通分量

首先，邻接矩阵所有的1都集中到对角线以上意味着：i->j，同时i<j，可以利用拓扑排序实现

图各个顶点之间的地位是平等的，因此可以按照需要对图中顶点重新编号