图论入门基础

文章首先于微信公众号：几何思维，关注第一时间获取更新信息

图论是计机算算法中很重要的一种思想，很多的实际问题都可以通过图论建模来解决。本文先介绍基本的图论相关知识，为后续讲解具体的图论算法做铺垫，如最大匹配，最小生成树，最短路，网络流，差分约束，拓扑序等。

1 图定义

图的表示：G=(V,E), V=(v|v为图中的顶点)， E=(e|e为图中的边)
如下图：点集V：a,b,c,d,e，边集E：1，2，3，4，5

2 分类

可分为有向图和无向图

3 存储

分邻接矩阵和邻接表：

邻接矩阵，一般用二维数组实现，对于不带权的图，也可以用n(row)个m(column)位二进制数来表示；
空间由点决定，适用点少、边多的稠密图
邻接表，一般用链表实现；
空间由边决定，适用边少、点多的稀疏图

如上图中，无向图用邻接矩阵存储，有向图用邻接表存储。

变量定义

// 邻接矩阵
int map[100][100];

// 邻接表
struct ENode{
    int adjvex;
    int weight;
    ENode *next;
}

struct VNode{
    int vertex;
    ENode *edge;
}

VNode adjList[100];

4 简单图与多重图

无向图中，关联一对顶点的边多于一条，称为平行边。有向图中，关联一对顶点的边多于一条，且方向相同，也称为平行边。
多重图：含平行边或自环边的图。
简单图：既不含平行边，也不含自环边。

5 完全图

每对顶点之间都恰有一条边的简单图，n个顶点的完全图，共有n(n-1)/2条边。

6 独立集

独立集：图中两两互不相邻的顶点构成的集合，为图G的顶点集的子集。
极大独立集：图的一个独立集，且不是其他任一独立集的真子集。
最大独立集：顶点数最多的独立集。顶点个数称为图G的独立数，记为α(G)。
如下图：
独立集：[a,c],[a,e],[b,c],[b,e],[b,d],[c,e],[a,c,e],[b,c,e]
极大独立集：[b,d]，加入任何点都无法构成独立集；而[a,c]不是极大独立集，还可以加入e构成更大的独立集[a,c,e]
最大独立集：[a,c,e],[b,c,e]