如何在Jupyter IDE中用Python 3.6绘制Petersen子图的哈密顿路径

Hey there! Let's walk through how to visualize a Hamiltonian path in the Petersen Graph using your setup. We'll use the networkx library (a go-to for graph tasks in Python) and matplotlib for plotting—both work seamlessly in Jupyter notebooks.

Step 1: Install Required Libraries #

Since you're on Python 3.6, make sure to install a compatible version of networkx (version 2.5.1 is a solid choice, as newer versions drop support for 3.6). Run this in a Jupyter cell:

!pip install networkx==2.5.1 matplotlib

Step 2: Import Libraries & Load the Petersen Graph #

First, import the tools we need, then generate the Petersen Graph directly using networkx's built-in function:

import networkx as nx
import matplotlib.pyplot as plt

# Generate the Petersen Graph
petersen = nx.petersen_graph()

Step 3: Define a Hamiltonian Path #

The Petersen Graph is a classic hypohamiltonian graph—meaning it has no Hamiltonian cycle, but does have Hamiltonian paths (paths that visit every vertex exactly once). Here's a valid Hamiltonian path we can use (vertex numbering follows networkx's default for the Petersen Graph):

# Example Hamiltonian path for Petersen Graph
hamiltonian_path = [0, 1, 2, 3, 4, 9, 6, 8, 5, 7]

You can verify this is a valid path using nx.is_hamiltonian_path(petersen, hamiltonian_path)—it should return True.

Step 4: Visualize the Graph & Highlight the Path #

Now let's plot the Petersen Graph, with our Hamiltonian path highlighted in a distinct color:

# Set up the plot
plt.figure(figsize=(8, 8))

# Draw the full Petersen Graph in light gray
pos = nx.spring_layout(petersen, seed=42)  # Seed for consistent layout
nx.draw(petersen, pos, with_labels=True, node_color='lightblue', edge_color='gray', node_size=700, font_size=12)

# Extract edges from the Hamiltonian path
path_edges = list(zip(hamiltonian_path[:-1], hamiltonian_path[1:]))

# Draw the Hamiltonian path in red, with thicker edges
nx.draw_networkx_edges(petersen, pos, edgelist=path_edges, edge_color='red', width=3)

# Show the plot
plt.title("Petersen Graph with Highlighted Hamiltonian Path")
plt.show()

When you run this cell in Jupyter, you'll see the Petersen Graph with the red path traversing all 10 vertices exactly once.

A Quick Note on Hypohamiltonian Graphs #

As you mentioned, the Petersen Graph is hypohamiltonian. To clarify this property in context:

• It has no Hamiltonian cycle (a path that starts and ends at the same vertex, visiting all others once).
• But if you remove any single vertex from the Petersen Graph, the resulting subgraph will have a Hamiltonian cycle.
• Even without cycles, it still supports Hamiltonian paths (like the one we plotted) that cover every vertex.

内容的提问来源于stack exchange，提问作者JuMoGar