各位版上大神好，小弟想请问有关System survivability in the context of interdiction networks这篇文章内容，因为想了很久想不出来想请各位协助帮忙 1.此篇文章分成两派脚色分别为follow(跟随者)及leader(领导者)互成对立，follow推算 各路径是采串联方式计算各节点存活率，leader则是要以follow可能路径实施破坏，第一 张图说明follow的计算方式 https://imgur.com/EhVHyTS 跨树问题 如果网路操作包括以跨树方式连接网路的所有节点，而不是将流从源发送到目的地，则後 续网路生存能力可以通过解决相应的最小跨度树问题来确定，而解决方案方法是众所周知 的，并且计算效率很高。在充分了解跟随者移动的情况下，领导者应简单地攻击与跟随者 选择的路径相同的路径（即解决最小跨树问题的道路）。对於缺乏资讯的情况：或说，当 跟随者移动旁边的领导者，因此可能会偏离"破坏路径"，然後，如上所述，领导者将以保 守的方式移动，试图迫使断开网路。这符合领导者网路生存能力的概念。在这种情况下， 问题被修改为领导者试图将网路划分为两个断开的子网路。这可以被看作是最小的二分段 问题，它包括将非定向图形的顶点分离成两个群集，从而最大限度地减轻集群之间交叉边 缘的重量。 A spanning tree problem If the network operation consists on linking all the nodes of the network in a spanning tree fashion instead of sending flow from a source to a destination, then the follower network survivability can be determined by solving the corresponding minimum-spanning-tree problem for which the solution methodology is well-known and computationally efficient. In the case of full knowledge about the follower move, the leader should simply attack the same path as to be chosen by the follower (i.e., the one solving the minimum spanning tree problem). For the case of absence of information; or say when the follower moves next to the leader and hence may deviate from the “destroyed path”, then, as above, the leader would move in a conservative way in an attempt to force disconnecting the network. This corresponds to the concept of the leader network survivability. In this case, the problem is modified to a one in which the leader seeks to partition the network into two disconnected sub-networks. This can be seen as the minimum bisection problem which consists on separating the vertices of an undirected graph into two clusters, such that the weight of the crossing edges between clusters is minimized. 推导公式https://imgur.com/DrwjlxN 例如，在电信网路中，当禁用的节点或连结很少时，可能会在发生一些相对较小的干扰后 重新路由以恢复系统。这可能会将领导者将网路划分为两组脱节：每个都有一些最小的大 小，使其昂贵的追随者恢复网路。因此，我们可以要求攻击时分离节点的最小数量大於或 等於给定阈值T In telecommunication networks for instance, when few nodes or links are disabled, rerouting may be applied to restore the system after some relatively minor disturbance. This may push the leader to partition the network into two disjoint sets; each with some minimum size to make it costly for the follower to restore the network. Therefore, we can require that the minimum number of separated nodes upon attack be larger than or equal to a given threshold value T. 原文图形疑似图错误(没有画[4-6]) https://imgur.com/4yV5P9X 修订後图形 https://imgur.com/hZUStcj 疑问为: 一、T是如何决定为哪个node 二、攻击者攻击node对应相邻的边，如何取决攻击哪个node优先，以T=1时为何是攻击2号 node旁边[4-2]、[2-3] 三、T=2时假设为node2、4旁边受攻击则应该有[1-4]、[2-3]、[4-6]、[2-4]， 但答案少了[4-2]。 四、T=3的点为何?又是如何选边呢? 麻烦各位大神协助帮忙，谢谢 --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 140.113.0.229 (台湾) ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Math/M.1622547336.A.E34.html