1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
{
"cells": [
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"%matplotlib inline"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"\n# Rainbow Coloring\n\nGenerate a complete graph with 13 nodes in a circular layout with the\nedges colored by node distance. The node distance is given by the minimum\nnumber of nodes traversed along an arc between any two nodes on the circle.\n\nSuch graphs are the subject of Ringel's conjecture, which states: any complete\ngraph with ``2n + 1`` nodes can be tiled by any tree with ``n + 1`` nodes\n(i.e. copies of the tree can be placed over the complete graph such that each\nedge in the complete graph is covered exactly once). The edge coloring is\nhelpful in determining how to place the tree copies.\n\n## References\nhttps://www.quantamagazine.org/mathematicians-prove-ringels-graph-theory-conjecture-20200219/\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {
"collapsed": false
},
"outputs": [],
"source": [
"import matplotlib.pyplot as plt\nimport networkx as nx\n\n# A rainbow color mapping using matplotlib's tableau colors\nnode_dist_to_color = {\n 1: \"tab:red\",\n 2: \"tab:orange\",\n 3: \"tab:olive\",\n 4: \"tab:green\",\n 5: \"tab:blue\",\n 6: \"tab:purple\",\n}\n\n# Create a complete graph with an odd number of nodes\nnnodes = 13\nG = nx.complete_graph(nnodes)\n\n# A graph with (2n + 1) nodes requires n colors for the edges\nn = (nnodes - 1) // 2\nndist_iter = list(range(1, n + 1))\n\n# Take advantage of circular symmetry in determining node distances\nndist_iter += ndist_iter[::-1]\n\n\ndef cycle(nlist, n):\n return nlist[-n:] + nlist[:-n]\n\n\n# Rotate nodes around the circle and assign colors for each edge based on\n# node distance\nnodes = list(G.nodes())\nfor i, nd in enumerate(ndist_iter):\n for u, v in zip(nodes, cycle(nodes, i + 1)):\n G[u][v][\"color\"] = node_dist_to_color[nd]\n\npos = nx.circular_layout(G)\n# Create a figure with 1:1 aspect ratio to preserve the circle.\nfig, ax = plt.subplots(figsize=(8, 8))\nnode_opts = {\"node_size\": 500, \"node_color\": \"w\", \"edgecolors\": \"k\", \"linewidths\": 2.0}\nnx.draw_networkx_nodes(G, pos, **node_opts)\nnx.draw_networkx_labels(G, pos, font_size=14)\n# Extract color from edge data\nedge_colors = [edgedata[\"color\"] for _, _, edgedata in G.edges(data=True)]\nnx.draw_networkx_edges(G, pos, width=2.0, edge_color=edge_colors)\n\nax.set_axis_off()\nfig.tight_layout()\nplt.show()"
]
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3.9.16"
}
},
"nbformat": 4,
"nbformat_minor": 0
}
|
