各位版上大神好，小弟想請問有關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/m.aspx?n=bbs/Math/M.1622547336.A.E34.html