Skip to main content

The Sabotage

As a resistance leader, you have obtained a schematic map of the dictatorship's communication cables. Because the government wants to control every piece of news, the signal is one-way only, flowing from the capital out to the military. To launch your attack, you must completely cut all connection between the Capital (s) and the Military Base (t).

Each one-way cable is guarded. The cost to destroy a cable (in C4 charges and personnel) is equal to its capacity. You have a total budget of B = 10.

s a b t 10 8 2 3 6

Problem Statement

Which of the following statements is true regarding your sabotage plan?

a) The cheapest way to disconnect the base costs 11, so your budget of B = 10 is not enough to go through with the plan.

b) You can successfully cut all signals for a cost of 9 by destroying the cables (a, t) and (b, t).

c) The most efficient plan is to hit cables (s, b) and (b, a), which only costs 10 and leaves the base isolated.

d) Since the signal is high-bandwidth, you would need to destroy every cable connected to the Capital, costing you exactly 18.

e) None of the above

Original idea by: Luis Alberto Vásquez Vargas

Comments

Post a Comment

Popular posts from this blog

The Barking Dog Dilemma

Albert enjoys walking through his neighborhood to buy groceries. He models the neighborhood as an undirected simple graph \(G=(V,E)\), where: Each corner is represented by a vertex . Each street connecting two corners is represented by an edge . Albert starts from his home at vertex \(s\) and wants to reach the grocery store at vertex \(t\). Some dogs in the neighborhood bark aggressively. Dogs may be located either at corners or along streets , and they are represented in the graph as follows: If a dog is located at a corner , the corresponding vertex is considered unsafe . If a dog is located along a street , the corresponding edge is considered unsafe . Consider the graph with: Vertices \(V=\{s,1,2,3,4,5,6,t\}\) Edges \(E=\{(s,1),(s,3),(1,3),(1,2),(3,4),(3,6),(4,5),(5,6),(4,2),(2,t)\}\) Additionally: Edge \((1,2)\) is unsafe. Edge \((3,4)\) is unsafe. Vertex \(1\) is unsafe. s 1 2 3 4 5 6 t ...
Post a Comment
Read more

Inverse Problem for Degree Sequences

Let G = (V,E) be a simple undirected graph , meaning that it has no self-loops (edges of the form (v,v)) and no multiple edges between the same pair of vertices. For such a graph we can define its degree sequence deg , where each element represents the degree of a vertex. For example, the graph shown below has degree sequence deg = (3,1,1,1) In this exercise we consider the inverse problem : given a degree sequence deg , determine whether it is possible to construct a simple undirected graph with that sequence. For each of the following statements, determine whether it is True (T) or False (F) . i) deg = (2,2) generates more than one graph. ii) deg = (2,2,2) generates exactly one graph. iii) deg = (2,2,2,2,2,2) generates exactly one graph. Alternatives a) TTF b) FTT c) TFT d) FTF e) None of the above Original idea by: Luis Alberto Vásquez Vargas
2 comments
Read more

The Reachability & SCC Correlation

In a directed graph \(G = (V, E)\), we explore the relationship between path reachability and Strongly Connected Components (SCCs) . To analyze this, we define two functions: \(f(u, v) \in \{True, False\}\): Returns True if there exists at least one directed path from \(u\) to \(v\). \(scc\_id(u) \in \mathbb{Z}\): Returns a unique ID for the SCC containing node \(u\). In the following example, we can observe that two nodes \(u\) and \(v\) are in the same SCC if and only if \(scc\_id(u) = scc\_id(v)\). scc_id = 1 scc_id = 2 scc_id = 3 1 2 3 ...
1 comment
Read more