图

https://www.bilibili.com/video/BV1hg411V7Bm?p=62

1）图的分类

完全图

在无向图中，若每对顶点之间都有一条边相连，则称该图为完全图。

无向图完全图

在有向图中，若每对顶点之间都有两条有向边相连接，则称该图为完全图。

有向图完全图

问题：n个顶点的无向图和有向图的完全图的边的个数为多少？

无向图

n个顶点：

顶点编号	边统计	参与的边
1	顶点1和顶点2 顶点1和顶点3 顶点1和顶点4 …… 顶点1和顶点n	n-1
2	顶点2和顶点3 顶点2和顶点4 …… 顶点2和顶点3 顶点2和顶点n	n-2
n-1	顶点n-1和顶点n	1
n	0

n-1，n-2，……，1，0

等差数列求和：(n-1+0)×n÷2=(n-1)×n÷2

有向图：

参考无线图，因为有向图两个顶点之间的线是两条，所以就是(n-1)×n

连通图

连通图：指任意两个顶点之间都有一个路径相连。

连通图与完全图不同的是：完全图中，任意两个顶点一定有至少一条边直接相连；而连通图中两个顶点之间的路径可以是间接相连的。

在有向图中，如果可以直接满足任意两个顶点之间都有一个路径相连的条件的叫做强连通图；如果不计较方向可以直接满足任意两个顶点之间都有一个路径相连的条件的叫做弱连通图。

2）图的转换：无向图转邻接矩阵

用一个n阶方阵R来存放图中各结点的关联信息，其矩阵元素R_ij定义为：

比如

矩阵R₁中R₁₂=1就表示顶点1到顶点2的边；

矩阵R₁中R₂₁=1就表示顶点2到顶点1的边（和R₁₂描述的是同一条边）；

矩阵R₁中R₂₅=0就表示顶点2到顶点5的没有路径，没有边；

无向图转换的邻接矩阵为对称矩阵。

满足R_ij=R_ji的矩阵叫做对称矩阵。

出度：看行，一个顶点连到其他顶点

入度：看列，其他顶点连到当前顶点

https://www.bilibili.com/video/BV1hg411V7Bm?p=63

2）图的转换：有向图转邻接矩阵

与有向图的转换方式相同。

有向图中，一个顶点指向另一个顶点的边又叫做弧；

R_ij=0表示顶点i到顶点j没有弧的存在；

R_ij=1表示顶点i到顶点j有弧的存在；

有向图中度分入度和出度：其他顶点指向自己的弧的和自己指向其他顶点的弧；

比如顶点V₁，看第1行，有6、1、50，我们就说顶点V₁的出度为3；看第1列，没有有效值，我们就说顶点V₁的入度为0。

再比如顶点V₅，看第5行，有38、24，我们就说顶点V₅的出度为2；看第5列，有6、12、1，我们就说顶点V₅的入度为3。