按顶点度数计算的子图中的边数
Edges number in a subgraph counted by vertice degree
我有一个子图，它只被识别为一组已知度数的顶点。
我想知道这个子图中有多少条边。有没有办法计算这个？
请注意，并非每条边都在子图中。有边连接子图中的顶点和子图中的顶点，因此不能简单地计算为顶点度数之和除以 2。
如果这对我有任何帮助，我正在使用 JGraphT。
Q: Is there a method to count this?
仅使用已知度数的顶点集 - 不幸的是不是。考虑这个简单的反例：具有 3 个顶点的完整子图将用 3 个 2 度顶点表示（假设这是一个强连通分量），因此在这种情况下子图中的边数为 3.
但是，如果你有3个2度的顶点并不都是相互连通的（比如A和B和A和C是连通的，但是B和C不连通），并且顶点B和C仍然是连通的度数为 2，因为边与其他顶点不在子图中，答案为 2。因此，对于相同的输入，您可以有两个不同的输出，这表明您需要一些额外的数据。
我有一个子图，它只被识别为一组已知度数的顶点。
我想知道这个子图中有多少条边。有没有办法计算这个？
请注意，并非每条边都在子图中。有边连接子图中的顶点和子图中的顶点，因此不能简单地计算为顶点度数之和除以 2。
如果这对我有任何帮助，我正在使用 JGraphT。
Q: Is there a method to count this?
仅使用已知度数的顶点集 - 不幸的是不是。考虑这个简单的反例：具有 3 个顶点的完整子图将用 3 个 2 度顶点表示（假设这是一个强连通分量），因此在这种情况下子图中的边数为 3.
但是，如果你有3个2度的顶点并不都是相互连通的（比如A和B和A和C是连通的，但是B和C不连通），并且顶点B和C仍然是连通的度数为 2，因为边与其他顶点不在子图中，答案为 2。因此，对于相同的输入，您可以有两个不同的输出，这表明您需要一些额外的数据。