资源描述：
《图论基础与网络流习题集锦.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、图论基础与网络流习题集锦北京大学朱睿大纲图论部分：1.图论简介2.生成树与生成树计数3.欧拉回路与哈密顿回路4.割与流，匹配网络流问题部分：1.习题2.习题3.更多的习题图论简介一个无向图G一般被抽象为一个二元组1.V是一个集合并被称为G的点集。2.E是V的无序积的多重子集，被称为G的边集。其元素被称为无向边。一个有向图D一般被抽象为一个二元组1.V是一个集合并被称为D的点集。2.E是V的卡氏积的多重子集，被称为D的边集。其元素被称为有向边。图的阶：即
2、V
3、。零图：
4、E
5、=0。基图：将D的有向边改为无向边，成
6、为一个无向图。无向完全图：简单无向图中每个点都与其他点相邻。有向完全图：简单有向图中对于任意vi,vj∈V都有∈E且∈E。图论简介平行边：即重边。环：即自环。简单图：不含平行边且不含环的图。度：无向图中，与某点关联的边的数量。入度，出度：有向图中，与某点关联的入边和出边的数量。K-正则图：无向简单图中所有点的度数都为K。握手定理：所有点度数之和等于2*
7、E
8、。同构：两个无向图与，若存在双射函数f:V1->V2，使得对于任意vi,vj∈V1,f(vi),f(vj)∈V2时，<
9、vi,vj>∈E1当且仅当∈E2，则称这两个无向图同构。生成树与生成树计数生成树：一个连通无向图的极小连通子图，被称为这个图的生成树最小生成树：一个边带权的连通无向图的极小连通子图，同时包含最小的边权—Prim算法—Kruskal算法生成树计数问题：如何求出一个连通无向简单图的不重复生成树个数？生成树与生成树计数Matrix-Tree（矩阵树）定理：假设图G是一个包含n个点无向图。定义G的度数矩阵D[G]为一个n*n的矩阵，并且对于任意i≠j，有Dij=0；当i=j时，Dij为节点i的度数。定义G的邻接
10、矩阵A[G]为一个n*n的矩阵，并且对于任意属于G的边集时，Aij为1；否则为0。定义G的Laplace算子(Kirchhoff矩阵)为C[G]=D[G]-A[G]。那么图G的生成树个数为C[G]的任意一个n-1阶主子式（即去掉第r行第r列，r任意）的行列式之绝对值。欧拉回路与哈密顿回路欧拉回路：对于一个连通图，遍历所有边并回到起点的路径被称为是一条欧拉回路。无向图欧拉回路的充要条件：连通并且每个点的度数都为偶数。有向图欧拉回路的充要条件：强连通并且每个点的入度和等于出度和。欧拉回路与哈密顿回路哈密顿回路：遍历图中所有
11、点一次且仅一次并最终回到起点的路径被称为哈密顿回路。哈密顿通路：遍历图中所有点一次且仅一次的路径被称为哈密顿通路。到目前为止，还没有一个简明的条件能作为判断一个图是否存在哈密顿回路的充要条件TT这里给出一个充分条件：若对于无向简单图G，任意两个不相邻点的度数之和大于或等于n-1，则该图存在哈密顿通路。若对于无向简单图G，任意两个不相邻点的度数之和大于或等于n，则该图存在哈密顿回路。割与流，匹配流：假设G(V,E)是一个有限的有向图，它的每条边(u,v)∈E都有一个非负值实数的容量c(u,v)。如果(u,v)不属于E，我们假设c(
12、u,v)=0。我们区别两个顶点：一个源s和一个汇t。一个网络流是一个对于所有结点u和v都有以下特性的实函数f:V×V→R其满足以下三个要求：1.容量限制：f(u,v)<=c(u,v)2.斜对称：f(u,v)=-f(v,u)3.流守恒：除非u=s或u=t，否则Σ(w∈V)f(u,w)=0则该网络流的流量为s的总输出（或t的总输入）割：设Ci为网络N中一些弧的集合，若从N中删去Ci中的所有弧，即：使得从顶点Vs到顶点Vt的路集为空集时，称Ci为Vs和Vt间的一个割。割与流，匹配最大流：从s到t的所有可行的网络流中，流量最大的网络流。
13、最小割：从s到t的割中，删除边权和最小的割。对于一个给定的s和t，最大流=最小割割与流，匹配对于一个无向图G=点独立集：V的一个子集使得该集合中任意两点之间没有边。点支配集：V的一个子集使得任意V中元素要么属于该集合，要么与该集合中点有边相连。点覆盖集：V的一个子集使得任意E中元素都与该集合中某个或某两个元素相关联。极大/最大点独立集，极小/最小点支配集，极小/最小点覆盖集。同样的，我们可以定义边覆盖集（即用边覆盖所有点）与边独立集（即任意两条边之间没有共同点）。割与流，匹配匹配：G的一个边独立集，又被称为G的一个匹配
14、。极大匹配与最大匹配。二部图（二分图）：若无向图G的点集V可以分割成两个互不相交的子集，并且对于边集E中的所有边(vi,vj)所关联的两个顶点vi和vj都分属这两个子集，那么图G就被称为一个二部图。二部图匹配的霍尔定理（婚姻定理）：设有二部图G=
