给定一个具有 n >= 3 节点且没有边的无向图 G(无自环，不允许多边)。
还有下面的方法A:
向图 G 添加一个新节点 v 和三个边 {v,w1}、{v,w2} 和 {v,w3}。
w1、w2 和 w3 是原始图中已经包含的节点(成对不同)。
问题是方法A可以执行多少次(取决于n)，
如果节点可能没有 degree > 4?
我的观察: 每次执行方法 A 时，我们都会多一个节点。该节点的度数已经为 3，因此该节点只能再连接一条边。在同一步骤中，其他三个节点获得了更高的 +1 度。 我已经测试了具有 n=3 个节点的图 G。该方法可以执行四次。
这不是作业，这是一道老考题。 所以我不要求解决方案，只是寻求如何解决任务的提示。
最佳答案
看来您的方向是正确的。该图以添加 4*n 条边的“容量”开头。每个新节点都会将总边容量减少 2。这可以用简单的代数来解决。唯一剩下的问题是你能找到一种边缘分配方案来防止你有足够的边缘容量但没有足够的节点的情况。
关于algorithm - 一种方法可以在图形上执行的频率，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/20292248/