What is a Graph?

In mathematics, a graph is a structure consisting of vertices (also called nodes or points) and edges (also called links or lines). The edges connect pairs of vertices, representing relationships between them. Graphs are fundamental mathematical structures used to model pairwise relations between objects.

Let’s create a simple visualization to understand what a graph looks like:

import networkx as nx
import matplotlib.pyplot as plt

# Create a simple graph
G = nx.Graph()
G.add_nodes_from(range(1, 8))  # Add nodes 1-7
G.add_edges_from([
    (1, 2), (1, 3), (2, 3), (3, 4), 
    (3, 5), (4, 5), (5, 6), (5, 7), (6, 7)
])

# Draw the graph
plt.figure(figsize=(10, 6))
pos = nx.spring_layout(G, seed=42)
nx.draw(G, pos, with_labels=True, 
        node_color='skyblue', 
        node_size=800,
        edge_color='gray',
        font_size=15,
        font_weight='bold')
plt.title("A Simple Graph", fontsize=16)
plt.axis('off')
plt.show()

Graph Components

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

Let’s break down these components visually:

# Create a simpler graph to highlight components
H = nx.Graph()
H.add_nodes_from(['A', 'B', 'C', 'D', 'E'])
H.add_edges_from([('A', 'B'), ('B', 'C'), ('C', 'D'), ('D', 'E'), ('E', 'A')])

plt.figure(figsize=(10, 6))
pos = nx.circular_layout(H)  # Position nodes in a circle

# Draw nodes
nx.draw_networkx_nodes(H, pos, 
                      node_color='lightgreen',
                      node_size=700)

# Draw edges
nx.draw_networkx_edges(H, pos,
                      width=2,
                      alpha=0.7)

# Draw labels
nx.draw_networkx_labels(H, pos, font_size=16, font_weight='bold')

# Add annotations
plt.text(-0.15, 0, "Vertex (Node)", fontsize=14, 
        bbox=dict(facecolor='white', alpha=0.7))
plt.text(0.5, 0, "Edge (Link)", fontsize=14,
        bbox=dict(facecolor='white', alpha=0.7))

plt.title("Basic Graph Components", fontsize=16)
plt.axis('off')
plt.show()

The mathematical notation for this graph would be:
- V = {A, B, C, D, E}
- E = {(A,B), (B,C), (C,D), (D,E), (E,A)}

Visual Representation

Graphs are typically visualized as a set of dots (vertices) connected by lines (edges). This visual representation makes it easy to understand the relationships between different entities.

Different layout algorithms provide different ways to arrange the nodes:

# Create a graph to demonstrate layouts
G_layout = nx.Graph()
G_layout.add_edges_from([
    (1, 2), (1, 3), (1, 4), (2, 3), 
    (3, 5), (3, 6), (4, 6), (5, 6)
])

fig, axes = plt.subplots(2, 2, figsize=(12, 10))

# Spring layout (force-directed)
pos_spring = nx.spring_layout(G_layout, seed=42)
nx.draw(G_layout, pos_spring, ax=axes[0, 0], 
        with_labels=True, node_color='lightblue', node_size=500)
axes[0, 0].set_title("Spring Layout")

# Circular layout
pos_circular = nx.circular_layout(G_layout)
nx.draw(G_layout, pos_circular, ax=axes[0, 1], 
        with_labels=True, node_color='lightgreen', node_size=500)
axes[0, 1].set_title("Circular Layout")

# Spectral layout
pos_spectral = nx.spectral_layout(G_layout)
nx.draw(G_layout, pos_spectral, ax=axes[1, 0], 
        with_labels=True, node_color='lightcoral', node_size=500)
axes[1, 0].set_title("Spectral Layout")

# Shell layout
pos_shell = nx.shell_layout(G_layout)
nx.draw(G_layout, pos_shell, ax=axes[1, 1], 
        with_labels=True, node_color='lightyellow', node_size=500)
axes[1, 1].set_title("Shell Layout")

plt.tight_layout()
plt.show()

Common Types of Graphs

Let’s explore and visualize the common types of graphs:

1. Undirected Graph

In an undirected graph, edges have no direction. The relationship between nodes is symmetric.

G_undirected = nx.Graph()
G_undirected.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'D')])

plt.figure(figsize=(6, 5))
nx.draw(G_undirected, with_labels=True, 
        node_color='lightblue', node_size=500,
        font_size=15, font_weight='bold')
plt.title("Undirected Graph", fontsize=16)
plt.show()

2. Directed Graph (Digraph)

In a directed graph, edges have direction, representing asymmetric relationships.

G_directed = nx.DiGraph()
G_directed.add_edges_from([('A', 'B'), ('B', 'C'), ('A', 'C'), ('C', 'A')])

plt.figure(figsize=(6, 5))
nx.draw(G_directed, with_labels=True, 
        node_color='lightgreen', node_size=500,
        font_size=15, font_weight='bold',
        arrows=True, arrowsize=15)
plt.title("Directed Graph (Digraph)", fontsize=16)
plt.show()

3. Weighted Graph

In a weighted graph, edges have associated values (weights).

G_weighted = nx.Graph()
weighted_edges = [('A', 'B', 5), ('A', 'C', 3), ('B', 'C', 2), ('C', 'D', 7)]
G_weighted.add_weighted_edges_from(weighted_edges)

plt.figure(figsize=(7, 6))
pos = nx.spring_layout(G_weighted, seed=42)
nx.draw(G_weighted, pos, with_labels=True, 
        node_color='lightcoral', node_size=500,
        font_size=15, font_weight='bold')

# Draw edge weights
edge_labels = {(u, v): d['weight'] for u, v, d in G_weighted.edges(data=True)}
nx.draw_networkx_edge_labels(G_weighted, pos, edge_labels=edge_labels, font_size=14)

plt.title("Weighted Graph", fontsize=16)
plt.axis('off')
plt.show()

4. Complete Graph

In a complete graph, every node is connected to every other node.

G_complete = nx.complete_graph(6)

plt.figure(figsize=(7, 6))
nx.draw(G_complete, with_labels=True, 
        node_color='lightyellow', node_size=500,
        font_size=15, font_weight='bold')
plt.title("Complete Graph (K6)", fontsize=16)
plt.show()

5. Bipartite Graph

In a bipartite graph, nodes can be divided into two sets with edges only between nodes of different sets.

# Create a bipartite graph
G_bipartite = nx.Graph()
# Add nodes with bipartite attribute
G_bipartite.add_nodes_from(['A', 'B', 'C'], bipartite=0)
G_bipartite.add_nodes_from([1, 2, 3, 4], bipartite=1)
# Add edges only between different sets
G_bipartite.add_edges_from([('A', 1), ('A', 2), ('B', 2), 
                            ('B', 3), ('C', 3), ('C', 4)])

plt.figure(figsize=(7, 6))
# Position nodes in two vertical lines
pos = nx.bipartite_layout(G_bipartite, ['A', 'B', 'C'])
# Draw nodes with different colors for each set
node_colors = ['lightblue' if node in ['A', 'B', 'C'] else 'lightgreen' 
               for node in G_bipartite.nodes()]
nx.draw(G_bipartite, pos, with_labels=True, 
        node_color=node_colors, node_size=500,
        font_size=15, font_weight='bold')
plt.title("Bipartite Graph", fontsize=16)
plt.show()

6. Tree

A tree is a connected graph with no cycles.

# Create a tree
G_tree = nx.Graph()
G_tree.add_edges_from([
    ('A', 'B'), ('A', 'C'), ('B', 'D'), 
    ('B', 'E'), ('C', 'F'), ('C', 'G')
])

plt.figure(figsize=(8, 6))
pos = nx.spring_layout(G_tree, seed=42)
nx.draw(G_tree, pos, with_labels=True, 
        node_color='lightblue', node_size=500,
        font_size=15, font_weight='bold')
plt.title("Tree", fontsize=16)
plt.show()

7. Cycle

A cycle is a graph where vertices form a closed chain.

# Create a cycle graph
G_cycle = nx.cycle_graph(6)

plt.figure(figsize=(6, 6))
pos = nx.circular_layout(G_cycle)
nx.draw(G_cycle, pos, with_labels=True, 
        node_color='lightgreen', node_size=500,
        font_size=15, font_weight='bold')
plt.title("Cycle Graph", fontsize=16)
plt.show()

Real-World Applications

Graph theory has applications in diverse fields. Let’s simulate a few examples:

# Create a social network
social_network = nx.Graph()
# Add friendships
friends = [
    ('Alice', 'Bob'), ('Alice', 'Carol'), ('Bob', 'Dave'),
    ('Carol', 'Eve'), ('Dave', 'Eve'), ('Eve', 'Frank'),
    ('Frank', 'Alice'), ('Frank', 'Carol')
]
social_network.add_edges_from(friends)

# Calculate degree (number of friends)
degrees = dict(social_network.degree())

plt.figure(figsize=(10, 8))
pos = nx.spring_layout(social_network, seed=42)
# Size nodes by number of connections
node_sizes = [degrees[node] * 300 + 300 for node in social_network.nodes()]
nx.draw(social_network, pos, with_labels=True,
        node_color='lightblue', node_size=node_sizes,
        font_size=12, font_weight='bold')
plt.title("Social Network - Node Size Reflects Number of Connections", fontsize=16)
plt.show()

Transportation Network

# Create a transportation network (cities connected by roads)
transport_net = nx.Graph()
# Add weighted edges (distances between cities)
roads = [
    ('New York', 'Boston', 215), ('New York', 'Philadelphia', 95),
    ('Philadelphia', 'Washington', 140), ('Boston', 'Providence', 50),
    ('Providence', 'New York', 180), ('Washington', 'Richmond', 110)
]
transport_net.add_weighted_edges_from(roads)

plt.figure(figsize=(12, 8))
pos = nx.spring_layout(transport_net, seed=10)
nx.draw(transport_net, pos, with_labels=True,
        node_color='lightcoral', node_size=700,
        font_size=12, font_weight='bold')

# Draw distances on edges
edge_labels = {(u, v): d['weight'] for u, v, d in transport_net.edges(data=True)}
nx.draw_networkx_edge_labels(transport_net, pos, edge_labels=edge_labels, 
                            font_size=11)
plt.title("Transportation Network with Distances (miles)", fontsize=16)
plt.show()

# Find shortest path from New York to Richmond
path = nx.shortest_path(transport_net, 'New York', 'Richmond', weight='weight')
print(f"Shortest path from New York to Richmond: {' → '.join(path)}")

# Calculate total distance
distance = nx.shortest_path_length(transport_net, 'New York', 'Richmond', weight='weight')
print(f"Total distance: {distance} miles")

Output:

Shortest path from New York to Richmond: New York → Philadelphia → Washington → Richmond
Total distance: 345 miles

Why Graphs Matter

Graphs provide a powerful abstraction for modeling and solving complex problems. Let’s visualize graph density to show how graphs can represent different levels of connectivity:

# Generate graphs with different densities
fig, axes = plt.subplots(1, 3, figsize=(18, 6))

# Sparse graph (low density)
sparse = nx.gnp_random_graph(15, 0.1, seed=42)  # Low probability of edges
nx.draw(sparse, ax=axes[0], with_labels=True, 
        node_color='lightblue', node_size=300)
axes[0].set_title(f"Sparse Graph\nDensity: {nx.density(sparse):.3f}", fontsize=14)

# Medium density graph
medium = nx.gnp_random_graph(15, 0.3, seed=42)  # Medium probability of edges
nx.draw(medium, ax=axes[1], with_labels=True, 
        node_color='lightgreen', node_size=300)
axes[1].set_title(f"Medium Density Graph\nDensity: {nx.density(medium):.3f}", fontsize=14)

# Dense graph
dense = nx.gnp_random_graph(15, 0.7, seed=42)  # High probability of edges
nx.draw(dense, ax=axes[2], with_labels=True, 
        node_color='lightcoral', node_size=300)
axes[2].set_title(f"Dense Graph\nDensity: {nx.density(dense):.3f}", fontsize=14)

plt.tight_layout()
plt.show()

Graphs allow us to:

Represent complex relationships in an intuitive way
Apply well-established algorithms to solve problems
Analyze network properties and behaviors
Optimize flows, paths, and connections
Discover patterns and clusters in connected data

Try It Yourself!

Now that you understand the basics of graphs, try experimenting with our interactive playground where you can create and manipulate graphs in real-time. You can add nodes, create edges, and run algorithms to see how they work.

In future posts, we’ll explore specific graph algorithms and their applications in more detail.

References

Diestel, R. (2017). Graph Theory (5th ed.). Springer.
Newman, M. E. J. (2010). Networks: An Introduction. Oxford University Press.
Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory. Springer.

What is a Graph?

What is a Graph?

Graph Components

Visual Representation

Common Types of Graphs

1. Undirected Graph

2. Directed Graph (Digraph)

3. Weighted Graph

4. Complete Graph

5. Bipartite Graph

6. Tree

7. Cycle

Real-World Applications

Social Network Analysis

Transportation Network

Why Graphs Matter

Try It Yourself!

References