Week4 - Graph algorithms

Question 1

Conditions for topological sorting

Answer 1

DAG:

Directed - Directed Graph
Acyclic

G is just graph

said to be a DAG if :
- irreflexive ( no self loops )
- does not contain any cycles of length >= 2

hint when you do DFS part look for a vertex with no in degree or small in degree

Question 2

very good video on topological sorting must watch

Answer 2

https://youtu.be/yYW6lQ1ajx4?si=vpi5MSyPXn5FFqpy

Question 3

Q1: What is a Strongly Connected Component (SCC)?

Answer 3

A strongly connected component is a maximal subset C of vertices such that for all u, v in C, there is a path from u to v and a path from v to u.

Question 4

JUST READ VERY GOOD NOYTES

Answer 4

Topological sorting (which is typically used to determine task ordering and concurrency) only works on DAGs

When you have cycles, it means tasks depend on each other in a circular way, which creates a logical impossibility for ordering

You can’t determine a valid sequence when Task A needs Task B to complete, but Task B also needs Task A to complete

Your peer suggests the solution would be to:

Find the Strongly Connected Components (SCCs) - these are groups of nodes that form cycles
Treat each SCC as a single unit, which would create a DAG
Then use topological sorting on this new DAG to determine which tasks can be performed concurrently

This is a valid approach because tasks within a cycle must effectively be performed together or considered as one unit, since they can’t be sequenced independently.

Question 5

: How is a binary relation ( ~) defined for Strongly Connected Components?

Answer 5

A binary relation ~ is defined such that u ~ v if u = v or there exists a path from u to v and a path from v to u.

Question 6

What does the term “maximal subset” mean in the context of SCCs?

Answer 6

A maximal subset is the largest possible subset C of vertices where all vertices are strongly connected to each other. Adding any vertex outside C would break the property of strong connectivity.

Question 7

difference between kruskals algorithm and primms

Answer 7

In kruskal we dont care if minimums spanning tree is connected we are just growing lots of smaller trees that come together to form one final tree

but in prims we do

Question 8

if all edges are distinct ( different weights ) how many minimum spanning trees

Answer 8

If all edge weights in a graph are distinct, there will be exactly one unique Minimum Spanning Tree (MST). This is because greedy algorithms (like Kruskal’s or Prim’s) always have a clear choice for the smallest edge, with no ties or ambiguity. The cycle and cut properties also ensure a unique solution.