algorithm - 我对有向加权图中心概念的理解是否正确？

Question

我目前正在解决一个问题，该问题要求我找到有向加权图的中心。我正在努力确保我对一些相关概念的理解是正确的。

例如，假设我们有一些表示为链接的节点集:

/wiki/Flow_network
/wiki/Braess%27_paradox

/wiki/Flow_network
/wiki/Circulation_problem

/wiki/Braess%27_paradox
/wiki/new

/wiki/new
/wiki/Braess%27_paradox

每个集合都有两个节点(链接)，其中第一个节点是“源”节点，并且有到第二个节点的有向边。

据我了解，每个节点都有以下怪癖:

ecc(FN) = 2
ecc(CP) = 0
ecc(BP) = 1
ecc(new) = 1

图形的半径将为 0，因为这是最小的偏心率。

并且由于图的中心是偏心率 = 半径的节点集，所以这个有向加权图的中心将是 CP？

我试图确保我的理解是正确的一个原因是，当人们绘制有问题的图表时，这个“中心”看起来很奇怪。

我的理解正确吗？

Answer 1

在阅读之前，请注意我不是数学家，我只是试图在考虑实现的情况下尝试回答这个问题。图的中心的定义确实是最小离心率的所有顶点的集合。问题是这通常是无向图上使用的概念。如果你的图是无向的，你就不会遇到像你在这里遇到的问题，你的最小偏心率的顶点没有连接到任何其他顶点。根据定义，您认为这是图形的“中心”是正确的。但是，如果图形是无向的，这显然不是中心，并且在理论上下文之外的任何情况下都可能对您无用。如果您只是想找到图形的理论中心，这可能就是您的答案，至少如果您遵循此处找到的偏心率、半径和中心的定义:https://en.wikipedia.org/wiki/Distance_(graph_theory) .如果你想找到更多的无向图中心的影响，其中返回的顶点距离所有其他顶点最远，也许尝试找到具有最低偏心率的顶点，该顶点具有到所有或大多数的路径其他节点，或者如果它不连接到任何其他节点，则可以将顶点的偏心率设置为无穷大。这些建议中的任何一个都可能会给您带来更有用的结果。如果您想要更理论化的观点，请前往数学堆栈交换:https://math.stackexchange.com/ .