algorithm - 比较不同大小的图的好方法？

很抱歉，如果这是一个基本问题，但我想知道是否有人可以帮助我找出这类问题我的具体问题陷入。我在寻找可以用来比较不同大小和连通性的图的任何标准度量具体来说，请考虑以下示例：

      G1                             G2
      2                              D
      |                             /  \
4 --- 1 --- 3                 C -- A1 - A2 -- E
      |
      5

我感兴趣的是在一个图（内部稳定性）和相对于另一个图（内部稳定性）中捕捉稳定性的概念。例如，
内部稳定性：
在G1中，在我的假设度量中，2,3,4,5都具有相同的效果，如果将它们从图中删除。在G2中，C,E将具有相同的效果，但D将具有更大的效果。但是，如果去除它们，A1,A2会产生更大的效果。我在这里寻找的是一个图的稳定性的概念我猜我可以使用每个节点的度来捕捉特定节点的效果，但不确定如何计算整个图本身的效果。
内部稳定性：
我们能从相对意义上说一下G1和G2吗？比如说，因为G1有一个稳定性指标X和G2有Y并且因为X < Y，我们得出结论G1比G2不稳定吗？稳定本身的定义是开放的，但我试图捕捉一个图有多不可靠，或者它对一个节点有多依赖。
有人能给我指一个正确的方向来量化这个或者至少这个问题被称为什么吗？

最佳答案

在图论中，一个割集或割集似乎描述了你的最大不稳定性描述。
作为衡量标准，你可能在谈论“连接性”

关于algorithm - 比较不同大小的图的好方法？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6741468/