GATE D12
Đồ thị tỉ số: thưa đóng, dày hạng thấp
Điều gì thay đổi
Phần non-tight còn lại nay là một đồ thị hữu hạn nhãn hữu tỉ chính xác, không phải đám mây vector. Danh tính dual-deficit chính xác biểu diễn margin theo từng cạnh ngoại lệ. Đồ thị thưa (≤2 cạnh ngoại lệ) giữ margin đục-lỗ dương nên vector proper (22/22, 0 phản ví dụ). Đồ thị dày mang một relation basis độc lập qua spanning forest, hạng chứng minh bằng đại số tuyến tính chính xác, không phải đếm cạnh, handoff cấu trúc hạng thấp. Mọi vector thất bại có ≥3 cạnh ngoại lệ và xuất relation basis kiểm được, không dư thừa vô lý.
Bằng chứng
kiểm 1Danh tính dual-deficit chính xác: margin = generic + độ lệch từng cạnh (cặp + / bộ ba −, dấu chính xác)
kiểm 2Thưa (≤2 cạnh ngoại lệ) ⟹ margin > 0 ⟹ proper (22/22, 0 phản ví dụ)
kiểm 3Dày ⟹ relation basis độc lập spanning-forest (Q-rank, không đếm cạnh), 2 verifier, 32/32 tấn công
Kiểm chứng: double · I2 · 9 artifact (report, verifier, bộ tấn công, manifest SHA-256)