在图中测量节点的“连接重度”

Question

4

我已经在MathOverflow.com上发布了这个问题。我不是数学家，英语也不是我的母语，所以如果我的问题太蠢，措辞不当或两者都有，请原谅。

我正在开发一个创建课程表的程序。除了创建课程表外，我的算法还创建了一个图形，其节点表示我已经编程的每个班级，弧表示不能同时编程哪些班级，即使它们必须重新编程。节点与其他节点的联系越紧密，与重新编程相对应的班级就越不灵活。

有时，在过程中，没有选择，只能重新编程已经编程的班级。我希望我的程序能够选择一个班级，如果重新编程，会影响尽可能少数量的其他已编程班级。这意味着选择图中“联系不太紧密”的节点，但需要满足某些节点的选择限制。

编辑：问题是...您是否知道任何测量节点“链接程度”的算法？

- pyon

我不明白问题在哪里。 - WhirlWind

正确的术语是“度”。 - Martin

http://en.wikipedia.org/wiki/Degree_%28graph_theory%29 - Martin

2个回答

0

假设你的弧是“双向链接”的，我会考虑保持一个单独的优先队列，其中包含图中每个节点的引用，每个节点的优先级设置为每个节点具有的链接计数。

- Brent Arias

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- celerno · Accepted Answer

不是很难。在你的类里面，你可以简单地创建一个“重量”字段和一个事件，在涉及该类的任何链接上进行任何更改时触发该事件。因此，您只需使用“权重”属性来计算“获取最大值”算法。