图论
  1. Dotcpp
  2. 图论

列表

网络流的基本概念

网络流的基本概念

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

最大流是什么？

一、流网络G=(V，E)是一个有向图，其中每条边(u，v)有一个非负的容量值c(u，v)，而且如果E中包含一条边(u，v)，那么图中就不存在它的反向边。在流网络中有两个特殊的结点，源结点s和汇点t。下面给出流网络的形式化定义。令G=(V，E)为一个流网络，其容量函数为c，设s我为网络的源点，t为汇点。
图论 2022年02月25日
上下界网络流总结

上下界网络流总结

上下界网络流可以看做普通网络流的升级版，现在对于流量网络，我们不再只关注其流量的上界，而是同时关注流量的上下界。一、无源汇有上下界可行流这是上下界网络流中最简单的一种，给定一个没有源点和汇点、每条边的流量有上下界的流量网络，问是否存在一种可行流使得流量平衡。
图论 2022年02月01日
简述最大团搜索算法

简述最大团搜索算法

一、引入在计算机科学中，团问题指的是在给定的图中找到团（顶点的子集，都彼此相邻，也称为完全子图）的计算问题。团的问题在现实生活中也有体现。例如我们考虑一个社交网络，其中图的点代表用户，图的边代表其所连接的两个用户互相认识。那么我们找到了一个团，也就找到了一群互相认识的人。
图论 2022年05月24日
什么是弦图？

什么是弦图？

什么是弦图？下面的图我们看到后，第一感觉应该虽然看着很酷炫，但是会感觉很复杂，感觉无所适从，不知怎么来看这个图表。今天我们就来介绍下这个图表是怎么用的？这个图表叫做弦图，弦图主要用于展示多个对象之间的关系，连接圆上任意两点的线段叫做弦，弦（两点之间的连线）就代表着两者之间的关联关系。
图论 2022年01月18日
简述LGV引理

简述LGV引理

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

什么是Prufer序列？

Prufer序列可以将一个带标号n个结点的树用[1,n]中的n-2个整数表示。你也可以把它理解为完全图的生成树与数列之间的双射。显然你不会想不开拿这玩意儿去维护树结构。这玩意儿常用组合计数问题上。HeinzPrufer于1918年发明这个序列来证明凯莱定理。
图论 2022年02月11日
二分图的最大匹配、完美匹配和匈牙利算法

二分图的最大匹配、完美匹配和匈牙利算法

二分图：简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。准确地说：把一个图的顶点划分为两个不相交集U和V，使得每一条边都分别连接U、V中的顶点。如果存在这样的划分，则此图为一个二分图。二分图的一个等价定义是：不含有「含奇数条边的环」的图。
图论 2022年01月30日