图的基本概念

有向图与无向图

 

完全图

 

图的定义与术语

 

度

无向图的度就是边的个数
有向图的入度是: 进来的弧的个数
有向图的出度是: 出去的弧的个数
有向图的度为: 入度加出度



 

路径、简单路径、回路、简单回路

路径：假如 a1 到 a4，那么路径为 a1,a3,a4
路径长度: 假如不是网，没有权值,那么a1到a4的长度就是a1到a4弧的个数为2
如果是网，有权值，假如a1到a3的权值为10，a3到a4的权值为15，那么a1到a4的长度为a1到a3的权值+a3到a4权值的和=25

简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径
回路：第一个顶点和最后一个顶点相同的路径
简单回路：除路径起点和终点相同外，其余顶点均不相同的路径<路径起点和路径终点必须相同>

简单路径与回路的区别
<1,2,3,3,2,1>
虽然它的起点和终点相同，但它有重复定顶点
所以这是一条回路，但不是一条简单路径

简单路径与简单回路的区别
简单路径从概念上包含简单回路，
它们最主要的区别就是简单路径起点和终点可以不同,但简单回路的起点和终点必须相同

连通图

G = (V,{E})
V: 顶点的集合
E: 边的集合

 

权与网

子图

 

连通分量

强连通分量

 

极小连通子图、生成树、生成森林

 

案例引入