斯坦纳树的应用 斯坦纳树问题是组合优化问题，与最小生成树相似，是最短网络的一种。最小生成树是在给定的点集和边中寻求最短网络使所有点连通。而最小斯坦纳树允许在给定点外增加额外的点，使生成的最短网络开销最小。1.什么是斯坦纳树？斯坦纳树问题是组合优化学科中的一个问题。 图论 2022年02月01日 209 点赞 0 评论 88249 浏览
上下界网络流总结 上下界网络流可以看做普通网络流的升级版，现在对于流量网络，我们不再只关注其流量的上界，而是同时关注流量的上下界。一、无源汇有上下界可行流这是上下界网络流中最简单的一种，给定一个没有源点和汇点、每条边的流量有上下界的流量网络，问是否存在一种可行流使得流量平衡。 图论 2022年02月01日 226 点赞 0 评论 86777 浏览
有向无环图图文讲解 一、定义边有向，无环。英文名叫DirectedAcyclicGraph，缩写是DAG。一个无环的有向图称做有向无环图。在图论中，如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。因为有向图中一个点经过两种路线到达另一个点未必形成环， 图论 2022年03月20日 154 点赞 0 评论 84717 浏览
简述最大团搜索算法 一、引入在计算机科学中，团问题指的是在给定的图中找到团（顶点的子集，都彼此相邻，也称为完全子图）的计算问题。团的问题在现实生活中也有体现。例如我们考虑一个社交网络，其中图的点代表用户，图的边代表其所连接的两个用户互相认识。那么我们找到了一个团，也就找到了一群互相认识的人。 图论 2022年05月24日 152 点赞 0 评论 83627 浏览
图论部分简介 图论(Graphtheory)是数学的一个分支，图是图论的主要研究对象。图(Graph)是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。 图论 2022年05月12日 147 点赞 0 评论 83019 浏览
图论中的有向无环图 在图论中，如果一个有向图从任意顶点出发无法经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。因为有向图中一个点经过两种路线到达另一个点未必形成环，因此有向无环图未必能转化成树，但任何有向树均为有向无环图。一、简介有向无环图是图论的重要概念， 图论 2022年02月06日 86 点赞 0 评论 82297 浏览
哈密顿图的应用 哈密顿通路（回路）与哈密顿图（Hamilton图）通过图G的每个结点一次，且仅一次的通路（回路），就是哈密顿通路（回路）。下面总结四个定义，帮助大家理解。一、哈密顿图定义通过图中所有顶点一次且仅一次的通路称为哈密顿通路。通过图中所有顶点一次且仅一次的回路称为哈密顿回路。 图论 2022年02月21日 195 点赞 0 评论 80019 浏览
什么是虚树？ 当我们遇到一类频繁询问关键点信息的题目时，往往数据范围颇大，而对关键点总和有一定限制，此时我们可以建立虚树，将问题规模转化为关键点总和级别的。一、定义什么是虚树？当我们在树上有部分结点是无用的或用处不大的时，我们可以将其在树上删去，仅仅保留关键点和连接关键点的边。 图论 2022年01月16日 194 点赞 0 评论 78649 浏览
最大流是什么？ 一、流网络G=(V，E)是一个有向图，其中每条边(u，v)有一个非负的容量值c(u，v)，而且如果E中包含一条边(u，v)，那么图中就不存在它的反向边。在流网络中有两个特殊的结点，源结点s和汇点t。下面给出流网络的形式化定义。令G=(V，E)为一个流网络，其容量函数为c，设s我为网络的源点，t为汇点。 图论 2022年02月25日 110 点赞 0 评论 78213 浏览
树的直径实例讲解 首先先介绍一下什么是树的直径，树的直径，又称树的最长链，定义为一棵树上最远的两个节点的路径，即树上一条不重复经过某一条边的最长的路径。树的直径也可以代指这条路径的长度，总的来说树的直径就是树中所有最短路经距离的最大值。求树的直径有两种比较常用的方法：一种是通过两次搜索（bfs和dfs均可）， 图论 2022年03月24日 60 点赞 0 评论 75268 浏览
