Introduction to Graph Theory

Graph theory is a fascinating branch of mathematics that deals with the study of graphs, which are mathematical structures used to model pairwise relationships between objects. Graphs consist of nodes (or vertices) connected by edges (or links).

Let’s visualize a simple graph:

import networkx as nx
import matplotlib.pyplot as plt

# Create a simple graph
G = nx.Graph()
G.add_edges_from([
    (1, 2), (1, 5), (2, 3), (2, 5),
    (3, 4), (4, 5), (4, 6)
])

# Visualize the graph
plt.figure(figsize=(8, 6))
pos = nx.spring_layout(G, seed=42)
nx.draw(G, pos, with_labels=True, node_color='lightblue', 
        node_size=500, edge_color='gray', 
        font_size=15, font_weight='bold')
plt.title("A Simple Graph")
plt.axis('off')
plt.show()

Basic Concepts

Let’s understand some basic concepts of graph theory:

Vertices and Edges

A graph G can be formally defined as G = (V, E), where:
- V is a set of vertices (nodes)
- E is a set of edges, which are pairs of vertices

For example, in a social network graph:
- Each person is represented by a vertex
- A friendship between two people is represented by an edge connecting their respective vertices

We can define this mathematically:

$G = (V, E)$

Where:
- $V = \{v_1, v_2, …, v_n\}$ is the set of vertices
- $E = \{(v_i, v_j) | v_i, v_j \in V\}$ is the set of edges

Types of Graphs

There are several types of graphs with different properties:

Undirected Graph: Edges have no orientation (Facebook friendships)
Directed Graph (Digraph): Edges have orientation (Twitter follows)
Weighted Graph: Edges have weights/costs (Road networks with distances)
Complete Graph: Every vertex is connected to every other vertex
Bipartite Graph: Vertices can be divided into two sets where no vertices within the same set are adjacent

Let’s visualize some of these graph types:

# Create figure with subplots
fig, axes = plt.subplots(2, 2, figsize=(12, 10))

# 1. Undirected Graph
G_undirected = nx.Graph()
G_undirected.add_edges_from([(1, 2), (1, 3), (2, 3), (3, 4)])
pos_undirected = nx.spring_layout(G_undirected, seed=42)
nx.draw(G_undirected, pos_undirected, ax=axes[0, 0], with_labels=True, 
        node_color='lightblue', node_size=500)
axes[0, 0].set_title("Undirected Graph")

# 2. Directed Graph
G_directed = nx.DiGraph()
G_directed.add_edges_from([(1, 2), (2, 3), (3, 1), (3, 4)])
pos_directed = nx.spring_layout(G_directed, seed=42)
nx.draw(G_directed, pos_directed, ax=axes[0, 1], with_labels=True,
        node_color='lightgreen', node_size=500, 
        arrowstyle='->', arrowsize=15)
axes[0, 1].set_title("Directed Graph")

# 3. Complete Graph
G_complete = nx.complete_graph(5)
pos_complete = nx.spring_layout(G_complete, seed=42)
nx.draw(G_complete, pos_complete, ax=axes[1, 0], with_labels=True, 
        node_color='lightcoral', node_size=500)
axes[1, 0].set_title("Complete Graph (K5)")

# 4. Bipartite Graph
G_bipartite = nx.Graph()
G_bipartite.add_nodes_from([1, 2, 3], bipartite=0)  # First group
G_bipartite.add_nodes_from([4, 5, 6, 7], bipartite=1)  # Second group
G_bipartite.add_edges_from([(1, 4), (1, 5), (2, 5), (2, 6), (3, 6), (3, 7)])
pos_bipartite = nx.bipartite_layout(G_bipartite, [1, 2, 3])
nx.draw(G_bipartite, pos_bipartite, ax=axes[1, 1], with_labels=True, 
        node_color=['lightblue', 'lightblue', 'lightblue', 'lightgreen', 'lightgreen', 'lightgreen', 'lightgreen'],
        node_size=500)
axes[1, 1].set_title("Bipartite Graph")

plt.tight_layout()
plt.show()

Why Study Graphs?

Graph theory has numerous applications across various fields:

Computer Science: Network routing, database design, compiler optimization
Social Sciences: Modeling social networks and relationships
Biology: Protein interaction networks, ecological systems
Transportation: Optimizing routes, traffic flow analysis
Telecommunications: Network design and optimization
Operations Research: Scheduling, resource allocation

Here’s a real-world example of analyzing a social network:

# Create a simple social network graph
social_graph = nx.Graph()

# Add friendship relationships
friendships = [
    ('Alice', 'Bob'), ('Alice', 'Carol'), ('Alice', 'David'),
    ('Bob', 'Eve'), ('Bob', 'Frank'), ('Carol', 'David'),
    ('David', 'Eve'), ('Eve', 'Frank'), ('Frank', 'Grace')
]
social_graph.add_edges_from(friendships)

# Calculate degree centrality (number of connections)
centrality = nx.degree_centrality(social_graph)

# Visualize the social network
plt.figure(figsize=(10, 8))
pos = nx.spring_layout(social_graph, seed=42)

# Size nodes by their centrality
node_sizes = [centrality[node] * 3000 + 300 for node in social_graph.nodes()]

nx.draw(social_graph, pos, with_labels=True, 
        node_color='lightblue', node_size=node_sizes,
        font_size=12, font_weight='bold')

plt.title("Simple Social Network - Node Size Represents Centrality")
plt.show()

Getting Started with Algorithms

Some fundamental algorithms in graph theory include:

Breadth-First Search (BFS): Explores neighbor nodes first before moving to next level
Depth-First Search (DFS): Explores as far as possible along each branch before backtracking
Dijkstra’s Algorithm: Finds the shortest path between nodes in a weighted graph
Minimum Spanning Tree (Kruskal’s, Prim’s): Finds a subset of edges that forms a tree including every vertex with minimum total edge weight

Let’s implement a simple Breadth-First Search:

def bfs(graph, start):
    """Simple BFS implementation"""
    visited = set([start])
    queue = [start]
    traversal_order = [start]

    while queue:
        current = queue.pop(0)
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
                traversal_order.append(neighbor)

    return traversal_order

# Create a simple graph as an adjacency list
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# Run BFS starting from 'A'
bfs_result = bfs(graph, 'A')
print("BFS traversal starting from 'A':", ' -> '.join(bfs_result))

Output:

BFS traversal starting from 'A': A -> B -> C -> D -> E -> F

Mathematical Representation

Graphs can be represented in various ways:

Adjacency Matrix

An adjacency matrix is a square matrix where each element (i, j) represents an edge from vertex i to vertex j:

$A = \\begin{pmatrix} 0 & 1 & 1 & 0 \\\\ 1 & 0 & 1 & 1 \\\\ 1 & 1 & 0 & 1 \\\\ 0 & 1 & 1 & 0 \\end{pmatrix}$

# Create a simple graph
simple_graph = nx.Graph()
simple_graph.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'C'), ('B', 'D'), ('C', 'D')])

# Get adjacency matrix
adj_matrix = nx.adjacency_matrix(simple_graph).todense()

# Display the matrix
print("Adjacency Matrix:")
print(adj_matrix)

# Visualize the graph
plt.figure(figsize=(6, 6))
pos = nx.spring_layout(simple_graph, seed=42)
nx.draw(simple_graph, pos, with_labels=True, node_color='lightblue', 
        node_size=500, font_size=15, font_weight='bold')
plt.title("Graph Represented by Adjacency Matrix")
plt.show()

Output:

Adjacency Matrix:
[[0 1 1 0]
 [1 0 1 1]
 [1 1 0 1]
 [0 1 1 0]]

Adjacency List

An adjacency list represents a graph as a collection of lists, one for each vertex, containing the vertices adjacent to it:

A: [B, C]
B: [A, C, D]
C: [A, B, D]
D: [B, C]

Conclusion

Graph theory provides powerful tools for modeling and analyzing interconnected systems. In future posts, we’ll explore these algorithms in detail and implement them in our interactive playground. We’ll also dive deeper into specific applications and advanced topics in graph theory.

Stay tuned for our next post on graph traversal algorithms!

References

Bondy, J. A., & Murty, U. S. R. (1976). Graph theory with applications. North-Holland.
Wilson, R. J. (1996). Introduction to Graph Theory. Longman.
West, D. B. (2000). Introduction to Graph Theory (2nd ed.). Prentice Hall.