图论入门
图论是计机算算法中很重要的一种思想，很多的实际问题都可以通过图论建模来解决。本文先介绍基本的图论相关知识，为后续讲解具体的图论算法做铺垫，如最大匹配，最小生成树，最短路，网络流，差分约束，拓扑序等。
图定义
图的表示：G=(V,E), V=(v|v为图中的顶点)， E=(e|e为图中的边)
如下图：点集V：a,b,c,d,e，边集E：1，2，3，4，5
分类
可分为有向图和无向图
存储
分邻接矩阵和邻接表：
邻接矩阵，一般用二维数组实现，对于不带权的图，也可以用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];
简单图与多重图
无向图中，关联一对顶点的边多于一条，称为平行边。有向图中，关联一对顶点的边多于一条，且方向相同，也称为平行边。
多重图：含平行边或自环边的图。
简单图：既不含平行边，也不含自环边。
完全图
每对顶点之间都恰有一条边的简单图，n个顶点的完全图，共有n(n-1)/2条边。
独立集
独立集：图中两两互不相邻的顶点构成的集合，为图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]
团
团：图G的一个完全子图。
极大团：图的一个团，且不是其他任一团的真子集。
最大团：顶点数最多的团。
如下图：
团：[a,b],[a,d],[c,d],[c,e],[d,e],[c,d,e]
极大团：[a,b],[a,d],[c,d,e]
最大团：[c,d,e]
补图
定义：图G的完全图去除G的边集后得到的图。
最大独立集与最大团
独立集是任意两点不相邻，而团是任意两点相邻。图G的补图是去掉了相连的边，添加不相邻的边。这样图G的最大独立集就可以转化成补图的最大团。
如下图：
连通图
图中从一个顶点到达另一顶点，若存在至少一条路径，则称这两个顶点是连通的。
无向图中，如果任意两个顶点之间都能够连通，则称此无向图为连通图。
无向图G的一个极大连通子图称为G的一个连通分量。
有向图中，如果任意两个顶点之间都存在路径，则称此有向图为强连通图。
有向图的极大强连通子图，称为强连通分量。
n个顶点的强连通图，边数最多为n(n-1)，最少为n。
二分图
定义：设G=(V,E)是一个无向图，顶点集V可分割为两个互不相交的子集，并且图中每条边关联的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻。
充要条件：G至少有两个顶点,且其所有回路的长度均为偶数。
判断方法：染色法
开始对任意一未染色的顶点染色
判断其相邻的顶点中，若未染色则将其染上和相邻顶点不同的颜色；
若已经染色且颜色和相邻顶点的颜色相同则说明不是二分图，若颜色不同则继续判断
可用bfs或者dfs。
- EOF -
觉得本文有帮助？请分享给更多人
推荐关注「算法爱好者」，修炼编程内功
点赞和在看就是最大的支持❤️