图论

基础

是什么

是数学的一个分支,叫几何拓扑学;

以图为研究对象;

由若干给定的点以及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定的关系;用点代表事物,用两点之间的连线表示相应的两个事物间具有的关系;

图=二元组(顶点集V,边集E).

术语

阶: 顶点个数(V);

无向图与有向图: 边(u,v)与弧<u,v>,入边与出边;

邻接: 两个顶点的邻接与非邻接;

度: 入度与出度;

奇点与偶点: 无向图中顶点度的奇偶性;

自环: 若一天边的两个顶点为同一顶点.

路径: (字面意义)

回路: 环(起点终点重合)

简单图: 没有环,没有多重边

连通: 从顶点x到顶点y有路径相连

连通图: 无向图的任意两个顶点都是连通的

强连通图: 有向图的任意两个顶点都有互相到达的路径*(不管方向与边)*

带权图: 权的含义

最短路: 从x到y具有的最小长度(长度包含路径上的所有边权之和)

二分图: 一个图的顶点集可以划分为两个非空子集.

满足每一条边都有一个顶点在x中,而另一个顶点在y中

图形分类

1.完全图

  • 每一对顶点间都有边相连.

  • 总变数为n*(n-1)/2;n=顶点数

2.稀疏图与稠密图

  • 稠密图,接近于完全图
  • 稀疏图,有很多点,但是没有几条边
  1. 子图

    • 取出若干顶点和边构成的新图
  2. 补图

    • 图中所有的顶点和所有能使该图成为完全图的添加边 所组成的图
  3. 逆图

    • 把一个有向图的每条边都反向得到的有向图

问题类型

① 欧拉回路问题(一笔画);

有0个或2个奇点就可以一笔画;

0个奇点起点终点重合;

2个奇点能画完,但起点终点不重合; 否则不行.

应用

很多题目可以转化为一张图来做.

存储结构

① 邻接矩阵

定义A[n][n]

A[i][j]用来表示两个顶点之间的权数(长度).

同时记录权值

适用于稠密图.

② 边集数组

开二维数组.

同时记录起点,中点与权值(A[n][3])

适用于稀疏图.

③ 邻接表

开结构体与用结构体存储的vector.

同时记录起点,中点,权数与指针.

适用于稀疏图.

④ 链式向前星

这是一种特殊的边集数组,在边集数组的基础上将每一条边按照起点从小到大排序(,如果起点相同就按终点).

同时记录