图论基础
图是怎么存的？¶
直接存边¶
什么意思呢？我们开一个数组，数组里每个元素是图的一条边。
这样做有个缺点，每次想要知道两个点之间是否有连边（或者说一条边是否存在），都需要在数组里进行一番查找。而且如果没有对边事先排序的话，就不能使用二分查找的方法（ ），而是每次只能按顺序找（ ），成本较高。
什么时候会用到这个方法呢？最简单的一个例子是使用 Kruskal 算法求最小生成树的时候。
邻接矩阵¶
邻接矩阵的英文名是 adjacency matrix。它的形式是 bool adj[n][n] ，这里面 是节点个数， 表示 和 之间是否有边。
如果边有权值，也可以直接用 int adj[n][n] ，直接把边权存进去。
它的优点是可以在 时间内得到一条边是否存在，缺点是需要占用 的空间。对于一个稀疏的图（边相对于点数的平方比较少）来说，用邻接矩阵来存的话，成本偏高。
邻接表¶
邻接表英文名是 adjacency list。它的形式是 vector adj[n] ，用 adj[i] 存以 为起点的边。
用 vector 无法科学地删除，所以常用 list 实现。
它的特点是可以用来按顺序访问一个结点的出边（或者入边）。
前向星¶
为什么它搜不到英文名呢？因为是中国玩家乱搞出来的。
首先介绍一下链式前向星，本质上是用单向链表实现的邻接表。
形式上是一个结构体： struct edge {edge *pre, int to;} *head[N], edge[M]
这个结构广泛出现于算法竞赛选手的代码中，编写简洁而且对于大多数题目效率足够高。
其中 head[i] 用来存以 为起点的边， edge 数组是边表。
那么什么是前向星呢？事先把 edge 数组排个序即可。这里可以使用基数排序做到 。
图的基本概念¶
路径¶
path，是指一个边的序列，其中的边首尾相连。
简单路径¶
simple path，是每条边只经过了一次的路径。
回路¶
cycle，也称为 环 ，是起点和终点相同的路径。
简单回路¶
图的定点序列中，除了起点和终点相同外，其余顶点不重复的回路。
可达¶
有向图中点 到 可达是指存在一条 到 的路径。
连通¶
两个点连通¶
图中点 和 连通是指两点互相可达。
图连通¶
如果无向图 中任意两个节点连通，称其为是连通的。
强连通¶
有向图 强连通是指， 中任意两个节点连通。
弱连通¶
有向图 弱连通是指， 中的所有边替换为无向边后， 为连通图。
点连通度¶
一张图的点连通度的大小等于最小点割集的大小。
边连通度¶
一张图的边连通度的大小等于最小边割集的大小。
子图¶
选取一个节点的子集和边的子集构成的图。
生成子图¶
选取的子图的节点和原图一样。
导出子图¶
选取一个节点的子集，再选取这些节点相关联的边的集合构成的图。
边导出子图¶
选取一个边的子集，再选取这些边相关联的节点的集合，构成的图。
连通子图¶
（一个无向图的）连通的子图。
连通分量¶
（一个无向图的）极大的连通子图。
【注】：极大是指添加任何节点或者边后都不再满足。
稀疏图¶
的图，或者指 相对较小的图。
稠密图¶
的图，或者指 相对较大的图。
完全图¶
设 为 阶无向简单图，弱 中每个顶点均与其余的 个顶点相邻，则称 为 阶无向完全图。
无向完全图的点数和边数满足这样的关系： 。
设 为 阶有向简单图，若对于任意的 ，有向边 和 均属于 ，则称 为 阶有向完全图。
竞赛图¶
设 为 阶有向简单图，若对于任意的 ，有向边 和 中有且仅有一个属于 ，则称 为 阶竞赛图。
正则图¶
各顶点的度均相同的无向简单图。
路径的长度¶
一般来说，路径的长度在数值上等于路径的边数，或者如果边是带权的，则是路径的边权和。
最短路径¶
两个节点之间，长度最小的路径。
【注】：不一定存在，不一定唯一。
图论基本定理¶
又称握手定理。设 为一个无向图， ，则 。其中 表示 v 的度数。
可图化¶
如果给定一个序列 a，可以找到一个图 G，以其为度数列，则称 a 是可图化的。
如果给定一个序列 a，可以找到一个简单图 G，以其为度数列，则称 a 是可简单图化的。
判别法¶
可图化当且仅当
可简单图化当且仅当 是可简单图化的。
Whitney 定理¶
对任意的图 ，有 。其中 分别为 的点连通度，边连通度和最小度。
build本页面最近更新：，更新历史
edit发现错误？想一起完善？ 在 GitHub 上编辑此页！
people本页面贡献者：
copyright本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用