1、支配集：
设D集合是无向图G的一个顶点子集，对于G中的任意顶点u，要么在D里，要么与D集合的一个顶点相邻，那么称我们集合D的G的一个支配集。如果去掉D中任何一个顶点，D不在是支配集，则支配集是极小支配集。G中所有支配集中顶点个数最小的支配集称为最小支配集，即是极小支配集。最小支配集的顶点个数为支配数。
2、独立集：
设I集合无向图G的一个顶点子集，对于集合I中任意两点都不相邻，则我们称集合I为G的一个独立集。如果在I中加入一个非I集合的顶点后，I集合不在是独立集，则称集合I为极大独立集。G中所有独立集中顶点个数最多的独立集称为最大独立集，即是极大独立集。最大独立集的顶点个数为独立数。
3、覆盖集：
设K集合是无向图G的一个顶点子集，对于G中的任意一条边e，至少有一个端点属于K，那么我们称集合K是G的一个覆盖集。如果去掉K中的任意一个顶点，K不在是覆盖集，则称集合K是极小覆盖集。在G中所有覆盖集中顶点个数最少的覆盖集称为最小覆盖集。即是极大覆盖集。最小覆盖集的顶点个数为覆盖数。
4、网络流：
a、网络与流：
网络D=(V,A,C）
设D是一个简单有向图，V是顶点集，A是边集，C弧容量集。
网络流F
F(i,j)=集合A上的一个函数，为弧(vi,vj)的流量。