didericis
41227c6a0f
- Main paper: dual_decomposition_minimal_counterexamples/ -> face_monochromatic_pairs/. Title is now "Face-Monochromatic Pairs and the Four Colour Theorem". - Companion paper: dual_decomposition_iterated_reduction/ -> iterated_reduction_in_reduced_dual/. Title is now "An Iterated Reduction in the Reduced Dual". Its prose and bibliography cite the parent under the new title. - Update one absolute sys.path reference inside check_conj_face_kempe_n15.py that pointed at the old folder. Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
175 lines
7.1 KiB
Python
175 lines
7.1 KiB
Python
"""Draw the four steps of the reduced-dual construction (Definition 2.1).
|
|
|
|
Uses the dodecahedron G' = dual of the icosahedron, with F_v the inner pentagon,
|
|
as built in reduced_dual.py. Produces fig_reduced_dual_step{1..4}.png.
|
|
"""
|
|
import os
|
|
import math
|
|
import matplotlib.pyplot as plt
|
|
from matplotlib.patches import Polygon
|
|
from matplotlib.lines import Line2D
|
|
|
|
from reduced_dual import build_dual, apply_reduction
|
|
|
|
OUT_DIR = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
|
|
|
|
GRAY = '#9ca3af'
|
|
DARK = '#374151'
|
|
GHOST = '#fca5a5'
|
|
DEG2 = '#f59e0b'
|
|
APEX = '#16a34a'
|
|
CHORD = '#2563eb'
|
|
FACE = '#fef9c3'
|
|
|
|
|
|
def draw_edges(ax, G, pos, nodes=None, **kw):
|
|
for u, v in G.edges():
|
|
if nodes is not None and (u not in nodes or v not in nodes):
|
|
continue
|
|
(x0, y0), (x1, y1) = pos[u], pos[v]
|
|
ax.plot([x0, x1], [y0, y1], **kw)
|
|
|
|
|
|
def draw_nodes(ax, pos, nodes, **kw):
|
|
xs = [pos[v][0] for v in nodes]
|
|
ys = [pos[v][1] for v in nodes]
|
|
ax.scatter(xs, ys, **kw)
|
|
|
|
|
|
def face_F_polygon(pos):
|
|
"""The new central face F: decagon alternating b_i, c_i clockwise."""
|
|
order = []
|
|
for i in range(5):
|
|
order += [('b', i), ('c', i)]
|
|
return [pos[v] for v in order]
|
|
|
|
|
|
def base_canvas(title):
|
|
fig, ax = plt.subplots(figsize=(8.5, 8.5))
|
|
ax.set_aspect('equal')
|
|
ax.axis('off')
|
|
ax.set_title(title, fontsize=12)
|
|
return fig, ax
|
|
|
|
|
|
def main():
|
|
Gp, pos, Fv = build_dual()
|
|
res = apply_reduction(Gp, pos, Fv, i=0)
|
|
Ghat, npos, A = res['Ghat'], res['pos'], res['A']
|
|
v_n, apex_nbrs, chord = res['v_n'], res['apex_nbrs'], res['chord']
|
|
|
|
survivors = [v for v in Gp if v not in Fv] # b, c, d families
|
|
surv_set = set(survivors)
|
|
deg2 = list(A) # the five b_i
|
|
|
|
# surviving edges (both endpoints survive) vs deleted edges (touch an a_i)
|
|
surv_edges = [(u, v) for u, v in Gp.edges()
|
|
if u in surv_set and v in surv_set]
|
|
del_edges = [(u, v) for u, v in Gp.edges()
|
|
if u not in surv_set or v not in surv_set]
|
|
|
|
def draw_surviving(ax):
|
|
ax.add_patch(Polygon(face_F_polygon(pos), closed=True,
|
|
facecolor=FACE, edgecolor='none', zorder=0))
|
|
for u, v in surv_edges:
|
|
(x0, y0), (x1, y1) = pos[u], pos[v]
|
|
ax.plot([x0, x1], [y0, y1], color=GRAY, lw=1.6, zorder=1)
|
|
others = [v for v in survivors if v not in deg2]
|
|
draw_nodes(ax, pos, others, s=120, color=DARK, zorder=3)
|
|
|
|
def draw_ghosts(ax):
|
|
for u, v in del_edges:
|
|
(x0, y0), (x1, y1) = pos[u], pos[v]
|
|
ax.plot([x0, x1], [y0, y1], color=GHOST, lw=1.2, ls='--', zorder=1)
|
|
draw_nodes(ax, pos, Fv, s=120, color='white', edgecolors=GHOST,
|
|
linewidths=1.5, zorder=2)
|
|
for v in Fv:
|
|
ax.plot(*pos[v], marker='x', color=GHOST, ms=8, zorder=3)
|
|
|
|
# ----- Step 1: delete F_v's boundary; five degree-2 vertices on face F -----
|
|
fig, ax = base_canvas(
|
|
"Step 1: delete the five dual vertices on $\\partial F_v$.\n"
|
|
"Their outer neighbours drop to degree 2 (orange) and lie on a new "
|
|
"face $F$ (shaded).")
|
|
draw_surviving(ax)
|
|
draw_ghosts(ax)
|
|
draw_nodes(ax, pos, deg2, s=260, color=DEG2, edgecolors='black',
|
|
linewidths=1.0, zorder=4)
|
|
cx = sum(pos[('a', i)][0] for i in range(5)) / 5
|
|
cy = sum(pos[('a', i)][1] for i in range(5)) / 5
|
|
ax.text(cx, cy, '$F$', fontsize=16, ha='center', va='center',
|
|
color='#a16207', zorder=5)
|
|
ax.legend(handles=[
|
|
Line2D([0], [0], marker='x', color=GHOST, lw=0, label='deleted (was $\\partial F_v$)'),
|
|
Line2D([0], [0], marker='o', color='w', markerfacecolor=DEG2,
|
|
markeredgecolor='black', label='degree-2 vertex'),
|
|
], loc='upper left', fontsize=10)
|
|
fig.savefig(os.path.join(OUT_DIR, 'fig_reduced_dual_step1.png'),
|
|
dpi=170, bbox_inches='tight'); plt.close(fig)
|
|
|
|
# ----- Step 2: order the five degree-2 vertices clockwise as A_0..A_4 -----
|
|
fig, ax = base_canvas(
|
|
"Step 2: list the degree-2 vertices clockwise around $F$ as "
|
|
"$A_0,\\dots,A_4$.")
|
|
draw_surviving(ax)
|
|
draw_nodes(ax, pos, deg2, s=300, color=DEG2, edgecolors='black',
|
|
linewidths=1.0, zorder=4)
|
|
for k, v in enumerate(A):
|
|
x, y = pos[v]
|
|
ax.annotate(f'$A_{k}$', (x, y), textcoords='offset points',
|
|
xytext=(0, 0), ha='center', va='center', fontsize=10,
|
|
fontweight='bold', color='black', zorder=5)
|
|
# outward label too
|
|
ax.annotate(f'$A_{k}$', (x * 1.18, y * 1.18), ha='center', va='center',
|
|
fontsize=12, color='#a16207', zorder=5)
|
|
fig.savefig(os.path.join(OUT_DIR, 'fig_reduced_dual_step2.png'),
|
|
dpi=170, bbox_inches='tight'); plt.close(fig)
|
|
|
|
# ----- Step 3: add v_n joined to A_i, A_{i+1}, A_{i+2} -----
|
|
fig, ax = base_canvas(
|
|
"Step 3: add a vertex $v_n$ joined to $A_i, A_{i+1}, A_{i+2}$ "
|
|
"(here $i=0$).")
|
|
draw_surviving(ax)
|
|
draw_nodes(ax, pos, deg2, s=300, color=DEG2, edgecolors='black',
|
|
linewidths=1.0, zorder=4)
|
|
for k, v in enumerate(A):
|
|
ax.annotate(f'$A_{k}$', (pos[v][0] * 1.18, pos[v][1] * 1.18),
|
|
ha='center', va='center', fontsize=12, color='#a16207', zorder=5)
|
|
for u in apex_nbrs:
|
|
(x0, y0), (x1, y1) = npos[v_n], pos[u]
|
|
ax.plot([x0, x1], [y0, y1], color=APEX, lw=2.4, zorder=5)
|
|
draw_nodes(ax, npos, [v_n], s=320, color=APEX, marker='s',
|
|
edgecolors='black', linewidths=1.0, zorder=6)
|
|
ax.annotate('$v_n$', npos[v_n], textcoords='offset points', xytext=(0, 14),
|
|
ha='center', fontsize=12, fontweight='bold', color=APEX, zorder=7)
|
|
fig.savefig(os.path.join(OUT_DIR, 'fig_reduced_dual_step3.png'),
|
|
dpi=170, bbox_inches='tight'); plt.close(fig)
|
|
|
|
# ----- Step 4: add chord A_{i+3} A_{i+4}; the reduced dual -----
|
|
fig, ax = base_canvas(
|
|
"Step 4: add the edge $A_{i+3} A_{i+4}$. The result $\\widehat{G}'_{v,i}$ "
|
|
"is again cubic and planar.")
|
|
draw_surviving(ax)
|
|
draw_nodes(ax, pos, deg2, s=300, color=DEG2, edgecolors='black',
|
|
linewidths=1.0, zorder=4)
|
|
for k, v in enumerate(A):
|
|
ax.annotate(f'$A_{k}$', (pos[v][0] * 1.18, pos[v][1] * 1.18),
|
|
ha='center', va='center', fontsize=12, color='#a16207', zorder=5)
|
|
for u in apex_nbrs:
|
|
(x0, y0), (x1, y1) = npos[v_n], pos[u]
|
|
ax.plot([x0, x1], [y0, y1], color=APEX, lw=2.4, zorder=5)
|
|
draw_nodes(ax, npos, [v_n], s=320, color=APEX, marker='s',
|
|
edgecolors='black', linewidths=1.0, zorder=6)
|
|
ax.annotate('$v_n$', npos[v_n], textcoords='offset points', xytext=(0, 14),
|
|
ha='center', fontsize=12, fontweight='bold', color=APEX, zorder=7)
|
|
(x0, y0), (x1, y1) = pos[chord[0]], pos[chord[1]]
|
|
ax.plot([x0, x1], [y0, y1], color=CHORD, lw=2.8, zorder=5)
|
|
fig.savefig(os.path.join(OUT_DIR, 'fig_reduced_dual_step4.png'),
|
|
dpi=170, bbox_inches='tight'); plt.close(fig)
|
|
|
|
print("wrote fig_reduced_dual_step1..4.png to", OUT_DIR)
|
|
|
|
|
|
if __name__ == '__main__':
|
|
main()
|