Differences

This shows you the differences between two versions of the page.

--- courses:b4m35ko:midterms [2026/05/29 10:40] – created mistrjirka
+++ courses:b4m35ko:midterms [2026/05/29 10:43] (current) – mistrjirka
@@ Line 1: / Line 1: @@
-hello
+====== Praktický test 2026 ======
+{{ :courses:b4m35ko:2024_practice_test.pdf |Praktický test practise}}
+{{ :courses:b4m35ko:ko_test_painting.pdf |ko_test_painting.pdf}}
+===== 1. semestrální test 2026 =====
+{{:courses:b4m35ko:ko_t1_sol1.png?direct&400}}
+{{:courses:b4m35ko:ko_t1_sol2.png?direct&400}}
+{{:courses:b4m35ko:ko_t1_sol3.png?direct&400}}
+{{:courses:b4m35ko:ko_t1_sol4.png?direct&400}}
+====== Praktický test 2025 ======
+{{:courses:b4m35ko:pasted:20250420-092518.png?direct&400}}
+{{:courses:b4m35ko:pasted:20250420-092450.png?direct&400}}
+====== 2. Teoretický test ======
+Psaný na přednášce v 10. týdnu.
+Rok ze kterého je toto PDF bohužel neznám.
+{{ :courses:b4m35ko:ko_test_2.pdf |}}
+{{ :courses:b4m35ko:ko_test2.pdf | Test 2 nevyplněný}} {{ :courses:b4m35ko:ko_test2.tex | $\LaTeX$ source (ko_test2.tex)}}
+Níže si můžete vyzkoušet otázky a odpovědi bez řešení, vyberte si kolik chcete otázek a odstartujte test.
+<flashcards heading="KO test 2" subtext="Každá otázka má jednu správnou odpověď." skiptext="Přeskočit" defaultnum="all">
+<questions>
+Test 1 - Question 1
+Consider the network graph depicted in the figure consisting of source node $s$, destination node $t$, and $n$ disjoint paths going from $s$ to $t$, each such path consists of exactly $m$ arcs. (Hence, such a graph consists of $n(m-1)+2$ nodes and $nm$ arcs.) All minimum capacities are 0 and maximum capacities are 1. How many distinct minimum capacity cuts are there?
+{{:courses:b4m35ko:ko_t21.png}}
+- $m^2$
+- $m$
+- $n^2$
+- $\binom{n}{m}$
+* $m^n$
+- $\binom{m}{n}$
+- $\binom{n(m-1)}{n}$
+- 0
+- $n^m$
+- 1
+- $\binom{n(m-1)}{m}$
+- None of the other options is correct
+---
+Test 1 - Question 2
+(i) Each maximum flow defines a minimum capacity cut. Is this minimum capacity cut unique? That is, for a given maximum flow, could there be more than one minimum capacity cut for this flow?
+(ii) On the contrary, does each minimum capacity cut define a unique maximum flow? Or can there be more maximum flows for a given minimum capacity cut?
+- (i) For a given maximum flow, the minimum capacity cut is unique, but (ii) for a given minimum capacity cut, there may be more maximum flows.
+- (i) For a given maximum flow, the minimum capacity cut is unique, as well as (ii) for a given minimum capacity cut, the maximum flow is unique.
+- (i) For a given maximum flow, there may be more minimum capacity cuts, but (ii) for a given minimum capacity cut, the maximum flow is unique.
+* (i) For a given maximum flow, there may be more minimum capacity cuts, as well as (ii) for a given minimum capacity cut, there may be more maximum flows.
+---
+Test 1 - Question 3
+(i) Does there exist a network $(G, l, u, c, b)$, where $G=(V,E)$ such that every minimum cost flow has a zero flow on the minimum cost arc from $E$?
+(ii) Does there exist a network $(G, l, u, c, b)$, where $G=(V,E)$ such that every minimum cost flow has a positive flow on the maximum cost arc from $E$?
+* (i) yes (ii) yes
+- (i) yes (ii) no
+- (i) no (ii) yes
+- (i) no (ii) no
+---
+Test 1 - Question 4
+Let 5-tuple $(G, l, u, s, t)$, where $G=(V,E)$, be a network and $f_1, f_2$ be two feasible flows in graph $G$ (functions from $E \to \mathbb{R}^+$). Are the following functions necessarily also feasible flows in $G$?
+(i) $f_1+f_2$
+(ii) $\alpha f_1$ for $\alpha \ge 0$.
+Function $f_1+f_2$ is defined as $(f_1+f_2)(e) := f_1(e) + f_2(e)$, for each arc $e \in E$, and, similarly, $(\alpha f_1)(e) := \alpha f_1(e)$.
+* (i) no (ii) no
+- (i) yes (ii) yes
+- (i) yes (ii) no
+- (i) no (ii) yes
+---
+Test 1 - Question 5
+Consider the directed graph shown in the figure. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijkstra's shortest path algorithm?
+Assume that, in any iteration, the shortest path to a vertex is updated only when a strictly shorter path to it is discovered.
+{{:courses:b4m35ko:ko_t24.png}}
+* S A C E T
+- None of the other options is correct
+- S A C D T
+- S D T
+- S B D T
+---
+Test 1 - Question 6
+Given a connected weighted undirected graph $G$ where weights of all edges are unique, i.e., no two edges have the same weights. Are the following statements true or false?
+(i) The shortest path from a source to a destination in such a graph is always unique.
+(ii) The minimum spanning tree (MST) of graph $G$ is always unique.
+(Hint: Recall how Prim's or Kruskal's algorithm works.)
+- (i) true (ii) true
+- (i) false (ii) false
+* (i) false (ii) true
+- (i) true (ii) false
+---
+Test 1 - Question 7
+Are the following statements true or false?
+(i) A graph can have more than one shortest path between two vertices.
+(ii) A graph where all edge weights are distinct can have more than one shortest path between two vertices.
+- (i) false (ii) false
+- (i) false (ii) true
+* (i) true (ii) true
+- (i) true (ii) false
+---
+Test 2 - Question 1
+Consider the graph consisting of source node $0$, destination node $n$, and $n$ connected "triangles" as depicted in the figure. (Such a graph consists of $2n+1$ nodes and $3n$ arcs.) How many distinct paths from $0$ to $n$ are there?
+{{:courses:b4m35ko:ko_t22.png}}
+- $n!$
+- 0
+- 1
+* $2^n$
+- None of the other options is correct
+- $2n$
+- $\binom{n}{2}$
+- $n^2$
+---
+Test 2 - Question 2
+Let 5-tuple $(G, l, u, s, t)$, where $G=(V,E)$ be a network and let a minimum cut be induced by $A \subset V$. Which of the following claims are true and which are false?
+(i) If we multiply each arc capacity by a positive number, the minimum cut induced by $A$ is still a minimum cut.
+(ii) If we add a positive number to each arc capacity, the minimum cut induced by $A$ is still a minimum cut.
+- (i) false (ii) true
+* (i) true (ii) false
+- (i) true (ii) true
+- (i) false (ii) false
+---
+Test 2 - Question 3
+Recall the application of the network flows related to the maximum dynamic flow problem. Are the following statements true or false?
+(i) The time-expanded replica of a network can contain a directed cycle.
+(ii) The maximum dynamic flow problem can have multiple optimal solutions.
+- (i) true (ii) false
+- (i) false (ii) false
+* (i) false (ii) true
+- (i) true (ii) true
+---
+Test 2 - Question 4
+Which of the following claims are true and which are false?
+(i) If $f$ is a maximum flow, then for every pair of arcs $(i, j)$ and $(j, i)$ either $f(i,j)=0$ or $f(j,i)=0$.
+(ii) Any network with zero minimum capacities always has a maximum flow $f$ for which, for every pair of arcs $(i, j)$ and $(j, i)$, either $f(i,j)=0$ or $f(j,i)=0$.
+- (i) true (ii) false
+- (i) true (ii) true
+* (i) false (ii) true
+- (i) false (ii) false
+---
+Test 2 - Question 5
+Let $G=(V,E)$ be a simple directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex $i$ to a vertex $j$ if and only if either $j=i+1$ or $j=3i$.
+What is the length of the shortest path (in terms of the number of edges) in $G$ from vertex 1 to vertex 100?
+* 7
+- 23
+- 99
+- 4
+---
+Test 2 - Question 6
+Given a connected weighted undirected graph $G$ where weights of all edges are unique, i.e., no two edges have the same weights. Are the following statements true or false?
+(i) The shortest path from a source to a destination in such a graph is always unique.
+(ii) The minimum spanning tree (MST) of graph $G$ is always unique.
+(Hint: Recall how Prim's or Kruskal's algorithm works.)
+- (i) true (ii) true
+- (i) true (ii) false
+- (i) false (ii) false
+* (i) false (ii) true
+---
+Test 2 - Question 7
+Given a weighted directed graph $G=(V,E,w)$ and a shortest path $P$ from $s$ to $t$. Are the following statements true or false?
+(i) If we multiply the weight of every edge by positive constant to produce $G'=(V,E,w')$, then $P$ is also a shortest path in $G'$.
+(ii) If we add positive constant to the weight of every edge to produce $G'=(V,E,w')$, then $P$ is also a shortest path in $G'$.
+- (i) true (ii) true
+- (i) false (ii) true
+- (i) false (ii) false
+* (i) true (ii) false
+---
+Test 3 - Question 1
+Consider the network graph depicted in the figure consisting of source node $s$, destination node $t$, and $n$ disjoint paths going from $s$ to $t$, each such path consists of exactly $m$ arcs. All minimum capacities are 0 and maximum capacities are 1.
+How many distinct maximum flows are there?
+{{:courses:b4m35ko:ko_t21.png}}
+* 1
+- 0
+- $m^2$
+- $m$
+- $\binom{n(m-1)}{m}$
+- None of the other options is correct
+- $m^n$
+- $\binom{m}{n}$
+- $\binom{n(m-1)}{n}$
+- $n^2$
+- $\binom{n}{m}$
+---
+Test 3 - Question 2
+(i) Each maximum flow defines a minimum capacity cut. Is this minimum capacity cut unique? That is, for a given maximum flow, could there be more than one minimum capacity cut for this flow?
+(ii) On the contrary, does each minimum capacity cut define a unique maximum flow? Or can there be more maximum flows for a given minimum capacity cut?
+- (i) For a given maximum flow, the minimum capacity cut is unique, but (ii) for a given minimum capacity cut, there may be more maximum flows.
+* (i) For a given maximum flow, there may be more minimum capacity cuts, as well as (ii) for a given minimum capacity cut, there may be more maximum flows.
+- (i) For a given maximum flow, there may be more minimum capacity cuts, but (ii) for a given minimum capacity cut, the maximum flow is unique.
+- (i) For a given maximum flow, the minimum capacity cut is unique, as well as (ii) for a given minimum capacity cut, the maximum flow is unique.
+---
+Test 3 - Question 3
+A matching $M$ is a maximal matching of $G=(V,E)$ if for every arc $(i, j) \notin M$, $M \cup \{(i, j)\}$ is not a matching. The cardinality of a matching $M$ is the number of arcs in the matching and is denoted as $|M|$. A matching is a maximum matching if it is of the largest cardinality among all matchings.
+(i) Does there exist a graph with a maximal matching $A$ and maximum matching $B$ such that $2 \cdot |A|=|B|$?
+(ii) In a weighted graph, a maximum weight matching is a matching of the largest sum of the weights of arcs in the matching among all matchings and a perfect matching is a matching that covers every vertex of the graph. Is maximum weight matching also a perfect matching?
+- (i) no (ii) yes
+- (i) yes (ii) yes
+- (i) no (ii) no
+* (i) yes (ii) no
+---
+Test 3 - Question 4
+Which of the following claims are true and which are false?
+(i) If $f$ is a maximum flow, then for every pair of arcs $(i, j)$ and $(j, i)$ either $f(i,j)=0$ or $f(j,i)=0$.
+(ii) Any network with zero minimum capacities always has a maximum flow $f$ for which, for every pair of arcs $(i, j)$ and $(j, i)$, either $f(i,j)=0$ or $f(j,i)=0$.
+* (i) false (ii) true
+- (i) true (ii) true
+- (i) true (ii) false
+- (i) false (ii) false
+---
+Test 3 - Question 5
+Suppose we run Dijkstra's shortest path tree algorithm on the edge-weighted directed graph depicted in the figure with vertex P as the source. In what order do the nodes get included into the set of vertices for which the shortest path distances are permanent?
+{{:courses:b4m35ko:ko_t23.png}}
+- P, Q, R, U, T, S
+* P, Q, R, U, S, T
+- None of the other options is correct
+- P, Q, T, R, U, S
+- P, Q, R, S, T, U
+---
+Test 3 - Question 6
+Given a connected weighted undirected graph $G$ where weights of all edges are unique, i.e., no two edges have the same weights. Are the following statements true or false?
+(i) The shortest path from a source to a destination in such a graph is always unique.
+(ii) The minimum spanning tree (MST) of graph $G$ is always unique.
+(Hint: Recall how Prim's or Kruskal's algorithm works.)
+- (i) true (ii) true
+- (i) false (ii) false
+- (i) true (ii) false
+* (i) false (ii) true
+---
+Test 3 - Question 7
+An airline charges a fixed price for each individual flight. For each sequence of hopping flights, the ticket price is the sum of the fares of the individual flights. TripGuru has precalculated the cheapest routes between all pairs of cities so that it can offer an optimum choice instantly to customers visiting its website. The airline has decided to become a full-service carrier and has included a meal on each individual flight. To account for this, the airline has added a flat "convenience fee" to the cost of each individual flight. Which of the following describes the impact of this surcharge on TripGuru's computation?
+- The surcharge favors hopping flights with more individual flights. TripGuru should recompute any cheapest route where there is a longer route in terms of the number of flights.
+* The surcharge favors hopping flights with fewer individual flights. TripGuru should recompute any cheapest route where there is a shorter route in terms of the number of flights.
+- The impact is unpredictable. TripGuru should recompute all routes.
+- There is no impact. The cheapest routes between all pairs of cities remain unchanged.
+---
+Test 4 - Question 1
+Consider the network graph consisting of source node $0$, destination node $n$, and $n$ connected "triangles" as depicted in the figure. (Such a graph consists of $2n+1$ nodes and $3n$ arcs.) All minimum capacities are 0 and maximum capacities are 1. How many distinct minimum capacity cuts are there?
+{{:courses:b4m35ko:ko_t22.png}}
+- $n^2$
+- $2^n$
+- None of the other options is correct
+- $n!$
+- $n$
+* $2n$
+- 1
+- 0
+- $\binom{n}{2}$
+---
+Test 4 - Question 2
+Consider a network with zero minimum capacities. Which of the following claims are true and which are false?
+(i) If all arcs in a network have different maximum capacities, the network has a unique minimum cut.
+(ii) If all arcs in a network have different maximum capacities, the network has a unique maximum flow.
+- (i) true (ii) false
+- (i) false (ii) true
+* (i) false (ii) false
+- (i) true (ii) true
+---
+Test 4 - Question 3
+Recall the application of the network flows related to the maximum dynamic flow problem. Are the following statements true or false?
+(i) The time-expanded replica of a network can contain a directed cycle.
+(ii) The maximum dynamic flow problem can have multiple optimal solutions.
+- (i) false (ii) false
+* (i) false (ii) true
+- (i) true (ii) false
+- (i) true (ii) true
+---
+Test 4 - Question 4
+Let $\alpha \in \mathbb{N}$. Which of the following claims are true and which are false?
+(i) If the capacity of every arc in a network is an integer multiple of $\alpha$, then in every maximum flow, each arc flow will be an integer multiple of $\alpha$.
+(ii) If the capacity of every arc in a network is increased by $\alpha$ units, then the value of a maximum flow will increase by an integer multiple of $\alpha$.
+(iii) If the capacity of every arc in a network is increased by $\alpha$ units, then the value of a maximum flow will increase by $\alpha$.
+* (i) false (ii) false (iii) false
+- (i) true (ii) false (iii) true
+- None of the other options is correct
+- (i) false (ii) false (iii) true
+- (i) true (ii) false (iii) false
+- (i) false (ii) true (iii) false
+- (i) true (ii) true (iii) false
+---
+Test 4 - Question 5
+Consider the directed graph shown in the figure. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijkstra's shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex is updated only when a strictly shorter path to it is discovered.
+{{:courses:b4m35ko:ko_t24.png}}
+- S B D T
+- None of the other options is correct
+- S A C D T
+- S D T
+* S A C E T
+---
+Test 4 - Question 6
+Let $s$ and $t$ be two vertices in an undirected graph $G=(V,E)$ having all distinct positive edge weights. The congestion on a path is defined as the maximum of the edge weights on the path. We wish to find the path from $s$ to $t$ having minimum congestion. Which one of the following paths is always such a path of minimum congestion?
+- An Euler walk (i.e., an edge progression where no edge appears more than once) from $s$ to $t$.
+- A shortest path from $s$ to $t$.
+- A Hamiltonian path (i.e., a path that visits all vertices) from $s$ to $t$.
+* A path from $s$ to $t$ in the minimum spanning tree (MST).
+---
+Test 4 - Question 7
+An airline charges a fixed price for each individual flight. For each sequence of hopping flights, the ticket price is the sum of the fares of the individual flights. TripGuru has precalculated the cheapest routes between all pairs of cities so that it can offer an optimum choice instantly to customers visiting its website. The airline has decided to become a full-service carrier and has included a meal on each individual flight. To account for this, the airline has added a flat "convenience fee" to the cost of each individual flight. Which of the following describes the impact of this surcharge on TripGuru's computation?
+- The surcharge favors hopping flights with more individual flights. TripGuru should recompute any cheapest route where there is a longer route in terms of the number of flights.
+* The surcharge favors hopping flights with fewer individual flights. TripGuru should recompute any cheapest route where there is a shorter route in terms of the number of flights.
+- The impact is unpredictable. TripGuru should recompute all routes.
+- There is no impact. The cheapest routes between all pairs of cities remain unchanged.
+---
+Test 5 - Question 1
+Consider the network graph depicted in the figure consisting of source node $s$, destination node $t$, and $n$ disjoint paths going from $s$ to $t$, each such path consists of exactly $m$ arcs. (Hence, such a graph consists of $n(m-1)+2$ nodes and $nm$ arcs.) All minimum capacities are 0 and maximum capacities are 1. How many distinct minimum capacity cuts are there?
+{{:courses:b4m35ko:ko_t21.png}}
+- $\binom{m}{n}$
+- $m$
+- None of the other options is correct
+- $\binom{n(m-1)}{n}$
+- $n^m$
+- $\binom{n(m-1)}{m}$
+- $\binom{n}{m}$
+- $m^2$
+- $n$
+* $m^n$
+- $n^2$
+- 1
+- 0
+---
+Test 5 - Question 2
+Consider a network with zero minimum capacities. Which of the following claims are true and which are false?
+(i) If all arcs in a network have different maximum capacities, the network has a unique minimum cut.
+(ii) If all arcs in a network have different maximum capacities, the network has a unique maximum flow.
+- (i) true (ii) false
+* (i) false (ii) false
+- (i) true (ii) true
+- (i) false (ii) true
+---
+Test 5 - Question 3
+A matching $M$ is a maximal matching of $G=(V,E)$ if for every arc $(i,j) \notin M$, $M \cup \{(i,j)\}$ is not a matching. The cardinality of a matching $M$ is the number of arcs in the matching and is denoted as $|M|$. A matching is a maximum matching if it is of the largest cardinality among all matchings.
+(i) Does there exist a graph with a maximal matching $A$ and maximum matching $B$ such that $2 \cdot |A|=|B|$?
+(ii) In a weighted graph, a maximum weight matching is a matching of the largest sum of the weights of arcs in the matching among all matchings and a perfect matching is a matching that covers every vertex of the graph. Is maximum weight matching also a perfect matching?
+- (i) no (ii) yes
+- (i) yes (ii) yes
+* (i) yes (ii) no
+- (i) no (ii) no
+---
+Test 5 - Question 4
+Which of the following claims are true and which are false?
+(i) If $f$ is a maximum flow, then for every pair of arcs $(i, j)$ and $(j, i)$, either $f(i,j)=0$ or $f(j,i)=0$.
+(ii) Any network with zero minimum capacities always has a maximum flow $f$ for which, for every pair of arcs $(i, j)$ and $(j, i)$, either $f(i,j)=0$ or $f(j,i)=0$.
+* (i) false (ii) true
+- (i) true (ii) true
+- (i) true (ii) false
+- (i) false (ii) false
+---
+Test 5 - Question 5
+Consider the directed graph shown in the figure. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijkstra's shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex is updated only when a strictly shorter path to it is discovered.
+{{:courses:b4m35ko:ko_t24.png}}
+* S A C E T
+- S D T
+- S B D T
+- S A C D T
+- None of the other options is correct
+---
+Test 5 - Question 6
+Let $s$ and $t$ be two vertices in an undirected graph $G=(V,E)$ having all distinct positive edge weights. The congestion on a path is defined as the maximum of the edge weights on the path. We wish to find the path from $s$ to $t$ having minimum congestion. Which one of the following paths is always such a path of minimum congestion?
+- A Hamiltonian path (i.e., a path that visits all vertices) from $s$ to $t$.
+* A path from $s$ to $t$ in the minimum spanning tree (MST).
+- An Euler walk (i.e., an edge progression where no edge appears more than once) from $s$ to $t$.
+- A shortest path from $s$ to $t$.
+---
+Test 5 - Question 7
+Let $G=(V,E)$ be a directed, weighted graph with weight function $w:E \to \mathbb{R}$. For some function $f:V \to \mathbb{R}$, for each edge $(u,v) \in E$, define $w'(u,v)=w(u,v)+f(u)-f(v)$. Which one of the options completes the following statement so that it is TRUE? "The shortest paths in $G$ under $w$ are shortest paths under $w'$ too, ................"
+- if and only if $\forall u \in V, f(u) > 0$
+- if and only if $\forall u \in V, f(u) < 0$
+- if and only if $\forall u \in V, f(u)$ is the distance from $s$ to $u$ in the graph obtained by adding a new vertex $s$ to $G$ and edges of zero weight from $s$ to every vertex of $G$.
+* for every $f:V \to \mathbb{R}$
+---
+Test 6 - Question 1
+Consider the network graph depicted in the figure consisting of source node $s$, destination node $t$, and $n$ disjoint paths going from $s$ to $t$, each such path consists of exactly $m$ arcs. (Hence, such a graph consists of $n(m-1)+2$ nodes and $nm$ arcs.) All minimum capacities are 0 and maximum capacities are 1. How many distinct minimum capacity cuts are there?
+{{:courses:b4m35ko:ko_t21.png}}
+- 1
+- None of the other options is correct
+- $m$
+- $\binom{n}{m}$
+- $n^2$
+- $m^2$
+- $\binom{n(m-1)}{m}$
+- $\binom{m}{n}$
+- 0
+- $n^m$
+* $m^n$
+- $\binom{n(m-1)}{n}$
+---
+Test 6 - Question 2
+Let 5-tuple $(G,l,u,s,t)$ where $G=(V,E)$ be a network and let a minimum cut be induced by $A \subset V$. Which of the following claims are true and which are false?
+(i) If we multiply each arc capacity by a positive number, the minimum cut induced by $A$ is still a minimum cut.
+(ii) If we add a positive number to each arc capacity, the minimum cut induced by $A$ is still a minimum cut.
+* (i) true (ii) false
+- (i) true (ii) true
+- (i) false (ii) false
+- (i) false (ii) true
+---
+Test 6 - Question 3
+Consider a network $(G, l, u, c, b)$ with maximum flow $f$. We define a most vital arc of a network as an arc whose deletion causes the largest decrease in the maximum flow value. Which of the following claims is true?
+- An arc that does not belong to some minimum cut cannot be a most vital arc.
+- A most vital arc is an arc with the maximum value of $f(i,j)$.
+* A network might contain several most vital arcs.
+- A most vital arc is an arc with the maximum value of $f(i,j)$ among arcs belonging to some minimum cut.
+- A most vital arc is an arc with the maximum value of $u(i,j)$.
+---
+Test 6 - Question 4
+Let $\alpha \in \mathbb{N}$. Which of the following claims are true and which are false?
+(i) If the capacity of every arc in a network is an integer multiple of $\alpha$, then in every maximum flow, each arc flow will be an integer multiple of $\alpha$.
+(ii) If the capacity of every arc in a network is increased by $\alpha$ units, then the value of a maximum flow will increase by an integer multiple of $\alpha$.
+(iii) If the capacity of every arc in a network is increased by $\alpha$ units, then the value of a maximum flow will increase by $\alpha$.
+* (i) false (ii) false (iii) false
+- (i) false (ii) false (iii) true
+- (i) false (ii) true (iii) false
+- (i) true (ii) false (iii) true
+- (i) true (ii) true (iii) false
+- None of the other options is correct
+- (i) true (ii) false (iii) false
+---
+Test 6 - Question 5
+Consider the directed graph shown in the figure. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijkstra's shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex is updated only when a strictly shorter path to it is discovered.
+{{:courses:b4m35ko:ko_t24.png}}
+- S A C D T
+- S D T
+- S B D T
+- None of the other options is correct
+* S A C E T
+---
+Test 6 - Question 6
+Given a connected weighted undirected graph $G$ where weights of all edges are unique, i.e., no two edges have the same weights. Are the following statements true or false?
+(i) The shortest path from a source to a destination in such a graph is always unique.
+(ii) The minimum spanning tree (MST) of graph $G$ is always unique.
+(Hint: Recall how Prim's or Kruskal's algorithm works.)
+- (i) true (ii) true
+- (i) true (ii) false
+- (i) false (ii) false
+* (i) false (ii) true
+---
+Test 6 - Question 7
+An airline charges a fixed price for each individual flight. For each sequence of hopping flights, the ticket price is the sum of the fares of the individual flights. TripGuru has precalculated the cheapest routes between all pairs of cities so that it can offer an optimum choice instantly to customers visiting its website. Overnight, the government has added a 13% luxury service surcharge to the cost of each individual flight. Which of the following describes the impact of this surcharge on TripGuru's computation?
+* There is no impact. The cheapest routes between all pairs of cities remain unchanged.
+- The surcharge favors hopping flights with more individual flights. TripGuru should recompute any cheapest route where there is a longer route in terms of the number of flights.
+- The impact is unpredictable. TripGuru should recompute all routes.
+- The surcharge favors hopping flights with fewer individual flights. TripGuru should recompute any cheapest route where there is a shorter route in terms of the number of flights.
+---
+Additional Question A
+Consider a network $(G, l, u, c, b)$ with maximum flow $f$. We define a most vital arc of a network as an arc whose deletion causes the largest decrease in the maximum flow value. Which of the following claims is true?
+* A network might contain several most vital arcs.
+- A most vital arc is an arc with the maximum value of $f(i,j)$ among arcs belonging to some minimum cut.
+- A most vital arc is an arc with the maximum value of $u(i,j)$.
+- A most vital arc is an arc with the maximum value of $f(i,j)$.
+- An arc that does not belong to some minimum cut cannot be a most vital arc.
+---
+Additional Question B
+If all edges have the same positive weight in a directed graph, which algorithm will find a shortest path from one node to other nodes with the best time complexity?
+* Breadth-First Search
+- Bellman-Ford
+- Depth-First Search
+- Dijkstra
+---
+Additional Question C
+Given a directed acyclic graph (DAG), i.e., there exists a topological ordering. The graph consists of $n$ nodes and $m$ edges. What will be the time complexity for the single-source shortest path algorithm?
+- $O(n + n \log m)$
+- $O(n + \log m)$
+- $O(n \log n)$
+* $O(n + m)$
+- $O(n + \sqrt{m})$
+- $O(n)$
+- None of the other options is correct
+---
+Additional Question D
+Let $G=(V,E)$ be a weighted connected undirected graph with distinct positive edge weights. If every edge weight is increased by the same value, then which of the following statements is true?
+(i) Minimum spanning tree (MST) of $G$ does not change.
+(ii) Shortest path between any pair of vertices does not change.
+- (i) true (ii) true
+* (i) true (ii) false
+- (i) false (ii) true
+- (i) false (ii) false
+---
+Additional Question E
+(i) Does there exist a network $(G,l,u,c,b)$ where $G=(V,E)$ such that every minimum cost flow has a zero flow on the minimum cost arc from $E$?
+(ii) Does there exist a network $(G,l,u,c,b)$ where $G=(V,E)$ such that every minimum cost flow has a positive flow on the maximum cost arc from $E$?
+* (i) yes (ii) yes
+- (i) no (ii) yes
+- (i) yes (ii) no
+- (i) no (ii) no
+</questions>
+</flashcards>

Trace:

Differences

Search

Navigation

Print/export

Tools

QR Code