Exercises A¶

Note

You must complete these exercises by Wednesday of W12.

Exercise 6.1.1¶

Give several data structures that can be used to represent an undirected \(G\) graph with \(n\) nodes (vertex) and \(m\) arcs (edges).

What are the complexities of the elementary operations Iterable<Integer> adj(int v) and addEdge(int v, int w)?

Exercise 6.1.2¶

A graph is bipartite if its nodes can be divided into two disjoint sets so that there is no arc between two nodes of the same set.

Propose a method to test if a graph is bipartite and if so who would find such a partition. What is the complexity of your algorithm? Hint: use a DFS.

Exercise 6.1.3¶

Prove that any connected graph has a node whose removal (including incident arcs) would not disconnect the graph. Write a method that finds such a node. Hint: use a DFS and node marking.

Exercise 6.1.4 (Inginious)¶

Let be an undirected and weightless graph \(G\) whose arcs represent the possible elementary moves of a robot in a maze from all possible positions (nodes). Given the current position and a node, implement method to find a path to the exit that minimizes the number of elementary moves: Maze. What is the complexity of your method? Does it depend on the implementation of the graph (for example if it is an adjacency matrix?)

Exercise 6.1.5¶

The EPL course syllabus lists the prerequisites for each course. You want to make sure that all courses can be taken, i.e. that there is no cycle of dependency between courses.

What method do you propose to perform this test? What would be the time complexity of your method?

Exercise 6.1.6¶

Develop (write the code) a topological sorting algorithm for a directed graph that maintains an array of the size of the number of nodes with each entry corresponding to the in-degree of each node. Your algorithm also maintains a queue of sources (nodes with an in-degree of 0). Initialize these two structures in a single pass on all edges. Then perform the following operations until the source queue becomes empty:

remove a source from the queue and mark it.
decrement the in-degree of the adjacent destinations of the node marked in the previous step.
if the in-degree of a node becomes 0, insert it in the source queue.

Is it possible to detect whether the topological sort is unique? What is the time complexity of your algorithm?

Exercise 6.1.7¶

Let \(G(V,E)\) be an undirected graph with weights on which a minimum spanning tree has been computed. Then \(k\) arcs have been randomly removed from this MST. Write a method to retrieve an MST from the partial MST. The final MST does not have to be identical to the original, only the remaining \(V-1-k\) arcs must at least be present.

On what important property(ies) of MSTs is your algorithm based? What is the complexity of your method?

Exercise 6.1.8¶

Let \(G(V,E)\) be an undirected graph with weight on which a minimum spanning tree has been computed. The edge \(e \in E\) of weight \(w\) is not part of this MST. Can you recompute an MST that would include \(e\) by adapting the original MST? Describe your algorithm (code). What is the time complexity? Hint: DFS on the original MST.

Exercise 6.1.9¶

Could java.util.PriorityQueue be used to effectively implement Dijkstra? If not, why not? What would be the complexity of using this priority queue?

Exercise 6.1.10¶

Explain why DijkstraSP does not support arcs with negative weight? Would the result be wrong or would the complexity no longer be guaranteed? Show an example of input that illustrates the problem.

Exercise 6.1.11¶

Let \(G\) be a graph with potentially negative weights but there is no negative cycle. I am looking for the shortest path between a \(u\) node and a \(v\) node. I have at my disposal an implementation of Dijkstra which does not allow to manage negative weights. So I just have to increase all the weights by the same amount corresponding to the absolute value of the smallest weight and apply Dijkstra to the and to apply Dijkstra on this graph. Is this method valid? If yes, prove it. If not, show a counter example.

Exercise 6.1.12¶

Let \(G\) be a graph with positive weights. I am looking for the longest path between a \(u\) node and a \(v\) node. I have at my disposal the Bellman-Ford implementation (which supports negative weights). I just need to compute the shortest path on the same graph with the opposite weights. Is this method valid? If not, can you propose a method to compute the longest path? Does your method apply to all graphs? If not, what particular types of graphs can it handle?

Exercise 6.1.13 (Inginious)¶

Implement a Digraph Data Structure

Exercise 6.1.14 (Inginious)¶

Implement a Depth First Search

Exercise 6.1.15 (Inginious)¶

Implement the computation of the number of connected components in a Graph: ConnectedComponents

Exercise 6.1.16 (Inginious)¶

A programming exercise on finding the the relations to forbid in a contact network to satisfy the belgian covid rules: Covid bubbles

Exercise 6.1.17 (Inginious)¶

A programming exercise on BFS from multiple sources: BFS multiple sources

Exercise 6.1.18 (Inginious)¶

A programming exercise on shortest path in an implicit graph: Global Warming Path

Exercise 6.1.19 (Inginious)¶

Revisit your computation of the number of islands but this time using DFS rather than union-find Global Warming Island