问题标签 [graph-theory]

I'm trying to write an algorithm that will find the set of all vertices in a graph with degree smaller than their neighbors. My initial approach is to find the degree of each vertex, then work through the list, comparing the degree of each vertex with the degree(s) of its neighbors. Unfortunately, this looks like it could be very time consuming. Is there a more efficient way to find this set?

假设我们正在遍历一个图，并且想要快速确定一个节点之前是否出现过。我们有一些设定的先决条件。

1. 节点已用整数值 1..N 标记
2. 图是用具有邻接列表的节点实现的
3. 1..N 中的每个整数值都出现在图中，其大小为 N

以纯功能方式执行此操作的任何想法？（不允许哈希表或数组）。

我想要一个有两个函数的数据结构；add（添加遇到的整数）和查找（检查是否添加了整数）。两者都应该优选地花费 O(n) 时间来分摊 N 次重复。

这可能吗？

在图论中，最小距离（Dijkstra 算法发现）和最小路径（我不确定它是什么）之间的区别是什么？

有什么好的算法可以解决这个问题？

我有三组人——A组、B组和C组。每组的人数相同。他们每个人都有一个他们愿意与之合作的其他组中的人员列表。我想将所有这些人分成 3 人一组（一个来自 A，一个来自 B，一个来自 C），这样一个组中的每个人都希望与他们组中的其他人一起工作。

如何快速找到这些组？如果没有办法让每个人都开心，那么算法应该首先让尽可能多的组有三个想要一起工作的人，然后让其他组中的尽可能多的人开心。

最后一点：人们就他们想和谁一起工作达成一致（如果 x 想和 y 一起工作，那么 y 也想和 x 一起工作）。如果您还可以给出算法运行时间的大 O，那就太好了！

锦标赛图和有向完全图是一回事吗？而且，锦标赛图中的所有顶点是否都具有相同数量的边？

在研究跨网络的最短路径算法时，我想生成网络的图片。我想表示节点（圆）、链接（线）、遍历链接的成本（链接线中间的数字）和链接的容量（链接线上它代表的节点旁边的数字）在图片里。是否有任何库/软件可以帮助自动创建此图片？

我可以在 Visio 或使用某些绘图应用程序中手动执行此操作，但我想在更改/调整网络时从代码生成它们。

我正在编写一个算法来找到锦标赛图的主导集。有向图的最小生成树是否等价于图的支配集？换句话说，如果我找到锦标赛图的最小 MST（通过遍历所有顶点），那么我可以说这相当于图的主导集吗？

给定一个集合列表：

• S_1：[1、2、3、4]
• S_2：[3、4、5、6、7]
• S_3 : [ 8, 9, 10, 11 ]
• S_4：[1、8、12、13]
• S_5 : [ 6, 7, 14, 15, 16, 17 ]

合并所有共享至少 2 个元素的集合的最有效方法是什么？我想这类似于连接组件问题。所以结果是：

• [ 1, 2, 3, 4, 5, 6, 7, 14, 15, 16, 17] (S_1 UNION S_2 UNION S_5)
• [ 8, 9, 10, 11 ]
• [ 1, 8, 12, 13 ]（S_4 与 S_1 共享 1，与 S_3 共享 8，但未合并，因为它们仅共享一个元素）

朴素的实现是 O(N^2)，其中 N 是集合的数量，这对我们来说是行不通的。这需要对数百万组有效。

我有一个与图表有关的问题。我不是计算机科学专业的毕业生，因此需要快速介绍什么是图形，我是否可以阅读有关图形以及如何在 C++ 或一般情况下解决图形相关问题的信息。

我在网上找到了几篇文章，提供了如何在 SQL 中对各种类型的图（尤其是 DAG）进行建模的示例，但鉴于它们所建模的内容相对简单，它们似乎都非常复杂。

是否有这样做的最佳/标准方法？我目前的想法是这样的：

这有什么问题吗？任何人都知道更好（也许更强大）的方式？