Now that you understand the conceptual foundation from Euler’s work, let’s explore how to represent and analyze networks computationally. Given a network of any size, our goal is to create a function that can tell us whether the network has an Euler path or not.
def has_euler_path(A):
"""
Check if a graph has an Euler path based on node degrees.
Complete this function based on Euler's theorem.
A: network (assumed to be an adjacency matrix)
return: True if the network has an Euler path, False otherwise
"""
# Calculate degrees of all nodes
degrees = A.sum(axis=1)
# Count nodes with odd degrees
odd_degree_count = 0
for degree in degrees:
if degree % 2 != 0:
odd_degree_count += 1
# According to Euler's theorem, an Euler path exists if:
# 1. The graph is connected (we assume this for now)
# 2. Exactly 0 or 2 nodes have odd degrees
return odd_degree_count == 0 or odd_degree_count == 2We’ll work through both general network representations and apply them specifically to the Königsberg bridge problem.
Consider this network with 5 nodes and 6 edges:
How do we represent this graph in a format that a computer can understand and manipulate? Just as Euler needed to abstract Königsberg’s bridges, we need data structures that capture the network’s essential connectivity while enabling efficient analysis.
The choice of representation can dramatically affect computational efficiency. For sparse networks (few edges), adjacency lists are memory-efficient. For dense networks or matrix operations, adjacency matrices are preferred.
Let’s explore three fundamental approaches that form the backbone of all network algorithms.
The edge table directly lists connections as pairs—the most intuitive way to store network data.
Edge tables are also called “edge lists” and are the most common format for storing large-scale network data in files. Social media platforms like Twitter and Facebook store billions of connections this way.
# Each row represents one edge (connection between two nodes)
edges = [
(0, 1), # Node 0 connects to Node 1
(0, 2), # Node 0 connects to Node 2
(1, 2), # Node 1 connects to Node 2
(1, 3), # Node 1 connects to Node 3
(2, 4), # Node 2 connects to Node 4
(3, 4) # Node 3 connects to Node 4
]
print(f"Network has {len(edges)} edges")
print("Edge list:", edges)Network has 6 edges
Edge list: [(0, 1), (0, 2), (1, 2), (1, 3), (2, 4), (3, 4)]This mirrors how we’d naturally describe the network: “Node 0 connects to nodes 1 and 2, node 1 connects to nodes 0, 2, and 3…” It’s the digital equivalent of Euler’s original approach—simply listing which bridges connect which landmasses.
The adjacency list stores each node’s neighbors in a dictionary—like a social network where each person has a list of friends.
Most graph algorithms prefer adjacency lists because they allow fast iteration over a node’s neighbors. This is crucial for algorithms like breadth-first search or computing clustering coefficients.
# Define adjacency list directly as a dictionary
neighbors = {
0: [1, 2], # Node 0 connects to nodes 1 and 2
1: [0, 2, 3], # Node 1 connects to nodes 0, 2, and 3
2: [0, 1, 4], # Node 2 connects to nodes 0, 1, and 4
3: [1, 4], # Node 3 connects to nodes 1 and 4
4: [2, 3] # Node 4 connects to nodes 2 and 3
}
print("Adjacency list representation:")
for node, neighbor_list in neighbors.items():
print(f"Node {node}: {neighbor_list}")Adjacency list representation:
Node 0: [1, 2]
Node 1: [0, 2, 3]
Node 2: [0, 1, 4]
Node 3: [1, 4]
Node 4: [2, 3]The adjacency matrix uses a grid where entry (i,j) = 1 if nodes are connected—the mathematician’s favorite representation.
Adjacency matrices enable powerful mathematical operations. Matrix multiplication reveals paths of different lengths, and eigenvalue analysis can uncover community structure. Google’s PageRank algorithm fundamentally relies on matrix operations.
# Define adjacency matrix directly
import numpy as np
matrix = np.array([
[0, 1, 1, 0, 0], # Node 0 connects to nodes 1, 2
[1, 0, 1, 1, 0], # Node 1 connects to nodes 0, 2, 3
[1, 1, 0, 0, 1], # Node 2 connects to nodes 0, 1, 4
[0, 1, 0, 0, 1], # Node 3 connects to nodes 1, 4
[0, 0, 1, 1, 0] # Node 4 connects to nodes 2, 3
])
print("Adjacency matrix:")
print(matrix)Adjacency matrix:
[[0 1 1 0 0]
[1 0 1 1 0]
[1 1 0 0 1]
[0 1 0 0 1]
[0 0 1 1 0]]Notice the symmetry: if node i connects to node j, then node j connects to node i (for undirected networks). This symmetry disappears in directed networks, where relationships can be one-way.
The degree of a node is the number of edges connected to it. This simple concept was central to Euler’s proof—he realized that a valid bridge walk requires each landmass to have an even degree (except possibly the starting and ending points).
In Königsberg, all four landmasses had odd degree, making the bridge walk impossible. This insight—that global properties emerge from local structure—remains fundamental to network analysis today.
Here’s how to compute degrees using each representation:
Count how many times each node appears in the edge list.
_degrees = [0] * 5
for node1, node2 in edges:
_degrees[node1] += 1
_degrees[node2] += 1
print("Degrees from edge list:", _degrees)Degrees from edge list: [2, 3, 3, 2, 2]We increment the degree counter for both nodes in each edge because every edge contributes to two nodes’ degrees. This is why the total degree always equals twice the number of edges.
Count the length of each node’s neighbor list—the most direct approach.
_degrees = [len(neighbors[i]) for i in range(5)]
print("Degrees from adjacency list:", _degrees)Degrees from adjacency list: [2, 3, 3, 2, 2]Sum each row (or column) of the matrix—leveraging vectorized operations.
_degrees = matrix.sum(axis=1) # Sum rows
print("Degrees from adjacency matrix:", _degrees)Degrees from adjacency matrix: [2 3 3 2 2]For undirected networks, row sums equal column sums. For directed networks, row sums give out-degree (outgoing connections) while column sums give in-degree (incoming connections).
Now that we understand how to represent networks and compute degrees, let’s implement functions to verify whether a sequence of nodes represents a valid walk, trail, path, or cycle. These verification algorithms are essential for network analysis and implementing graph traversal algorithms.
A walk is the most permissive—we simply need to check that each consecutive pair of nodes is connected by an edge.
def is_walk(sequence, adjacency_matrix):
"""
Check if a sequence of nodes forms a valid walk.
Args:
sequence: List of node indices [v0, v1, v2, ...]
adjacency_matrix: 2D numpy array representing the graph
Returns:
bool: True if sequence is a valid walk, False otherwise
"""
if len(sequence) < 2:
return True # Single node or empty sequence is trivially a walk
# Use NumPy vectorized operations for efficient edge checking
sequence = np.array(sequence)
current_nodes = sequence[:-1] # All nodes except the last
next_nodes = sequence[1:] # All nodes except the first
# Simple but slower: for loop version (slower but more explicit)
# for i, j in zip(current_nodes, next_nodes):
# if adjacency_matrix[i, j] == 0:
# return False
# return True
# Check all edges at once using advanced indexing
edges_exist = adjacency_matrix[current_nodes, next_nodes]
# All edges must exist (all values must be 1)
return np.all(edges_exist == 1)
# Test with our sample network
test_sequence = [0, 1, 2, 4, 3, 1]
print(f"Sequence {test_sequence} is a valid walk: {is_walk(test_sequence, matrix)}")
# Test an invalid walk
invalid_sequence = [0, 3] # No direct edge between 0 and 3
print(f"Sequence {invalid_sequence} is a valid walk: {is_walk(invalid_sequence, matrix)}")Sequence [0, 1, 2, 4, 3, 1] is a valid walk: True
Sequence [0, 3] is a valid walk: FalseFor loops in Python is the notorious source of computational bottlenecks. Avoiding for loops significantly boosts the speed. In is_walk, we use one for loop but you can avoid it by using NumPy’s advanced indexing, i.e., adjacency_matrix[(current_nodes, next_nodes)]. The way to think about this is that (current_nodes, next_nodes) is a tuple of indices, acting as a multi-dimensional index. adjacency_matrix[(current_nodes, next_nodes)] is 1d array of length the same as current_nodes and next_nodes. If the value is 0, then the edge does not exist. We can then check if all the values are not zero.
A trail requires all edges to be distinct, but nodes can repeat.
def is_trail(sequence, adjacency_matrix):
"""
Check if a sequence of nodes forms a valid trail.
Args:
sequence: List of node indices [v0, v1, v2, ...]
adjacency_matrix: 2D numpy array representing the graph
Returns:
bool: True if sequence is a valid trail, False otherwise
"""
if not is_walk(sequence, adjacency_matrix):
return False # Must be a valid walk first
if len(sequence) < 2:
return True
# Convert to numpy for efficient operations
sequence = np.array(sequence)
current_nodes = sequence[:-1]
next_nodes = sequence[1:]
# Use complex numbers to represent edges!
# For undirected graph: smaller_node + 1j * larger_node
# This ensures edge (1,2) and (2,1) both become 1+2j
edge_starts = np.minimum(current_nodes, next_nodes) # Real part
edge_ends = np.maximum(current_nodes, next_nodes) # Imaginary part
complex_edges = edge_starts + 1j * edge_ends
# Check uniqueness directly with NumPy
return len(complex_edges) == len(np.unique(complex_edges))
# Alternative: Original for loop version (slower but more explicit)
# used_edges = set()
# for i in range(len(sequence) - 1):
# current_node = sequence[i]
# next_node = sequence[i + 1]
# # Create edge tuple (smaller index first for undirected graphs)
# edge = (min(current_node, next_node), max(current_node, next_node))
# if edge in used_edges:
# return False # Edge already used
# used_edges.add(edge)
# return True
# Test trail verification
trail_sequence = [0, 1, 3, 4, 2]
print(f"Sequence {trail_sequence} is a valid trail: {is_trail(trail_sequence, matrix)}")
# Test invalid trail (reuses edge 1-2)
invalid_trail = [0, 1, 2, 1, 3]
print(f"Sequence {invalid_trail} is a valid trail: {is_trail(invalid_trail, matrix)}")Sequence [0, 1, 3, 4, 2] is a valid trail: True
Sequence [0, 1, 2, 1, 3] is a valid trail: Falsenp.unique is a powerful function that can handle complex numbers natively.
We use complex numbers to represent edges! Each edge becomes smaller_node + 1j * larger_node. For example, edge (1,2) becomes 1+2j, and edge (2,1) also becomes 1+2j (normalized). Think of complex numbers as natural 2D coordinates for representing node pairs.
A path requires all nodes (except possibly start/end for cycles) to be distinct.
def is_path(sequence, adjacency_matrix):
"""
Check if a sequence of nodes forms a valid path.
Args:
sequence: List of node indices [v0, v1, v2, ...]
adjacency_matrix: 2D numpy array representing the graph
allow_cycle: If True, allows start node = end node (cycle)
Returns:
bool: True if sequence is a valid path, False otherwise
"""
if not is_walk(sequence, adjacency_matrix):
return False # Must be a valid walk first
if len(sequence) < 2:
return True
sequence = np.array(sequence)
return len(sequence) == len(np.unique(sequence))
# Test path verification
path_sequence = [0, 1, 3, 4]
print(f"Sequence {path_sequence} is a valid path: {is_path(path_sequence, matrix)}")
# Test invalid path (repeats node 1)
invalid_path = [0, 1, 2, 1, 3]
print(f"Sequence {invalid_path} is a valid path: {is_path(invalid_path, matrix)}")Sequence [0, 1, 3, 4] is a valid path: True
Sequence [0, 1, 2, 1, 3] is a valid path: FalseConnected components are the maximal sets of nodes where every pair is connected by some path. For Euler path analysis, this is crucial—an Euler path can only exist if the entire graph forms a single connected component (or if we’re only considering the component containing edges).
In Königsberg, all landmasses were connected by bridges, forming one component. If one landmass were isolated, no Euler path could traverse the entire city. This connectivity requirement is the first condition in Euler’s theorem.
A simple way to find connected components is to systematically explore from each unvisited node using depth-first search (DFS). This works because DFS can only reach nodes that are connected through some path.
Algorithm steps: 1. Mark all nodes as unvisited 2. For each unvisited node: - Start a new component - Use DFS to explore all reachable nodes - Add all reached nodes to this component 3. Return the list of components
def connected_components(adjacency_matrix):
"""
Find connected components in an undirected graph using adjacency matrix.
Args:
adjacency_matrix: 2D numpy array (square)
Returns:
List of lists, each sublist contains node indices in a component
"""
import numpy as np
n = adjacency_matrix.shape[0]
visited = np.zeros(n, dtype=bool)
components = []
def dfs(node, component):
"""Depth-first search to explore a component"""
# Mark the current node as visited and add it to current component
visited[node] = True
component.append(node)
# Find all neighbors of the current node using vectorized operation
neighbors = np.where(adjacency_matrix[node] > 0)[0]
# Recursively visit unvisited neighbors
for neighbor in neighbors:
if not visited[neighbor]:
dfs(neighbor, component)
# Main algorithm: iterate through all nodes
for v in range(n):
if not visited[v]: # Found a new component
component = []
dfs(v, component) # Explore entire component
components.append(component)
return components
# Test with our original connected graph
print("Testing with connected graph:")
components = connected_components(matrix)
print("Connected components:", components)
print(f"Number of components: {len(components)}")
# Create a disconnected graph to demonstrate multiple components
disconnected_matrix = np.array([
[0, 1, 0, 0, 0], # Component 1: nodes 0,1,2
[1, 0, 1, 0, 0],
[0, 1, 0, 0, 0],
[0, 0, 0, 0, 1], # Component 2: nodes 3,4
[0, 0, 0, 1, 0]
])
print("\nTesting with disconnected graph:")
disconnected_components = connected_components(disconnected_matrix)
print("Connected components:", disconnected_components)
print(f"Number of components: {len(disconnected_components)}")Testing with connected graph:
Connected components: [[0, np.int64(1), np.int64(2), np.int64(4), np.int64(3)]]
Number of components: 1
Testing with disconnected graph:
Connected components: [[0, np.int64(1), np.int64(2)], [3, np.int64(4)]]
Number of components: 2DFS naturally explores as “deep” as possible before backtracking. This makes it perfect for component finding because once we start exploring from a node, we want to find ALL nodes in its component before moving to the next component.
Now we can enhance our Euler path function to include the connectivity requirement:
def has_euler_path_complete(adjacency_matrix):
"""
Complete Euler path checker with connectivity verification.
Args:
adjacency_matrix: 2D numpy array representing the graph
Returns:
bool: True if graph has an Euler path, False otherwise
"""
# Check if graph is connected (ignoring isolated nodes)
components = connected_components(adjacency_matrix)
# Find nodes with at least one edge (degree > 0)
degrees = adjacency_matrix.sum(axis=1)
non_isolated_nodes = np.where(degrees > 0)[0]
if len(non_isolated_nodes) == 0:
return True # Empty graph has Euler path trivially
# Check if all non-isolated nodes are in the same component
component_with_edges = None
for component in components:
if non_isolated_nodes[0] in component:
component_with_edges = set(component)
break
# All nodes with edges must be in the same component
if not all(node in component_with_edges for node in non_isolated_nodes):
return False # Graph is disconnected
# Count nodes with odd degrees (among non-isolated nodes)
non_isolated_degrees = degrees[non_isolated_nodes]
odd_degree_count = np.sum(non_isolated_degrees % 2)
# Euler's theorem: exactly 0 or 2 nodes with odd degrees
return odd_degree_count == 0 or odd_degree_count == 2
# Test with connected graph
print("Connected graph has Euler path:", has_euler_path_complete(matrix))
# Test with disconnected graph
print("Disconnected graph has Euler path:", has_euler_path_complete(disconnected_matrix))
# Test the classic Königsberg bridge problem (all odd degrees)
konigsberg = np.array([
[0, 1, 1, 1], # Landmass 0 connects to all others (degree 3)
[1, 0, 1, 1], # Landmass 1 connects to all others (degree 3)
[1, 1, 0, 1], # Landmass 2 connects to all others (degree 3)
[1, 1, 1, 0] # Landmass 3 connects to all others (degree 3)
])
print("Königsberg bridges have Euler path:", has_euler_path_complete(konigsberg))Connected graph has Euler path: True
Disconnected graph has Euler path: False
Königsberg bridges have Euler path: FalseEven if a graph has exactly 2 odd-degree nodes, an Euler path cannot exist if those nodes are in different connected components. You cannot traverse from one component to another without existing edges, making a single continuous path impossible.
You now understand how to:
These fundamental algorithms form the building blocks for more sophisticated network analysis. Whether you’re analyzing social networks, transportation systems, or molecular structures, these core concepts of connectivity, traversal, and structural analysis remain essential.
From Euler’s original insight about Königsberg’s bridges to modern network science, the mathematical principles you’ve implemented here continue to solve real-world problems—from GPS routing algorithms to understanding brain connectivity patterns.