图论

1. Dotcpp
2. 图论

简述矩阵树定理

Kirchhoff矩阵树定理可以简称矩阵树定理，可以解决了一张图的生成树个数计数问题。本篇中的图，无论无向还是有向，都允许重边，但是不允许自环。一、概况1.无向图情况设G是一个有n个顶点的无向图。定义度数矩阵D(G)为：设为点i与点j相连的边数，

图论 2022年05月27日 160 点赞 0 评论 93130 浏览

简述LGV引理

LGV引理可以用于在DAG上求解不相交路径方案数问题，下面我们简单介绍一下。一、简介LGV引理英文全称是Lindström–Gessel–Viennotlemma，可以用来处理有向无环图上不相交路径计数等问题。在此之前，大家要先了解图论相关概念、矩阵、高斯消元求行列式等知识，

图论 2022年04月20日 249 点赞 0 评论 65870 浏览

网络流的基本概念

什么是网络流？首先大家要知道网络流在图论中是尤为重要的。在这里，给大家介绍网络流中的一些基本知识。一、网络流的概念和定义整理在图论中，网络流（英语：Networkflow）是指在一个每条边都有容量（Capacity）的有向图分配流，使一条边的流量不会超过它的容量。

图论 2022年03月23日 158 点赞 0 评论 106338 浏览

树上启发式合并

启发式算法是什么呢？启发式算法是基于人类的经验和直观感觉，对一些算法的优化。最常见的就是并查集的按秩合并了，有带按秩合并的并查集中，合并的代码是这样的：voidmerge(intx,inty){intxx=find(x),yy=find(y);if(size[xx]<size[yy])swap(xx,

图论 2022年02月17日 189 点赞 0 评论 66961 浏览

斯坦纳树Steiner Tree实例讲解

说到斯坦纳树问题，它是一种组合优化问题，与最小生成树相似，是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点外增加额外的点，使生成的最短网络开销最小。一、斯坦纳树斯坦纳树问题是组合优化问题，与最小生成树相似，

图论 2022年05月10日 233 点赞 0 评论 90779 浏览

什么是差分约束系统？

什么是差分约束系统？差分约束系统是一种特殊的N元一次不等式组，它包含N个变量以及M个约束条件，每个约束条件都是由两个变量作差得到的，形如，其中是常数。我们根据题目要求，并用这M个约束条件求出某个不等式的最值，例如的最大值。怎么解？转化：把上面不等式稍微变形一下可以得到，

图论 2022年02月05日 234 点赞 0 评论 71356 浏览

图的遍历DFS深搜优先搜索及C语言代码实现

1.图的遍历在理解DFS算法之前，我们首先需要对什么是遍历进行了解，遍历的概念就是：从某一个点出发（一般是首或尾），依次将数据结构中的每一个数据访问且只访问一遍。2.DFS简介DFS（Depth-First-Search，深度优先搜索）算法的具体做法是：从某个点一直往深处走，

图 2022年01月25日 261 点赞 0 评论 184276 浏览

图论中的有向无环图

在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。因为有向图中一个点经过两种路线到达另一个点未必形成环，因此有向无环图未必能转化成树，但任何有向树均为有向无环图。一、简介有向无环图是图论的重要概念，

图论 2022年02月06日 86 点赞 0 评论 82297 浏览

图论矩阵树定理实例讲解

矩阵树定理也称Matrix-Tree定理或Kirchhoff定理。这个定理提供了一种方式使用一个特殊的矩阵的行列式来计算一个图的生成树的数量。对于一个无向图来说，我们可以构造它的Laplace矩阵L，其中：如果节点i有度为d，那么L[i,i]=d如果节点i和节点j之间有边相连，

图论 2022年01月26日 159 点赞 0 评论 72884 浏览

什么是虚树？

当我们遇到一类频繁询问关键点信息的题目时，往往数据范围颇大，而对关键点总和有一定限制，此时我们可以建立虚树，将问题规模转化为关键点总和级别的。一、定义什么是虚树？当我们在树上有部分结点是无用的或用处不大的时，我们可以将其在树上删去，仅仅保留关键点和连接关键点的边。

图论 2022年01月16日 194 点赞 0 评论 78648 浏览