Skip to main content

Introduction to Graph Theory

What is Graph Theory?​

Graph theory is a branch of mathematics that deals with the study of graphs, which are mathematical structures used to model relationships between objects. In the context of computer science, graph theory plays a crucial role in various fields such as algorithms, data structures, network analysis, and more.

Key Concepts​

  1. Definition: A graph consists of two main components:

    • Vertices (also called nodes): These represent points or entities in the graph.
    • Edges: These represent connections or relationships between vertices.

  2. Types of Graphs:

    • Undirected Graphs: Edges have no direction.
    • Directed Graphs: Edges have direction.
    • Weighted Graphs: Each edge has a numerical weight associated with it.

  3. Graph Terminology:

    • Adjacent: Two vertices connected by an edge.
    • Incident: An edge connected to a vertex.
    • Neighbors: The set of all vertices adjacent to a given vertex.

  4. Graph Representations:

    • Adjacency Matrix: Represents edges as entries in a matrix.
    • Adjacency List: Represents edges as a list of neighboring vertices.

  5. Graph Properties:

    • Connectedness: Whether there exists a path between every pair of vertices.
    • Cycles: Paths that start and end at the same vertex.
    • Bipartite: Graphs whoe vertices can be divided into two disjoint sets.

Basic Graph Operations​

Adding and Removing Vertices/Edges​

# Adding a vertex to an undirected graph represented as an adjacency list

# Initialize the graph
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'C'],
    'C': ['A', 'B']
}

# Add a new vertex 'D' with no edges
graph['D'] = []

# Print the updated graph
print(graph)

Removing a vertex:​

# Removing vertex 'B' from the graph

def remove_vertex(graph, vertex):
    if vertex in graph:
        del graph[vertex]  # Remove the vertex
        for v in graph:     # Remove any edges to the vertex
            if vertex in graph[v]:
                graph[v].remove(vertex)

# Remove vertex 'B'
remove_vertex(graph, 'B')

# Print the updated graph
print(graph)

Adding and Removing Edges​

To add an edge between two vertices:

# Adding an edge between 'A' and 'D'
graph['A'].append('D')
graph['D'].append('A')

# Print the updated graph
print(graph)

To remove an edge:

# Removing the edge between 'A' and 'D'
graph['A'].remove('D')
graph['D'].remove('A')

# Print the updated graph
print(graph)

Graph Traversal​

Depth-First Search (DFS)​

DFS is an algorithm used to traverse or search through graph structures. It explores as far down as possible along each branch before backtracking.

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

# Perform DFS starting from vertex 'A'
dfs(graph, 'A')

Breadth-First Search (BFS)​

BFS explores all the neighbors of a vertex before moving to the next level of neighbors.

from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    
    while queue:
        vertex = queue.popleft()
        if vertex not in visited:
            visited.add(vertex)
            print(vertex)
            queue.extend([neighbor for neighbor in graph[vertex] if neighbor not in visited])

# Perform BFS starting from vertex 'A'
bfs(graph, 'A')

Applications of Graph Theory​

  1. Shortest Path Algorithms: Algorithms like Dijkstra's and Bellman-Ford are used to find the shortest path between vertices.
  2. Network Flow: Algorithms like Ford-Fulkerson are used to calculate the maximum flow in a network.
  3. Graph Coloring: Used to color graphs so that no two adjacent vertices have the same color, important in scheduling problems.
  4. Social Networks: Graph theory is used to analyze relationships in social networks, like finding clusters of friends.
  5. Web Search Engines: Search engines like Google use PageRank, an algorithm based on graph theory, to rank web pages.

Graph theory is a powerful tool with a wide range of applications in computer science, helping solve complex problems efficiently through a graphical representation of relationships.