- 摘要:其实是我的备忘录
- G=（V,E）其中G是图，V是图中顶点，E是图中边。
- 顶点的入边条数称为该项点的入度。
- 顶点的出边条数称为该顶点的出度。
-
点基：一个点集B，使得B中的顶点可以到达任意其他顶点，称B为图的点基。
-
最小点基：顶点最少的点基。
-
最小权点基：顶点对应的权值之和最小的点基。（顶点权值非负）
- 有向图强连通分量：在有向图G中，如果两个顶点vi,vj间（vi>vj）有一条从vi到vj的有向路径，同时还有一条从vj到vi的有向路径，则称两个顶点强连通。如果有向图G的每两个顶点都强连通，称G是一个强连通图。有向图的极大强连通子图，称为强连通分量。
- 最高强连通分量：最高强连通分支就是入度为0的强连通分量。
-
最小点覆盖：对于图G=(V,E)中的一个点覆盖是一个集合S⊆V使得每一条边至少有一个端点在S中。 二分图：最大匹配
最小边覆盖：使该图上每一节点都与这个边子集中的一条边关联 二分图：n-最大匹配
最小路径覆盖：选n条路径 覆盖所有点 对DAG可转换为二分图上的n-最大匹配 不可相交路径：若有边x->y 将x1连向y2 即拆点保证路径不重复 可相交路径：如果x->y有路径 将x1连向y2
最大独立集：选n个点 两两之间没有边 二分图:n-最大匹配 一般图：补图的最大团
最大团:NP完全问题 模拟退火
最大权闭合子图： 最大权闭合子图指选择u，则u以下关系的都要选，一定要选到底，不能跳过u选它以下的。增设一个超级源点和一个超级汇点，（1->n）的点中，当点权为正时，从源点向该点连一条权值为点权大小的边，当点权为负时，从该点连一条权值大小为它的绝对值的边连向汇点。这种问题一般都是对于（u，v），如果选择u必须选择v，对（u，v）连一条容量为oo的边。 答案数等于靠近源点最小割一边的点数，最大利益=所有点正权值之和-最小割。 对于一个图，我们可能会有多种割法得到的最大权封闭子图的价值相等。
求所得最大权子图中的所有点：遍历源点能到达所有点，能遍历到说明其点在子图中，什么叫能遍历到呢？就是检查残余网络中的边和反向边，若(u,v)边权大于0，则说明u能到达。
这样能遍历到的一定是点数最少的最大权封闭子图
如何求最多能遍历到一种类型的点在最大价值下最多能有多少个呢，比如有梦想和付出，完成梦想可以得到价值，完成付出需要消耗价值，如何求在得到最大价值的情况下最多能得完成多少个梦想呢。
给所有连接到源点汇点的边权乘一个较大的常数，另给连接到源点的梦想的边权加1，这样弄一遍网络流，得到的最大价值除一个较大的常数就是我们需要的价值，源点能到达的梦想就是最大梦想。