MathLabs

Bài toán mở, Tổ hợp và Toán rời rạc, nêu năm 1941

Giả thuyết tái thiết đồ thị

Còn mở

Cho GG và HH là hai đồ thị vô hướng đơn hữu hạn trên n≥3n \ge 3 đỉnh. Nếu hai bộ bài của chúng — tức hai đa tập gồm các đồ thị con cảm sinh không gán nhãn thu được khi xóa một đỉnh {G−v:v∈V(G)}\{G - v : v \in V(G)\} và {H−w:w∈V(H)}\{H - w : w \in V(H)\} — đẳng cấu từng lá bài một, thì GG đẳng cấu với HH.

Hiện trạng nghiên cứu tính đến năm 2026

Tính đến năm 2026, giả thuyết tái thiết đồ thị vẫn còn mở đối với đồ thị đơn hữu hạn tổng quát. Giả thuyết đã được khẳng định cho mọi đồ thị có n≤13n \le 13 đỉnh (McKay, 2022), cho cây, đồ thị không liên thông, đồ thị chính quy, đồ thị một chu trình, đồ thị xương rồng, đồ thị phẳng ngoài, đồ thị phẳng cực đại, cũng như tiệm cận cho hầu hết mọi đồ thị. Các bất biến đồ thị đã biết là khôi phục được từ bộ bài gồm dãy bậc, tính liên thông, số cây khung, đa thức đặc trưng, đa thức sắc số và đa thức Tutte, nhưng đồ thị phẳng tổng quát và đồ thị hai phía vẫn chưa được giải quyết.

Kết quả tốt nhất đã biết

  • Mọi đồ thị có 3≤n≤133 \le n \le 13 đỉnh đều tái thiết được duy nhất — ngay cả khi chỉ biết tập hợp các lớp đẳng cấu trong bộ bài của nó (McKay, 2022).
  • Cây, đồ thị không liên thông, đồ thị chính quy, đồ thị phẳng ngoài và đồ thị phẳng cực đại đều tái thiết được; hơn nữa, bản thân tính phẳng cũng nhận diện được từ bộ bài.
  • Với xác suất tiến tới 11 khi n→∞n \to \infty, đồ thị ngẫu nhiên G(n,1/2)G(n, 1/2) được xác định duy nhất bởi 33 đồ thị con xóa đỉnh bất kỳ của nó (Bollobás, 1990).

Công cụ và chỗ dừng

Công cụĐạt đượcChỗ dừng
Bổ đề đếm Kelly và đại số đồ thị conXác định chính xác số lần xuất hiện của mọi đồ thị con FF có ∣V(F)∣<n|V(F)| < n vì mỗi bản sao của FF xuất hiện trong đúng n−∣V(F)∣n - |V(F)| lá bài của bộ bài, qua đó khôi phục bậc các đỉnh, cây, đồ thị không liên thông và đa thức Tutte.Không thể đếm trực tiếp các đồ thị con bao trùm (∣V(F)∣=n|V(F)| = n) như chu trình Hamilton, cũng không cho biết các mảnh trên những lá bài khác nhau khớp lại ra sao trong các đồ thị 2-liên thông có tính đối xứng cao.
Nguyên lý bao hàm-loại trừ và phương pháp đếm cạnh Lovász–MüllerChứng minh giả thuyết tái thiết cạnh cho mọi đồ thị có m>nlog⁡2nm > n \log_2 n cạnh bằng cách so sánh kích thước nhóm tự đẳng cấu qua bao hàm-loại trừ trên các tập con cạnh.Tổng đan dấu trong bao hàm-loại trừ đòi hỏi 2m>n!2^m > n!, nên thất bại ở miền đồ thị thưa m≤nlog⁡2nm \le n \log_2 n — nơi tập trung các trường hợp khó nhất của tái thiết đỉnh.

Câu hỏi còn mở

  • Mọi đồ thị phẳng hữu hạn hoặc mọi đồ thị hai phía hữu hạn trên n≥3n \ge 3 đỉnh có luôn tái thiết được từ bộ bài xóa đỉnh của nó hay không?
  • Giả thuyết tái thiết cạnh của Harary có đúng cho mọi đồ thị thưa có số cạnh 4≤m≤nlog⁡2n4 \le m \le n \log_2 n hay không?

Tài liệu tham khảo

  1. Paul J. Kelly (1957). A congruence theorem for trees · DOI:10.2140/pjm.1957.7.961
  2. J. A. Bondy, R. L. Hemminger (1977). Graph reconstruction—a survey · DOI:10.1002/jgt.3190010306
  3. Brendan D. McKay (2022). Reconstruction of small graphs and digraphs