File size: 1,224 Bytes
0f775d0 | 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 | """CPU-only verification test for Ramsey R(5,5) Simulated Annealing Search"""
print("Testing ramsey-r55-cuda...")
from itertools import combinations
def count_monochromatic_k5(n, adj_set):
"""Count monochromatic K_5 in 2-coloring. adj_set = set of edges colored red."""
count = 0
for combo in combinations(range(n), 5):
edges = list(combinations(combo, 2))
red = sum(1 for e in edges if e in adj_set)
if red == 10 or red == 0: # all red or all blue
count += 1
return count
# K_4: no K_5 subgraph possible, so count=0 for any coloring
print(f" K_4 all-red: {count_monochromatic_k5(4, set(combinations(range(4),2)))} K_5 (expect 0)")
assert count_monochromatic_k5(4, set(combinations(range(4),2))) == 0
# K_5 all-red: exactly 1 monochromatic K_5
all_edges = set(combinations(range(5), 2))
print(f" K_5 all-red: {count_monochromatic_k5(5, all_edges)} K_5 (expect 1)")
assert count_monochromatic_k5(5, all_edges) == 1
# K_6 all-red: C(6,5)=6 monochromatic K_5
all_edges_6 = set(combinations(range(6), 2))
print(f" K_6 all-red: {count_monochromatic_k5(6, all_edges_6)} K_5 (expect 6)")
assert count_monochromatic_k5(6, all_edges_6) == 6
print(f"\n3/3 tests passed")
|