Luận văn thạc sĩ: Xây dựng và phân loại một số lớp đồ thị có cấu trúc đặc biệt

Luận văn thạc sĩ trình bày phương pháp xây dựng và phân loại một số lớp đồ thị có cấu trúc đặc biệt, tập trung vào tính chất n-e.c độc đáo.

• Tác giả: Le Thi Thu Huong
• Người hướng dẫn: Le Anh Vinh
• Trường học: Trường Đại học Khoa học Tự nhiên, Đại học Quốc gia Hà Nội
• Chuyên ngành: Lý thuyết xác suất và thống kê toán học
• Đề tài: Xây dựng và phân loại một số lớp đồ thị có cấu trúc đặc biệt
• Loại tài liệu: Luận văn thạc sĩ khoa học
• Năm xuất bản: 2014
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CẢM ƠN
• MỞ ĐẦU
• 1. Chương 1: Đồ thị n-e
• 1.1. Khái niệm về đồ thị n-e.c
• 1.2. Một số tính chất cơ bản của đồ thị n-e.c
• 1.3. Các đồ thị Paley và biến thể
• 2. Chương 2: Xây dựng và phân loại một số đồ thị n-e.c
• 3. Chương 3: Xây dựng đồ thị ngẫu nhiên chính quy mạnh
• Tài liệu tham khảo

Tóm tắt

I. Khái niệm cơ bản về đồ thị có cấu trúc đặc biệt

Đồ thị có cấu trúc đặc biệt là một lĩnh vực quan trọng trong lý thuyết đồ thị hiện đại. Một đồ thị G = (V, E) được xác định bởi tập đỉnh V và tập cạnh E, trong đó các đỉnh được kết nối với nhau theo những quy tắc nhất định. Khác với đồ thị tổng quát, đồ thị có cấu trúc đặc biệt tuân theo các tính chất hình học và đại số riêng biệt. Nghiên cứu về những loại đồ thị này bắt đầu từ công trình của Erdős và Rényi, khi họ phát hiện ra tính chất n-e.c (n-extensible connectivity). Tính chất này mô tả khả năng mở rộng của một đồ thị, nơi mỗi tập con các đỉnh có thể được kết nối theo những cách cụ thể. Các ứng dụng thực tiễn của loại đồ thị này rất đa dạng, từ khoa học máy tính đến sinh học và xã hội học.

1.1. Định nghĩa đồ thị n e.c

Một đồ thị n-e.c là đồ thị trong đó với mỗi cặp tập con rời nhau U, W của tập đỉnh V sao cho |U| + |W| = n, tồn tại một đỉnh v ∈ V − (U ∪ W) kết nối với tất cả đỉnh của U nhưng không kết nối với bất kỳ đỉnh nào của W. Đây là một khái niệm mạnh mẽ trong lý thuyết đồ thị, cho phép mô tả các cấu trúc phức tạp một cách chính xác.

1.2. Tính chất của đồ thị có cấu trúc đặc biệt

Tính chất n-e.c đảm bảo rằng đồ thị không có đỉnh cô lập hay đỉnh phổ quát. Các tính chất cơ bản bao gồm: tính liên thông, tính độc lập của cạnh, và tính đối xứng. Những tính chất này làm cho đồ thị đặc biệt trở nên hữu ích trong việc mô hình hóa các hệ thống phức tạp.

II. Xây dựng đồ thị n e

Xây dựng các lớp đồ thị n-e.c là một trong những nhiệm vụ chính trong lý thuyết đồ thị hiện đại. Quá trình xây dựng bắt đầu từ việc xác định các điều kiện cần thiết để một đồ thị thỏa mãn tính chất n-e.c. Phương pháp chính là sử dụng không gian xác suất G(m, 1/2) để chứng minh rằng hầu hết các đồ thị hữu hạn đều là n-e.c. Theo định lý cơ bản của Erdős và Rényi, với xác suất bằng 1 khi m → ∞, các đồ thị được tạo từ không gian này sẽ thỏa mãn tính chất n-e.c. Phương pháp này cung cấp một cơ sở lý thuyết vững chắc cho việc xây dựng các đồ thị có cấu trúc đặc biệt, mở ra nhiều hướng nghiên cứu mới.

2.1. Điều kiện xây dựng đồ thị 2 e.c

Đối với đồ thị 2-e.c, với mỗi cặp đỉnh riêng biệt u và w, phải tồn tại 4 đỉnh khác có khả năng kết nối với chúng theo tất cả các cách có thể. Điều này yêu cầu một cơ cấu kết nối chặt chẽ giữa các đỉnh, đảm bảo tính liên thông và độc lập cao.

2.2. Ứng dụng của không gian xác suất trong xây dựng

Không gian xác suất G(m, 1/2) là công cụ mạnh mẽ để chứng minh sự tồn tại của đồ thị n-e.c. Phương pháp này dựa trên lý thuyết xác suất và cho phép tạo ra các đồ thị ngẫu nhiên thỏa mãn các tính chất mong muốn với xác suất cao.

III. Phân loại các lớp đồ thị có cấu trúc đặc biệt

Phân loại đồ thị n-e.c là quá trình quan trọng để hiểu rõ hơn về các tính chất của chúng. Các lớp đồ thị khác nhau có những đặc điểm riêng biệt dựa trên giá trị n và cấu trúc liên thông. Phân loại có thể thực hiện dựa trên số đỉnh, số cạnh, hoặc các tính chất đặc thù khác. Đồ thị Paley là một ví dụ nổi bật của loại đồ thị này, được xây dựng từ các tính chất số học. Các biến thể của đồ thị Paley mang lại nhiều khám phá thú vị về cấu trúc và tính chất. Việc phân loại giúp các nhà nghiên cứu xác định các mẫu và quy tắc chung, từ đó phát triển các công cụ mới để nghiên cứu đồ thị có cấu trúc đặc biệt một cách hiệu quả hơn.

3.1. Đồ thị Paley và các tính chất

Đồ thị Paley được xây dựng từ các phần tử của trường hữu hạn, trong đó hai đỉnh được kết nối nếu hiệu của chúng là một thặng dư bậc hai. Những tính chất đặc biệt của đồ thị Paley bao gồm tính chính quy mạnh và tính đối xứng cao, làm cho nó trở thành một lớp đồ thị quan trọng trong nghiên cứu.

3.2. Biến thể và mở rộng

Các biến thể của đồ thị cấu trúc đặc biệt được tạo ra bằng cách sửa đổi các điều kiện kết nối. Những phiên bản mở rộng này giữ lại những tính chất chính nhưng có thêm các đặc điểm riêng, phục vụ cho các ứng dụng cụ thể.

IV. Xây dựng đồ thị ngẫu nhiên chính quy mạnh với tính chất 3 e

Đồ thị ngẫu nhiên chính quy mạnh là một loại đặc biệt được xây dựng để thỏa mãn tính chất 3-e.c. Có hai phương pháp chính để xây dựng loại đồ thị này, cả hai đều dựa trên nguyên lý ngẫu nhiên hóa có kiểm soát. Phương pháp thứ nhất sử dụng các quy trình lặp để đảm bảo rằng các đỉnh được thêm vào một cách tuần tự, mỗi đỉnh mới kết nối với các đỉnh cũ theo những cách được định sẵn. Phương pháp thứ hai dựa vào lý thuyết xác suất để tạo ra đồ thị chính quy với độ đều đặn cao. Chứng minh các tính chất của những đồ thị này yêu cầu các công cụ toán học tinh vi, đặc biệt là các kỹ thuật từ lý thuyết xác suất và tổ hợp. Kết quả là những đồ thị sinh ra thỏa mãn tính chất 3-e.c, mở ra những ứng dụng mới trong các lĩnh vực khác nhau.

4.1. Phương pháp xây dựng thứ nhất

Phương pháp lặp bắt đầu từ một tập đỉnh ban đầu và liên tục thêm các cạnh mới theo những quy tắc chặt chẽ. Mỗi bước xây dựng đảm bảo rằng các tính chất n-e.c được duy trì và tăng cường. Phương pháp này cho phép kiểm soát chính xác cấu trúc của đồ thị.

4.2. Phương pháp xây dựng thứ hai và chứng minh tính chất 3 e.c

Phương pháp xác suất sử dụng các biến ngẫu nhiên độc lập để tạo ra đồ thị chính quy mạnh với các tính chất mong muốn. Chứng minh rằng đồ thị sinh ra thỏa mãn tính chất 3-e.c dựa trên các bất đẳng thức xác suất và kỹ thuật union bound.

Nội dung chính

Tổng quan nghiên cứu

Lý thuyết đồ thị là một chuyên ngành toán học then chốt đóng vai trò nền tảng trong cả nghiên cứu thuần túy lẫn khoa học máy tính ứng dụng. Kể từ công trình tiên phong của hai nhà toán học Paul Erdős và Alfréd Rényi vào năm 1963, bài toán tìm kiếm và phân loại các đồ thị hữu hạn sở hữu tính chất kề tồn tại (n-existentially closed hay $n$-e.c) đã trở thành tâm điểm thu hút sự quan tâm của nhiều nhà khoa học. Một đồ thị đạt tính chất $n$-e.c khi với mọi cặp tập đỉnh rời nhau có tổng số đỉnh bằng $n$, luôn tồn tại ít nhất một đỉnh nằm ngoài nối với toàn bộ tập thứ nhất và không nối với bất kỳ đỉnh nào thuộc tập thứ hai. Dù về mặt xác suất, hầu hết các đồ thị ngẫu nhiên khi số đỉnh tiến tới vô cùng đều thỏa mãn tính chất $n$-e.c với xác suất xấp xỉ 100%, việc chỉ ra và kiến tạo các họ đồ thị cụ thể mang cấu trúc này lại là thách thức lớn kéo dài suốt hơn 50 năm.

Luận văn thạc sĩ khoa học của tác giả Lê Thị Thu Hường, thực hiện năm 2014 tại Trường Đại học Khoa học Tự nhiên – Đại học Quốc gia Hà Nội dưới sự hướng dẫn của PGS. Lê Anh Vinh, tập trung giải quyết bài toán xây dựng và phân loại các lớp đồ thị có cấu trúc đặc biệt này. Nghiên cứu thuộc chuyên ngành Lý thuyết xác suất và thống kê toán học (Mã số đào tạo: 60460106). Mục tiêu trọng tâm của đề tài là làm rõ các đặc trưng cấu trúc của đồ thị $n$-e.c, xác định chặn kích thước tối thiểu $m_{ec}(n)$, khảo sát mối liên hệ với đồ thị chính quy mạnh, và đề xuất các phương pháp giải tích hình học hữu hạn để tạo ra các lớp đồ thị mới. Luận văn đã phân loại thành công đồ thị giao khối từ các hệ tổ hợp và đề xuất 2 thuật toán kiến tạo đồ thị ngẫu nhiên chính quy mạnh phi đẳng cấu với quy mô tăng trưởng theo hàm mũ.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng trên sự giao thoa của 3 trụ cột lý thuyết: Lý thuyết đồ thị ngẫu nhiên, Đại số trừu tượng trên trường hữu hạn $\mathbb{F}_q$, và Hình học tổ hợp Affine. Các khái niệm và mô hình nền tảng bao gồm:

• Tính chất kề $n$-e.c: Đồ thị $G = (V, E)$ được gọi là $n$-e.c nếu với mọi cặp tập con rời nhau $U, W \subset V$ thỏa mãn $|U| + |W| = n$, tồn tại đỉnh $v \in V \setminus (U \cup W)$ sao cho $v$ kề với mọi đỉnh trong $U$ và không kề với bất kỳ đỉnh nào trong $W$. Khi $n \to \infty$, đồ thị vô hạn duy nhất thỏa mãn tính chất này với mọi $n$ được gọi là đồ thị Rado (ký hiệu là $R$).
• Đồ thị chính quy mạnh (Strongly Regular Graph - $\text{SRG}$): Đồ thị $k$-chính quy với $v$ đỉnh, ký hiệu $\text{SRG}(v, k, \lambda, \mu)$, trong đó mọi cặp đỉnh kề nhau có đúng $\lambda$ láng giềng chung, và mọi cặp đỉnh không kề nhau có đúng $\mu$ láng giềng chung.
• Đồ thị Paley ($P_q$) và biến thể: Được xác định trên trường hữu hạn $\mathbb{F}_q$ với $q \equiv 1 \pmod 4$. Hai đỉnh $x, y$ nối với nhau khi và chỉ khi hiệu $x - y$ là số chính phương trong $\mathbb{F}_q$.
• Thiết kế khối cân bằng khuyết $\text{BIBD}(v, k, \lambda)$ và Hệ bộ ba Steiner $\text{STS}(v)$: Cấu trúc tổ hợp gồm $v$ phần tử chia thành các khối $k$ phần tử sao cho mỗi cặp điểm xuất hiện trong đúng $\lambda$ khối (với $\text{STS}(v)$ tương ứng $k=3, \lambda=1$).

Phương pháp nghiên cứu

Nghiên cứu sử dụng nguồn dữ liệu thứ cấp gồm 42 công trình khoa học quốc tế uy tín, kết hợp với các cấu trúc đại số và mô hình xác suất $G(m, 1/2)$. Cỡ mẫu phân tích bao gồm toàn bộ các lớp đồ thị ngẫu nhiên từ cấp độ nhỏ nhất với số đỉnh bằng 4 ($m_{ec}(1) = 4$) cho tới các không gian xác suất vô hạn trên trường $\mathbb{F}_q$. Phương pháp chọn mẫu là chọn mẫu có chủ đích dựa trên các cấu trúc đối xứng cao: trường nguyên tố $\mathbb{Z}_p$, các ma trận Hadamard dạng Bush cấp $4n^2$, và các mặt phẳng Affine hữu hạn có $q^2$ điểm với $q \ge 8$.

Phương pháp phân tích chủ đạo là Phương pháp xác suất (Probabilistic Method) kết hợp giải tích đa thức và ước lượng tổng đặc trưng phi tầm thường Schmidt. Lý do lựa chọn phương pháp này xuất phát từ bản chất tổ hợp phức tạp của tính chất kề: việc kiểm tra vét cạn toàn bộ $2^n \binom{m}{n}$ khả năng tập con là bất khả thi khi số đỉnh tăng, trong khi phương pháp xác suất cho phép chứng minh sự tồn tại của đỉnh thỏa mãn với độ tin cậy tiệm cận 1 khi quy mô tham số trường $q \to \infty$. Toàn bộ quy trình chứng minh và tổng hợp cấu trúc được hoàn thiện trong timeline nghiên cứu kéo dài đến tháng 10 năm 2014.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Luận văn đã đạt được 4 phát hiện toán học mang tính đóng góp cao cho lý thuyết đồ thị cấu trúc:

• Xác lập chặn kích thước tối thiểu của đồ thị $n$-e.c: Luận văn chứng minh một đồ thị $n$-e.c bất kỳ luôn có cấp tối thiểu đạt $|V| \ge n + 2^n$ và sở hữu ít nhất $n \cdot 2^{n-1}$ cạnh. Đối với các bậc nhỏ, nghiên cứu chỉ ra chính xác $m_{ec}(1) = 4$ với đúng 3 đồ thị không đẳng cấu là $2K_2, C_4, P_4$; $m_{ec}(2) = 9$ với đại diện duy nhất là đồ thị tích Descartes $K_3 \square K_3$; và thu hẹp chặn tìm kiếm cho đồ thị 3-e.c trong khoảng $24 \le m_{ec}(3) \le 28$.
• Phân loại hoàn chỉnh đồ thị giao khối từ Hệ bộ ba Steiner: Chứng minh đồ thị giao khối của hệ $\text{STS}(v)$ đạt tính chất 2-e.c khi và chỉ khi $v \ge 13$. Nghiên cứu đã loại trừ thành công các trường hợp $v = 7$ và $v = 9$, đồng thời phân tích chi tiết 26 khối của $\text{STS}(13)$ để khẳng định tính thỏa mãn. Kết quả này được tổng quát hóa cho cấu trúc $\text{BIBD}(v, k, 1)$ với điều kiện $v \ge k^2 + k - 1$.
• Kiến tạo lớp đồ thị 3-e.c trong không gian Euclid hữu hạn: Thiết lập thành công mô hình đồ thị $G_{p,d}$ trên không gian $\mathbb{Z}_p^d$ với $p \ge 7$ là số nguyên tố lẻ và số chiều $d \ge 5$, chứng minh sự tồn tại của nghiệm hệ phương trình bậc hai với số lượng nghiệm không dưới $p$ điểm phân biệt.
• Đề xuất 2 phương pháp xây dựng đồ thị ngẫu nhiên chính quy mạnh: Luận văn kết hợp cấu trúc giải đấu Paley $\dot{P}_q$ với mặt phẳng Affine $A$ cấp $q$, tạo ra họ đồ thị $\text{SRG}((q+1)^2, q(q+1)/2, (q^2-1)/4, (q^2-1)/4)$ thỏa mãn tính chất kề $n$-e.c. Thuật toán chứng minh số lượng đồ thị không đẳng cấu sinh ra đạt tối thiểu $2^{\binom{q+1}{2}(1-s(q))}$, tăng theo hàm mũ so với các họ đồ thị Paley đơn lẻ.

Thảo luận kết quả

Các kết quả nghiên cứu có thể được trực quan hóa thông qua bảng phân loại tham số cấu trúc giữa các lớp đồ thị và biểu đồ so sánh tốc độ tăng trưởng tiệm cận của chặn dưới $m_{ec}(n) = \Omega(n 2^n)$. So sánh với các nghiên cứu trước đây của Erdős, Rényi và các công trình của Cameron, kết quả của luận văn đã giải quyết được hạn chế lớn: trước đây cộng đồng toán học hầu như chỉ biết đến đồ thị Paley như ví dụ duy nhất về đồ thị $n$-e.c.

+-------------------+-----------------+-----------------------+------------------------+
| Lớp đồ thị        | Số đỉnh (|V|)   | Bậc tính chất kề      | Đặc trưng cấu trúc     |
+-------------------+-----------------+-----------------------+------------------------+
| 2K_2, C_4, P_4    | 4               | 1-e.c                 | Cấp nhỏ nhất m_ec(1)=4 |
| K_3 □ K_3         | 9               | 2-e.c                 | Cấp nhỏ nhất m_ec(2)=9 |
| Giao khối STS(13) | 26 khối         | 2-e.c                 | Thiết kế khối BIBD     |
| G_{p,d}           | p^d (p≥7, d≥5)  | 3-e.c                 | Không gian Euclid Z_p^d|
| SRG Xây dựng 2    | (q+1)^2         | n-e.c                 | Chính quy mạnh đa hình |
+-------------------+-----------------+-----------------------+------------------------+

Đặc biệt, luận văn làm rõ sự khác biệt bản chất giữa đồ thị giả ngẫu nhiên (quasi-random graph) và đồ thị $n$-e.c. Mặc dù đồ thị Paley thỏa mãn cả hai tính chất, một đồ thị chuẩn ngẫu nhiên chưa chắc đã là $n$-e.c (chẳng hạn tồn tại các đồ thị giả ngẫu nhiên nhưng không đạt 4-e.c). Việc phát triển 2 phương pháp xây dựng đồ thị từ ma trận liên thuộc $D_q$ và hoán vị $\pi_i$ đã chứng minh tính hữu hiệu của việc kết hợp các công cụ đại số trừu tượng để điều khiển tính ngẫu nhiên tổ hợp.

Đề xuất và khuyến nghị

Dựa trên các kết quả đạt được, luận văn đề xuất 4 định hướng nghiên cứu và ứng dụng thực tiễn:

1. Thu hẹp khoảng cách xác định giá trị chính xác của $m_{ec}(3)$: Áp dụng các thuật toán giải bài toán thỏa mãn mệnh đề (SAT Solvers) kết hợp hệ thống tính toán hiệu năng cao để rà soát toàn bộ các đồ thị chính quy từ 24 đến 28 đỉnh. Mục tiêu là triệt tiêu 100% khoảng bất định của $m_{ec}(3)$ trong timeline 12 tháng, do các nhóm nghiên cứu chuyên sâu về Toán rời rạc chủ trì.
2. Mở rộng xây dựng đồ thị cho bậc $n \ge 4$: Phát triển các mô hình không gian vector nhiều chiều trên trường Galois $\mathbb{F}_{2^k}$ và tối ưu hóa ma trận Hadamard dạng Bush cấp $16n^2$. Mục tiêu nâng tỷ lệ bao phủ cấu trúc của các lớp đồ thị 4-e.c và 5-e.c lên thêm 25% trong lộ trình 24 tháng tới, thực hiện bởi các nghiên cứu sinh ngành Xác suất - Thống kê.
3. Chuyển giao ứng dụng vào cấu trúc mạng truyền thông và mật mã: Ứng dụng các đồ thị chính quy mạnh $\text{SRG}((q+1)^2, q(q+1)/2, (q^2-1)/4, (q^2-1)/4)$ vào việc thiết kế mã kiểm tra chẵn lẻ mật độ thấp (LDPC codes) và định tuyến mạng ngang hàng chịu lỗi cao. Mục tiêu giúp giảm 15% xác suất nghẽn mạng trong vòng 18 tháng, phối hợp triển khai giữa Viện Công nghệ Thông tin và các trung tâm an toàn thông tin.
4. Chuẩn hóa học liệu chuyên đề cho chương trình cao học: Tích hợp các chuyên đề về tính chất kề $n$-e.c, hình học Affine hữu hạn và giải đấu Paley vào 2 học phần chuyên sâu của chương trình đào tạo thạc sĩ Toán học trong vòng 6 tháng tới, do Ban Chủ nhiệm Khoa Toán - Cơ - Tin học thực hiện.

Đối tượng nên tham khảo luận văn

Tài liệu này là nguồn tham khảo chuyên sâu, phục vụ thiết thực cho 4 nhóm đối tượng:

• Học viên cao học và nghiên cứu sinh ngành Toán học: Phù hợp cho những ai theo đuổi hướng nghiên cứu Lý thuyết đồ thị, Lý thuyết xác suất tổ hợp và Hình học hữu hạn. Luận văn cung cấp hệ thống chứng minh chi tiết cho hơn 10 định lý và bổ đề quan trọng.
• Chuyên gia mật mã học và bảo mật thông tin: Khai thác các đặc tính phân phối giả ngẫu nhiên, ma trận Hadamard và cấu trúc tự bù của đồ thị Paley để thiết kế các hàm băm kháng va chạm và hệ mật mã khóa công khai.
• Kỹ sư thiết kế kiến trúc mạng và khoa học dữ liệu: Ứng dụng nguyên lý đồ thị chính quy mạnh để xây dựng cấu trúc liên kết mạng máy tính chịu lỗi (fault-tolerant network topologies) với hệ số kết nối láng giềng tối ưu.
• Giảng viên các trường đại học khối khoa học tự nhiên: Sử dụng 3 chương nội dung của luận văn làm tài liệu giảng dạy, bài giảng mẫu cho các môn học Toán rời rạc nâng cao và Thiết kế tổ hợp.

Câu hỏi thường gặp

Tính chất kề $n$-e.c của đồ thị có ý nghĩa gì trong thực tiễn?

Tính chất $n$-e.c phản ánh mức độ ngẫu nhiên hoàn hảo có tính tất định của một mạng lưới. Trong mạng truyền thông gồm hàng nghìn nút, tính chất này đảm bảo với bất kỳ 2 nhóm nút hoạt động và nút lỗi cho trước có tổng quy mô bằng $n$, luôn tìm được một nút trung gian liên lạc trực tiếp với toàn bộ nhóm thứ nhất mà hoàn toàn cô lập với nhóm thứ hai, giúp mạng tự phục hồi hiệu quả.

Vì sao đồ thị Paley lại giữ vị trí trung tâm trong nghiên cứu tính chất $n$-e.c?

Đồ thị Paley $P_q$ được xây dựng trên trường hữu hạn $\mathbb{F}_q$ ($q \equiv 1 \pmod 4$) có tính chất tự bù và đối xứng đỉnh-cạnh cao. Nhờ vào ước lượng tổng đặc trưng Schmidt, các nhà toán học đã chứng minh $P_q$ thỏa mãn tính chất $n$-e.c khi $q > n^2 2^{2n-2}$, biến nó thành cây cầu nối hoàn hảo giữa lý thuyết số và tổ hợp đồ thị.

Cận kích thước nhỏ nhất $m_{ec}(3)$ hiện nay đã được giải quyết trọn vẹn chưa?

Chưa trọn vẹn. Luận văn đã tổng hợp và chỉ ra rằng cấp nhỏ nhất thỏa mãn 3-e.c nằm trong khoảng $24 \le m_{ec}(3) \le 28$. Việc tìm ra con số chính xác đơn lẻ giữa 24 và 28 hiện vẫn là bài toán mở đòi hỏi sự kết hợp giữa lý thuyết đồ thị nâng cao và sức mạnh tính toán số học.

Hai phương pháp xây dựng trong Chương 3 mang lại bước đột phá nào?

Phương pháp Xây dựng 1 và 2 đã vượt qua giới hạn của họ Paley đơn lẻ bằng cách kết hợp cấu trúc giải đấu Paley $\dot{P}_q$ với mặt phẳng Affine. Cách tiếp cận này sinh ra ít nhất $2^{\binom{q+1}{2}(1-s(q))}$ đồ thị chính quy mạnh phi đẳng cấu, cung cấp một nguồn cấu trúc ngẫu nhiên phong phú chưa từng có cho ngành lý thuyết đồ thị.

Đồ thị giao khối của hệ bộ ba Steiner $\text{STS}(v)$ trở thành 2-e.c khi nào?

Luận văn chứng minh đồ thị giao khối của $\text{STS}(v)$ đạt chuẩn 2-e.c khi và chỉ khi số phần tử $v \ge 13$. Với $v = 7$ và $v = 9$, đồ thị không thể thỏa mãn các trường hợp khối song song độc lập, trong khi với $v = 13$ (gồm 26 khối), tính chất kề được bảo đảm trọn vẹn.

Kết luận

• Luận văn đã hệ thống hóa toàn diện cơ sở lý thuyết về lớp đồ thị có tính chất kề $n$-e.c và mối quan hệ chặt chẽ với đồ thị ngẫu nhiên vô hạn Rado.
• Xác định chính xác các giá trị cận dưới kích thước tối thiểu $m_{ec}(1) = 4$, $m_{ec}(2) = 9$ và khoanh vùng thành công chặn $24 \le m_{ec}(3) \le 28$.
• Giải quyết trọn vẹn bài toán phân loại tính chất 2-e.c cho đồ thị giao khối của Hệ bộ ba Steiner $\text{STS}(v)$ với điều kiện cần và đủ $v \ge 13$.
• Thiết lập mô hình kiến tạo đồ thị 3-e.c trên không gian Euclid hữu hạn $\mathbb{Z}_p^d$ ($p \ge 7, d \ge 5$) và thông qua ma trận Hadamard dạng Bush cấp $16n^2$.
• Đóng góp 2 phương pháp xây dựng đồ thị ngẫu nhiên chính quy mạnh từ hình học Affine, tạo ra hàng triệu đồ thị phi đẳng cấu mới phục vụ nghiên cứu liên ngành.

Trong giai đoạn 2026–2027, các hướng mở rộng về thuật toán song song nhằm xác định $m_{ec}(3)$ và triển khai mã hóa tổ hợp sẽ tiếp tục được hoàn thiện. Độc giả và các nhà nghiên cứu quan tâm có thể khai thác toàn văn luận văn tại thư viện số Đại học Quốc gia Hà Nội để phát triển các ứng dụng chuyên sâu.