didericis
7183dc1b67
Defines level cycles, edge switches, surface switches, and facial depth on level components of plane triangulations. Proves outerplanarity of level components and a depth-descent lemma. Introduces balanced surface switches and proves they remove a depth-d level cycle while creating 1-2 new depth-(d-1) cycles. Documents the 9-vertex counterexample where no balanced switch exists and sketches preprocessing toward balancedness, leaving general termination open. Co-Authored-By: Claude Opus 4.7 <noreply@anthropic.com>
99 lines
3.4 KiB
Python
99 lines
3.4 KiB
Python
"""9-vertex L_k where the unique depth-1 face has NO balanced surface switch.
|
|
|
|
Outer cycle: 0..8. Triangulated with chords 0-2, 0-3, 3-5, 3-6, 0-6, 6-8.
|
|
Central triangle F = (0,3,6) has depth 1; its three neighbours
|
|
(0,2,3), (3,5,6), (6,8,0) are all depth 0 but each has only ONE
|
|
outer-cycle edge (not two), so none is an "ear" of F.
|
|
|
|
For d = 1, balancedness requires F' to be an ear of uv (both non-uv
|
|
edges on the outer cycle). No neighbour of F qualifies.
|
|
"""
|
|
import os
|
|
import math
|
|
import networkx as nx
|
|
import matplotlib.pyplot as plt
|
|
from matplotlib.patches import Polygon
|
|
|
|
OUT_DIR = os.path.join(os.path.dirname(os.path.abspath(__file__)), os.pardir)
|
|
|
|
n = 9
|
|
POS = {i: (math.cos(math.radians(90 - i * 360 / n)),
|
|
math.sin(math.radians(90 - i * 360 / n))) for i in range(n)}
|
|
OUTER_EDGES = [(i, (i + 1) % n) for i in range(n)]
|
|
CHORDS = [(0, 2), (0, 3), (3, 5), (3, 6), (0, 6), (6, 8)]
|
|
|
|
FACES = [
|
|
(0, 1, 2), # ear
|
|
(0, 2, 3), # 1 outer edge, depth 0
|
|
(3, 4, 5), # ear
|
|
(3, 5, 6), # 1 outer edge, depth 0
|
|
(6, 7, 8), # ear
|
|
(6, 8, 0), # 1 outer edge, depth 0
|
|
(0, 3, 6), # central, depth 1 -- the troublemaker
|
|
]
|
|
|
|
|
|
def face_edges(f):
|
|
return {frozenset((f[0], f[1])), frozenset((f[1], f[2])),
|
|
frozenset((f[0], f[2]))}
|
|
|
|
|
|
outer_set = {frozenset(e) for e in OUTER_EDGES}
|
|
|
|
D = nx.Graph()
|
|
D.add_nodes_from(range(len(FACES)))
|
|
for i, fi in enumerate(FACES):
|
|
for j, fj in enumerate(FACES):
|
|
if i < j and face_edges(fi) & face_edges(fj):
|
|
D.add_edge(i, j)
|
|
|
|
B = [i for i, f in enumerate(FACES)
|
|
if len(face_edges(f) & outer_set) >= 1]
|
|
depth = {i: min(nx.shortest_path_length(D, i, b) for b in B)
|
|
for i in range(len(FACES))}
|
|
|
|
palette = {0: '#86efac', 1: '#fde68a', 2: '#fca5a5'}
|
|
edge_pal = {0: '#16a34a', 1: '#d97706', 2: '#dc2626'}
|
|
|
|
fig, ax = plt.subplots(figsize=(7, 7))
|
|
for i, f in enumerate(FACES):
|
|
d = depth[i]
|
|
poly = Polygon([POS[v] for v in f], closed=True,
|
|
facecolor=palette[d], edgecolor=edge_pal[d],
|
|
linewidth=1.6, alpha=0.7, zorder=0)
|
|
ax.add_patch(poly)
|
|
cx = sum(POS[v][0] for v in f) / 3
|
|
cy = sum(POS[v][1] for v in f) / 3
|
|
ax.text(cx, cy, rf'$\mathrm{{depth}}={d}$',
|
|
ha='center', va='center', fontsize=10,
|
|
color=edge_pal[d], fontweight='bold')
|
|
|
|
# Mark the three "bad" chord edges (would-be-switched edges of F that
|
|
# fail balancedness because the chord side has no outer-cycle edge to
|
|
# pair with).
|
|
F_edges = [(0, 3), (3, 6), (0, 6)]
|
|
for (a, b) in OUTER_EDGES + CHORDS:
|
|
color = '#333'; lw = 1.2
|
|
if (a, b) in F_edges or (b, a) in F_edges:
|
|
color = '#dc2626'; lw = 3.0
|
|
ax.plot([POS[a][0], POS[b][0]], [POS[a][1], POS[b][1]],
|
|
color=color, linewidth=lw, zorder=1)
|
|
|
|
for i, (x, y) in POS.items():
|
|
ax.scatter([x], [y], s=300, c='#1f2937', edgecolors='black',
|
|
linewidths=1.0, zorder=2)
|
|
ax.text(x, y, str(i), ha='center', va='center',
|
|
fontsize=10, color='white', fontweight='bold', zorder=3)
|
|
|
|
ax.set_aspect('equal'); ax.axis('off')
|
|
ax.set_xlim(-1.3, 1.3); ax.set_ylim(-1.3, 1.3)
|
|
ax.set_title('Depth-1 face with no balanced surface switch',
|
|
fontsize=12)
|
|
fig.tight_layout()
|
|
out = os.path.join(OUT_DIR, 'fig_no_balanced_switch.png')
|
|
fig.savefig(out, dpi=180, bbox_inches='tight')
|
|
plt.close(fig)
|
|
print(f'wrote {out}')
|
|
for i, f in enumerate(FACES):
|
|
print(f' {f} -> depth {depth[i]}')
|