1. Introduction to Graph Theory

Graph theory is a branch of mathematics that studies the properties of graphs, which are mathematical structures used to model pairwise relations between objects. A graph consists of a set of vertices (also called nodes) and a set of edges that connect these vertices.

Graphs are used to model many types of relations and processes in physical, biological, social, and information systems, making graph theory one of the most versatile areas of mathematics with applications in computer science, electrical engineering, operations research, linguistics, and more.

2. Basic Concepts

Vertex (Node)

A vertex (or node) is the fundamental unit of a graph. It represents an object or entity in the model.

Edge

An edge is a connection between two vertices, representing a relationship or link between the corresponding objects.

Degree of a Vertex

The degree of a vertex is the number of edges connected to it. For directed graphs, we distinguish between in-degree (number of incoming edges) and out-degree (number of outgoing edges).

Path

A path in a graph is a sequence of vertices where each adjacent pair is connected by an edge. The length of a path is the number of edges in it.

Cycle

A cycle is a path that starts and ends at the same vertex, with no repeated edges or vertices (except the starting/ending vertex).

Connected Graph

A graph is connected if there is a path between every pair of vertices. Otherwise, it is disconnected.

3. Types of Graphs

Undirected Graph

In an undirected graph, edges have no direction. If vertex A is connected to vertex B, then vertex B is also connected to vertex A.

Directed Graph (Digraph)

In a directed graph, edges have a direction. If there is an edge from vertex A to vertex B, it doesn't necessarily mean there is an edge from B to A.

Weighted Graph

In a weighted graph, each edge has a weight or cost associated with it. These weights could represent distances, costs, capacities, etc.

Complete Graph

A complete graph is an undirected graph where every pair of vertices is connected by an edge. A complete graph with n vertices is denoted by K_n.

Bipartite Graph

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in the first set to a vertex in the second set.

Tree

A tree is a connected undirected graph with no cycles. A tree with n vertices has exactly n-1 edges.

Planar Graph

A planar graph is a graph that can be drawn on a plane without any edges crossing.

4. Graph Representation

There are several ways to represent a graph in a computer:

Adjacency Matrix

An adjacency matrix is a 2D array of size V×V where V is the number of vertices in the graph. The entry at position (i, j) is 1 if there is an edge from vertex i to vertex j, and 0 otherwise. For weighted graphs, the entry can be the weight of the edge.

Adjacency List

An adjacency list represents a graph as an array of linked lists. The index of the array represents a vertex, and each element in its linked list represents the vertices that are adjacent to it.

A -> B -> C
B -> A -> C -> D
C -> A -> B
D -> B
      

Edge List

An edge list is a collection of all the edges in the graph. Each edge is represented by a pair of vertices (or a triplet if the graph is weighted).

(A, B)
(A, C)
(B, C)
(B, D)
      

Comparison of Representations

5. Graph Traversal Algorithms

Graph traversal means visiting all the vertices of a graph in a particular order.

Breadth-First Search (BFS)

BFS explores all vertices at the present depth before moving on to vertices at the next depth level. It uses a queue data structure to keep track of vertices to visit next.

function BFS(graph, startVertex):
    let queue = new Queue()
    let visited = new Set()
    
    queue.enqueue(startVertex)
    visited.add(startVertex)
    
    while queue is not empty:
        let currentVertex = queue.dequeue()
        // Process currentVertex
        
        for each neighbor of currentVertex:
            if neighbor is not in visited:
                queue.enqueue(neighbor)
                visited.add(neighbor)
      

Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It can be implemented using recursion or a stack data structure.

function DFS(graph, startVertex, visited = new Set()):
    visited.add(startVertex)
    // Process startVertex
    
    for each neighbor of startVertex:
        if neighbor is not in visited:
            DFS(graph, neighbor, visited)
      

Applications of Graph Traversal

• Finding connected components in a graph
• Detecting cycles in a graph
• Solving puzzles like mazes
• Topological sorting of vertices in a directed acyclic graph (DAG)
• Finding paths between two vertices

6. Shortest Path Algorithms

Shortest path algorithms find the path with minimum total weight between two vertices in a weighted graph.

Dijkstra's Algorithm

Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative weights.

function dijkstra(graph, startVertex):
    let distances = {}  // Stores shortest distance from startVertex to every other vertex
    let previous = {}   // Stores previous vertex in the optimal path
    let pq = new PriorityQueue()  // Vertices to visit next, ordered by distance
    
    // Initialize distances
    for each vertex v in graph:
        if v equals startVertex:
            distances[v] = 0
            pq.enqueue(v, 0)
        else:
            distances[v] = INFINITY
            pq.enqueue(v, INFINITY)
        previous[v] = null
    
    while pq is not empty:
        let currentVertex = pq.dequeue()
        
        for each neighbor of currentVertex:
            let distance = distances[currentVertex] + weight(currentVertex, neighbor)
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                previous[neighbor] = currentVertex
                pq.decreaseKey(neighbor, distance)
    
    return { distances, previous }
      

Bellman-Ford Algorithm

Bellman-Ford algorithm finds the shortest paths from a source vertex to all other vertices in a weighted graph, even if the graph contains negative weight edges. It can also detect negative weight cycles.

function bellmanFord(graph, startVertex):
    let distances = {}  // Stores shortest distance from startVertex to every other vertex
    let previous = {}   // Stores previous vertex in the optimal path
    
    // Initialize distances
    for each vertex v in graph:
        if v equals startVertex:
            distances[v] = 0
        else:
            distances[v] = INFINITY
        previous[v] = null
    
    // Relax edges |V| - 1 times
    for i from 1 to |V| - 1:
        for each edge (u, v) with weight w in graph:
            if distances[u] + w < distances[v]:
                distances[v] = distances[u] + w
                previous[v] = u
    
    // Check for negative weight cycles
    for each edge (u, v) with weight w in graph:
        if distances[u] + w < distances[v]:
            throw "Graph contains a negative weight cycle"
    
    return { distances, previous }
      

Floyd-Warshall Algorithm

Floyd-Warshall algorithm finds the shortest paths between all pairs of vertices in a weighted graph, even with negative weights (but no negative cycles).

function floydWarshall(graph):
    let dist = new 2D array of size |V| × |V|
    
    // Initialize distances
    for each vertex i in graph:
        for each vertex j in graph:
            if i equals j:
                dist[i][j] = 0
            else if there is an edge from i to j:
                dist[i][j] = weight(i, j)
            else:
                dist[i][j] = INFINITY
    
    // Update distances considering each vertex as an intermediate
    for k from 0 to |V| - 1:
        for i from 0 to |V| - 1:
            for j from 0 to |V| - 1:
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    
    return dist
      

7. Minimum Spanning Trees

A minimum spanning tree (MST) is a subset of the edges of a connected, undirected weighted graph that connects all the vertices together with the minimum possible total edge weight, without forming cycles.

Kruskal's Algorithm

Kruskal's algorithm finds the MST by adding edges in order of increasing weight, skipping edges that would create a cycle.

function kruskal(graph):
    let result = new Graph()  // This will store the MST
    let edges = all edges in graph sorted by weight
    let disjointSet = new DisjointSet(all vertices in graph)
    
    for each edge (u, v) with weight w in edges:
        if disjointSet.find(u) != disjointSet.find(v):  // If adding this edge doesn't create a cycle
            result.addEdge(u, v, w)
            disjointSet.union(u, v)
    
    return result
      

Prim's Algorithm

Prim's algorithm starts with a single vertex and grows the MST one vertex at a time by adding the lowest weight edge that connects a vertex in the tree to a vertex outside the tree.

function prim(graph, startVertex):
    let result = new Graph()  // This will store the MST
    let visited = new Set()  // Set of vertices included in MST
    let pq = new PriorityQueue()  // Edges to consider next, ordered by weight
    
    visited.add(startVertex)
    
    // Add all edges connected to startVertex to priority queue
    for each edge (startVertex, v) with weight w in graph:
        pq.enqueue(edge, w)
    
    while pq is not empty and visited.size < |V|:
        let currentEdge = pq.dequeue()
        let (u, v) = currentEdge
        
        // If v is not visited, add this edge to MST
        if v is not in visited:
            result.addEdge(u, v, weight(u, v))
            visited.add(v)
            
            // Add all edges connected to v to priority queue
            for each edge (v, x) with weight w in graph:
                if x is not in visited:
                    pq.enqueue(edge, w)
    
    return result
      

8. Graph Coloring

Graph coloring is the process of assigning labels (colors) to elements of a graph subject to certain constraints. In its simplest form, vertex coloring requires that no two adjacent vertices share the same color.

Applications of Graph Coloring

• Map coloring
• Scheduling problems
• Register allocation in compilers
• Frequency assignment in mobile networks

Greedy Coloring Algorithm

The greedy coloring algorithm assigns colors to vertices in a fixed order, always using the first available color that does not conflict with already colored adjacent vertices.

function greedyColoring(graph):
    let result = {}  // Maps vertices to colors
    let colors = [1, 2, 3, ...]  // Available colors
    
    for each vertex v in graph:
        let usedColors = new Set()  
        
        // Collect colors of all adjacent vertices
        for each adjacent vertex u of v:
            if u is colored:
                usedColors.add(result[u])
        
        // Find the first color not used by adjacent vertices
        let chosenColor = first color in colors not in usedColors
        result[v] = chosenColor
    
    return result
      

Chromatic Number

The chromatic number of a graph is the minimum number of colors needed to color the vertices of a graph so that no two adjacent vertices share the same color.

9. Advanced Topics

function fordFulkerson(graph, source, sink):
    let residualGraph = copy of graph
    let maxFlow = 0
    
    while there is an augmenting path p from source to sink in residualGraph:
        let residualCapacity = minimum capacity of edges along path p
        maxFlow += residualCapacity
        
        for each edge (u, v) in path p:
            residualGraph[u][v] -= residualCapacity  // Forward edge
            residualGraph[v][u] += residualCapacity  // Backward edge
    
    return maxFlow
        

function topologicalSort(graph):
    let visited = new Set()
    let stack = new Stack()
    
    function dfs(vertex):
        visited.add(vertex)
        
        for each neighbor of vertex:
            if neighbor is not in visited:
                dfs(neighbor)
        
        stack.push(vertex)
    
    for each vertex v in graph:
        if v is not in visited:
            dfs(v)
    
    // Return vertices in reverse order of their finishing times
    let result = []
    while stack is not empty:
        result.push(stack.pop())
    
    return result
        

function kosaraju(graph):
    let visited = new Set()
    let stack = new Stack()
    
    // First DFS to fill stack with vertices in order of finishing time
    for each vertex v in graph:
        if v is not in visited:
            fillOrder(v, visited, stack)
    
    // Create the transpose graph (reverse all edges)
    let transposeGraph = reverse all edges in graph
    
    // Second DFS using vertices from stack
    visited.clear()
    let result = []
    
    while stack is not empty:
        let v = stack.pop()
        
        if v is not in visited:
            let component = new Set()
            dfs(transposeGraph, v, visited, component)
            result.push(component)
    
    return result
        

function findEulerianPath(graph):
    let result = []
    let stack = new Stack()
    let startVertex = find a valid starting vertex
    
    stack.push(startVertex)
    
    while stack is not empty:
        let currentVertex = stack.peek()
        
        if degree(currentVertex) > 0:
            let nextVertex = any adjacent vertex of currentVertex
            
            // Remove the edge from the graph
            removeEdge(graph, currentVertex, nextVertex)
            
            stack.push(nextVertex)
        else:
            result.push(stack.pop())
    
    return reverse of result
        

10. Real-world Applications

Social Network Analysis

Graphs are used to model social networks where vertices represent people and edges represent relationships. Various graph algorithms help identify communities, influential individuals, and information flow patterns.

Transportation Networks

Road systems, flight routes, and public transit networks are modeled as graphs. Shortest path algorithms help find optimal routes, and network flow algorithms help optimize capacity.

Computer Networks

The internet and local networks are modeled as graphs. Routing algorithms determine how data moves through these networks.

Biology and Chemistry

Protein-protein interaction networks, metabolic pathways, and molecular structures are represented as graphs.

Computer Science

Graphs are used in various areas of computer science including:

• Compiler optimization
• Database query optimization
• Image processing
• Natural language processing
• Artificial intelligence and machine learning

11. Interactive Quiz