Maths 1 Week 11 Summary

📚

Graph Theory Summary

Directed Acyclic Graph (DAG)

A Directed Acyclic Graph (DAG) is a graph that is directed and contains no cycles. This means that it is impossible to start at any vertex and follow a sequence of edges that eventually loops back to the starting vertex.

Topological Sorting

Topological sorting of a DAG is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. This is useful for scheduling tasks, resolving symbol dependencies in linkers, etc.

Longest Path in DAG

Finding the longest path in a DAG can be done in linear time using topological sorting. Since DAGs have no cycles, the longest path problem is simpler compared to general graphs.

Shortest Path Algorithms

Shortest path algorithms are used to find the shortest path between vertices in a graph. Common algorithms include:

• Dijkstra's Algorithm: Finds the shortest path from a single source vertex to all other vertices in a graph with non-negative edge weights.
• Bellman-Ford Algorithm: Computes shortest paths from a single source vertex to all other vertices in a graph, even with negative edge weights. It can detect negative weight cycles.
• Floyd-Warshall Algorithm: Finds shortest paths between all pairs of vertices in a graph. It uses dynamic programming and can handle negative weights but not negative cycles.

Dijkstra's Algorithm

Dijkstra's algorithm is a greedy algorithm that finds the shortest path from a source vertex to all other vertices in a graph with non-negative edge weights. It uses a priority queue to repeatedly select the vertex with the smallest distance and update the distances of its neighbors.

Bellman-Ford Algorithm

The Bellman-Ford algorithm computes shortest paths from a single source vertex to all other vertices in a graph, even if the graph has negative edge weights. It iteratively relaxes all edges and can detect negative weight cycles.

Floyd-Warshall Algorithm

The Floyd-Warshall algorithm finds shortest paths between all pairs of vertices in a graph. It uses a dynamic programming approach to iteratively improve the shortest path estimates by considering all possible paths through the graph.

Difference Between Bellman-Ford and Floyd-Warshall

While both algorithms can handle graphs with negative weights, they differ in their approach and use cases:

• Bellman-Ford: Single-source shortest path algorithm, suitable for graphs with negative weights and capable of detecting negative cycles.
• Floyd-Warshall: All-pairs shortest path algorithm, uses dynamic programming and is simpler to implement but less efficient for large graphs.

Minimum Cost Spanning Tree

A Minimum Spanning Tree (MST) of a graph is a subset of the edges that connects all vertices together, without any cycles and with the minimum possible total edge weight. Two common algorithms to find the MST are:

• Kruskal's Algorithm: A greedy algorithm that sorts all edges by weight and adds them one by one to the MST, ensuring no cycles are formed.Prim's Algorithm: Another greedy algorithm that starts with a single vertex and grows the MST by adding the smallest edge that connects a vertex in the MST to a vertex outside the MST.

Kruskal's Algorithm

Kruskal's algorithm builds the MST by sorting all edges and adding them one by one, ensuring no cycles are formed. It uses a disjoint-set data structure to efficiently manage the connected components of the graph.

Prim's Algorithm

Prim's algorithm starts with a single vertex and grows the MST by repeatedly adding the smallest edge that connects a vertex in the MST to a vertex outside the MST. It is typically implemented using a priority queue.