Algorithm Chapter 4 Graphs Notes, Polytechnic 3rd Sem Algorithm Notes

4. Graphs

Graphs are an essential concept in computer science and mathematics, representing networks of interconnected nodes. They are widely used to model real-world systems such as social networks, transportation systems, communication networks, and more. A graph is a set of vertices (or nodes) connected by edges (or links), which can be directed or undirected.

4.1. Definition of a Directed and Undirected Graph

A graph is formally defined as $G = (V, E)$, where $V$ is a set of vertices and $E$ is a set of edges connecting the vertices.

• Directed Graph (Digraph): In a directed graph, the edges have a direction, meaning they go from one vertex to another. If there is an edge from vertex A to vertex B, it does not necessarily mean that there is an edge from B to A.

  • Example: A one-way street network, where each street has a specific direction.

• Undirected Graph: In an undirected graph, the edges do not have a direction. An edge between vertex A and vertex B means that A is connected to B, and B is connected to A.

  • Example: A friendship network where a connection between two people is mutual.

4.1.1. Paths

A path in a graph is a sequence of vertices where each consecutive pair is connected by an edge. The path can be of various lengths:

• Simple Path: A path that does not repeat any vertices.
• Cycle: A path where the first and last vertices are the same, forming a closed loop.
• In a directed graph, paths follow the direction of edges.

4.1.2. Cycles

A cycle is a closed path where the first and last vertices are the same, and no other vertex is repeated. Cycles are important in various fields:

• Undirected graph cycles: If any path forms a loop, it is a cycle.
• Directed graph cycles: The direction of the edges must be followed, and the cycle occurs when a vertex is reachable from itself through a series of directed edges.

4.1.3. Spanning Trees

A spanning tree is a subgraph of an undirected graph that connects all the vertices with the minimum number of edges and contains no cycles.

• Properties of Spanning Trees:
  • It includes all vertices of the original graph.
  • It is acyclic, meaning it contains no loops or cycles.
  • It has exactly $V-1$ edges, where $V$ is the number of vertices in the graph.

Applications of Spanning Trees:

• Network design (minimizing the wiring or cabling cost).
• Tree-like data structures for efficient searching and traversing.

4.2. Directed Acyclic Graphs (DAG)

A Directed Acyclic Graph (DAG) is a directed graph with no cycles, meaning that there is no way to start at any vertex and follow a sequence of directed edges to return to the same vertex.

• Properties of DAGs:
  • There is a direction associated with each edge.
  • It contains no cycles (hence, acyclic).
  • It is often used to represent dependencies between tasks.

Applications of DAGs:

• Task Scheduling: In project management, DAGs represent tasks that depend on other tasks being completed first.
• Version Control Systems: DAGs are used in systems like Git to represent different versions of files where changes depend on previous commits.
• Compilation Process: Compilers use DAGs to manage the order in which instructions are executed.

4.3. Topological Sorting

Topological Sorting is an ordering of the vertices in a Directed Acyclic Graph (DAG) such that for every directed edge $u \rightarrow v$, vertex $u$ comes before $v$ in the ordering.

• Algorithm: The process can be done using Depth-First Search (DFS) or Kahn’s algorithm.
  • DFS-based method: Perform a DFS traversal on the DAG, and whenever a vertex finishes processing, add it to the front of the ordering. This gives a valid topological sort.
  • Kahn’s Algorithm: Start with nodes that have no incoming edges, process them, and remove their outgoing edges. Repeat until all vertices are processed.

Applications of Topological Sorting:

• Task Scheduling: To determine the order of task execution where some tasks must be done before others.
• Prerequisite Systems: In academic course planning, topological sorting helps determine the order in which courses with prerequisites should be taken.

4.4. Minimum Spanning Tree Algorithms

A Minimum Spanning Tree (MST) of a graph is a spanning tree with the minimum possible total edge weight. It connects all vertices in a graph while minimizing the sum of the edge weights.

Common Algorithms for MST:

1. Kruskal’s Algorithm: A greedy algorithm that sorts all the edges of the graph in increasing order by weight and adds them one by one to the spanning tree, ensuring no cycles are formed.
   • Time complexity: $O(E \log E)$, where $E$ is the number of edges.
2. Prim’s Algorithm: Another greedy algorithm that grows the spanning tree one vertex at a time, always choosing the smallest edge that connects a vertex in the tree to a vertex outside the tree.
   • Time complexity: $O(E \log V)$ using a priority queue, where $V$ is the number of vertices.

Applications of MST:

• Network design (minimizing the cost of laying cables, pipelines, etc.).
• Clustering in machine learning.

4.4.1. Shortest Path Algorithms: Dijkstra’s Algorithm

Dijkstra’s Algorithm is used to find the shortest path from a source vertex to all other vertices in a weighted graph. The algorithm assumes that edge weights are non-negative.

How Dijkstra’s Algorithm Works:

1. Initialize the distance to the source vertex as 0 and all other vertices as infinity.
2. Use a priority queue to explore the vertex with the smallest tentative distance.
3. For each adjacent vertex, update its tentative distance if a shorter path through the current vertex is found.
4. Continue until all vertices are processed.

Time Complexity: $O(E \log V)$, where $E$ is the number of edges and $V$ is the number of vertices.

Applications of Dijkstra’s Algorithm:

• Routing and navigation: Finding the shortest path in road networks, flight paths, etc.
• Network packet routing: In telecommunications, Dijkstra’s algorithm helps determine the shortest path for packet transmission.

4.4.2. Flow-Based Algorithms

Flow-based Algorithms deal with optimizing the flow through a network, where each edge has a capacity and we want to find the maximum flow from a source vertex to a sink vertex.

Key Flow-Based Algorithms:

1. Ford-Fulkerson Algorithm: This method computes the maximum flow in a flow network by repeatedly finding augmenting paths and increasing the flow until no more augmenting paths can be found.

   • Time complexity: $O(E \times f)$, where $f$ is the maximum flow in the network.

2. Edmonds-Karp Algorithm: A specific implementation of Ford-Fulkerson that uses Breadth-First Search (BFS) to find the shortest augmenting paths in terms of the number of edges.

   • Time complexity: $O(VE^2)$, where $V$ is the number of vertices and $E$ is the number of edges.

Applications of Flow-Based Algorithms:

• Network design: Optimizing the flow of resources (such as data or goods) through a network.
• Transportation: Determining the maximum number of vehicles that can travel through a set of routes without congestion.
• Bipartite Matching: Finding the maximum matching in bipartite graphs using flow-based techniques.

---

These concepts are fundamental in graph theory and are applied in many areas, such as computer networks, operations research, logistics, and more. Understanding these algorithms and structures will help in designing efficient systems for solving complex real-world problems.