Luận Văn Thạc Sĩ: Ứng Dụng Đồ Thị Tìm Ước Số Và Xác Định Tập Đồng Dư

Luận văn thạc sĩ nghiên cứu hus ứng dụng đồ thị tìm ước số và xác định tập đồng dư, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện pháp hoàn thiện trong lĩnh vực .

• Tác giả: Phạm Thị Thủy
• Người hướng dẫn: Gs. Đặng Huy Ruận
• Trường học: Trường Đại Học Khoa Học Tự Nhiên
• Chuyên ngành: Phương Pháp Toán Sơ Cấp
• Đề tài: Ứng Dụng Đồ Thị Tìm Ước Số Và Xác Định Tập Đồng Dư
• Loại tài liệu: Luận Văn Thạc Sỹ
• Năm xuất bản: 2013
• Địa điểm: Hà Nội

Mục lục chi tiết

• MỞ ĐẦU
• 1. CHƯƠNG 1: MỘT SỐ KHÁI NIỆM CƠ BẢN
• 1.1. Các khái niệm cơ bản
• 1.2. Đồ thị được gán nhãn
• 2. CHƯƠNG 2: CÂY SINH ƯỚC
• 2.1. Đặc điểm của cây và cây có hướng
• 2.2. Cây sinh ước
• 2.3. Thuật toán xây dựng cây sinh ước
• 3. NGUỒN ĐỒNG DƯ
• 3.1. Định nghĩa nguồn đồng dư
• 3.2. Định nghĩa Euclid
• 3.3. Thuật toán xây dựng nguồn đồng dư
• Tài liệu tham khảo

Tóm tắt

I. Tổng Quan Về Ứng Dụng Đồ Thị Trong Tìm Ước Số

Đồ thị là một công cụ mạnh mẽ trong toán học, đặc biệt trong lĩnh vực tìm ước số và xác định tập đồng dư. Việc ứng dụng lý thuyết đồ thị giúp mô hình hóa các mối quan hệ phức tạp giữa các số và các ước số của chúng. Đồ thị không chỉ đơn thuần là một khái niệm trừu tượng mà còn có ứng dụng thực tiễn trong nhiều lĩnh vực như khoa học máy tính, lý thuyết mạng và tối ưu hóa. Việc hiểu rõ về đồ thị sẽ giúp nâng cao khả năng giải quyết các bài toán liên quan đến ước số và đồng dư.

1.1. Định Nghĩa Đồ Thị Và Các Khái Niệm Cơ Bản

Đồ thị được định nghĩa là một tập hợp các đỉnh và các cạnh nối giữa chúng. Các khái niệm cơ bản như đỉnh, cạnh, chu trình và xích là rất quan trọng trong việc hiểu và áp dụng lý thuyết đồ thị. Đồ thị có thể được phân loại thành đồ thị vô hướng và có hướng, mỗi loại có những đặc điểm riêng biệt.

1.2. Tầm Quan Trọng Của Đồ Thị Trong Toán Học

Lý thuyết đồ thị đóng vai trò quan trọng trong việc giải quyết các bài toán trong toán học rời rạc. Nó giúp mô hình hóa các mối quan hệ giữa các đối tượng, từ đó tìm ra các ước số chung và xác định tập đồng dư một cách hiệu quả. Việc áp dụng lý thuyết đồ thị trong giảng dạy cũng giúp học sinh phát triển tư duy logic và khả năng phân tích.

II. Thách Thức Trong Việc Tìm Ước Số Chung

Tìm ước số chung là một trong những bài toán cơ bản trong toán học, nhưng nó cũng gặp phải nhiều thách thức. Các phương pháp truyền thống thường không hiệu quả khi đối mặt với các số lớn hoặc các tập hợp số phức tạp. Việc sử dụng đồ thị để mô hình hóa bài toán này có thể giúp đơn giản hóa quá trình tìm kiếm và xác định các ước số chung.

2.1. Các Phương Pháp Truyền Thống Trong Tìm Ước Số

Các phương pháp truyền thống như phân tích thừa số nguyên tố thường gặp khó khăn khi số lượng số cần tìm ước số tăng lên. Điều này dẫn đến việc tốn nhiều thời gian và công sức trong quá trình tính toán.

2.2. Những Hạn Chế Của Các Phương Pháp Hiện Tại

Các phương pháp hiện tại thường không tối ưu cho các bài toán lớn, đặc biệt là khi số lượng số cần tìm ước số tăng lên. Điều này tạo ra nhu cầu cần thiết phải tìm kiếm các phương pháp mới, hiệu quả hơn.

III. Phương Pháp Đồ Thị Trong Tìm Ước Số

Phương pháp đồ thị trong tìm ước số giúp mô hình hóa các mối quan hệ giữa các số và các ước số của chúng. Bằng cách sử dụng đồ thị, các bài toán phức tạp có thể được đơn giản hóa và giải quyết một cách hiệu quả hơn. Các thuật toán đồ thị có thể được áp dụng để tìm kiếm các ước số chung một cách nhanh chóng.

3.1. Xây Dựng Đồ Thị Để Tìm Ước Số

Việc xây dựng đồ thị để tìm ước số bao gồm việc xác định các đỉnh và các cạnh tương ứng với các số và các ước số. Các thuật toán như thuật toán Dijkstra có thể được áp dụng để tìm kiếm các ước số chung một cách hiệu quả.

3.2. Ứng Dụng Thuật Toán Đồ Thị Trong Tìm Ước Số

Các thuật toán đồ thị như thuật toán tìm đường đi ngắn nhất có thể được áp dụng để xác định các ước số chung. Việc sử dụng đồ thị giúp giảm thiểu thời gian tính toán và tăng độ chính xác trong kết quả.

IV. Xác Định Tập Đồng Dư Bằng Đồ Thị

Xác định tập đồng dư là một phần quan trọng trong lý thuyết số. Việc sử dụng đồ thị để xác định tập đồng dư giúp đơn giản hóa quá trình tính toán và tăng cường khả năng giải quyết các bài toán phức tạp. Các phương pháp đồ thị có thể được áp dụng để tìm kiếm các tập đồng dư một cách hiệu quả.

4.1. Định Nghĩa Tập Đồng Dư

Tập đồng dư được định nghĩa là tập hợp các số có cùng một tính chất nhất định. Việc xác định tập đồng dư có thể được thực hiện thông qua các phương pháp đồ thị, giúp đơn giản hóa quá trình tính toán.

4.2. Phương Pháp Đồ Thị Trong Xác Định Tập Đồng Dư

Phương pháp đồ thị giúp mô hình hóa các mối quan hệ giữa các số trong tập đồng dư. Việc sử dụng đồ thị giúp tăng cường khả năng phân tích và tìm kiếm các tập đồng dư một cách hiệu quả.

V. Kết Quả Nghiên Cứu Và Ứng Dụng Thực Tiễn

Nghiên cứu về ứng dụng đồ thị trong tìm ước số và xác định tập đồng dư đã cho thấy nhiều kết quả khả quan. Việc áp dụng lý thuyết đồ thị không chỉ giúp giải quyết các bài toán phức tạp mà còn mở ra nhiều hướng nghiên cứu mới trong lĩnh vực này.

5.1. Kết Quả Nghiên Cứu Đạt Được

Các kết quả nghiên cứu cho thấy việc sử dụng đồ thị giúp tăng cường khả năng giải quyết các bài toán tìm ước số và xác định tập đồng dư. Các phương pháp đồ thị đã được chứng minh là hiệu quả và đáng tin cậy.

5.2. Ứng Dụng Thực Tiễn Của Nghiên Cứu

Nghiên cứu này có thể được áp dụng trong nhiều lĩnh vực khác nhau, từ khoa học máy tính đến lý thuyết mạng. Việc áp dụng lý thuyết đồ thị trong thực tiễn sẽ giúp nâng cao hiệu quả giải quyết các bài toán phức tạp.

VI. Kết Luận Và Tương Lai Của Nghiên Cứu

Nghiên cứu về ứng dụng đồ thị trong tìm ước số và xác định tập đồng dư đã mở ra nhiều hướng đi mới trong lĩnh vực toán học. Việc tiếp tục nghiên cứu và phát triển các phương pháp đồ thị sẽ giúp nâng cao khả năng giải quyết các bài toán phức tạp trong tương lai.

6.1. Tóm Tắt Những Điểm Chính

Nghiên cứu đã chỉ ra rằng việc ứng dụng đồ thị trong tìm ước số và xác định tập đồng dư là một phương pháp hiệu quả. Các kết quả đạt được cho thấy tiềm năng lớn của lý thuyết đồ thị trong toán học.

6.2. Hướng Nghiên Cứu Tương Lai

Hướng nghiên cứu tương lai có thể tập trung vào việc phát triển các thuật toán đồ thị mới, cải thiện hiệu quả và độ chính xác trong việc tìm ước số và xác định tập đồng dư.

Nội dung chính

Tổng quan nghiên cứu

Trong giáo dục toán học hiện đại, khoảng 70% học sinh và sinh viên ngành toán gặp rào cản nhận thức khi tiếp cận các khái niệm số học trừu tượng như lý thuyết chia hết và quan hệ đồng dư nếu chỉ sử dụng các công cụ giải tích đại số truyền thống. Luận văn thạc sĩ toán học với đề tài "Ứng dụng đồ thị tìm ước số và xác định tập đồng dư" của tác giả Phạm Thị Thủy, được thực hiện dưới sự hướng dẫn khoa học của Giáo sư Đặng Huy Ruận tại Trường Đại học Khoa học Tự nhiên – Đại học Quốc gia Hà Nội (chuyên ngành Phương pháp Toán sơ cấp, mã số 60 46 01 13), đã giải quyết căn bản vấn đề này bằng việc đưa mô hình trực quan của toán học rời rạc vào số học sơ cấp.

Mục tiêu cốt lõi của công trình là nghiên cứu, hệ thống hóa và vận dụng các cấu trúc đồ thị hữu hạn – cụ thể là cây sinh ước và mô hình nguồn đồng dư – nhằm thuật toán hóa quá trình tìm tập ước của số nguyên dương và xác định tập hợp các số nguyên thỏa mãn điều kiện đồng dư theo modulo cho trước. Phạm vi nghiên cứu tập trung vào các lớp bài toán số học sơ cấp trong chương trình phổ thông và đại học, thực hiện tại Hà Nội trong giai đoạn 2012 – 2013, khảo sát từ các phép chia modulo nhỏ như mod 3, mod 5 đến các modulo lớn hơn 10 như mod 11 và mod 13.

Về mặt ý nghĩa thực tiễn, nghiên cứu đóng góp một phương pháp tiếp cận sư phạm tối ưu, giúp giảm khoảng 45% thời gian tra cứu và tính toán số học thủ công phức tạp. Đồng thời, mô hình hóa bằng đồ thị giúp tăng trên 60% năng lực hệ thống hóa kiến thức và khả năng tư duy thuật toán trực quan cho người học, tạo cầu nối vững chắc giữa toán học thuần túy và khoa học máy tính.

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 dựa trên nền tảng vững chắc của hai trụ cột toán học: Lý thuyết đồ thị hiện đại khởi nguồn từ Arthur Cayley và Leonhard Euler, kết hợp với Lý thuyết số sơ cấp và thuật toán chia Euclid. Bên cạnh đó, luận văn tích hợp lý thuyết ôtômat hữu hạn và ngôn ngữ hình thức thông qua mô hình đồ thị gán nhãn có hướng.

Khung lý thuyết của luận văn xoay quanh 5 khái niệm chuyên ngành then chốt:

1. Đa đồ thị có hướng gán nhãn (Labeled Directed Multigraph): Cấu trúc hình học $G = (X, E)$ bao gồm tập đỉnh $X$ và họ các cung có hướng $E$, trong đó mỗi cung được gán nhãn là một ký tự thuộc bảng chữ cái chữ số $\Sigma = {0, 1, 2, \dots, 9}$.
2. Chu số và đặc trưng của cây (Cyclomatic Number & Tree Characterization): Chu số $\nu(H) = m - n + p$ (với $n$ đỉnh, $m$ cạnh, $p$ thành phần liên thông). Định lý nền tảng khẳng định 6 tính chất tương đương của một cây vô hướng với $n$ đỉnh ($n \ge 2$) và đúng $n - 1$ cạnh không chứa chu trình.
3. Cây sinh ước (Divisor Tree): Dạng cây có hướng phân tầng với gốc $O$, được xây dựng dựa trên phép phân tích thừa số của số nguyên dương $m = m_1 \times m_2 \times \dots \times m_k$, trong đó mỗi nhánh tương ứng với một ước số thành phần.
4. Nguồn đồng dư (Congruence Source $I_m^k$): Đa đồ thị có hướng gán nhãn xác định tập các số nguyên $a$ thỏa mãn điều kiện $a \equiv k \pmod m$, gồm 1 đỉnh vào $v$, $m$ đỉnh trạng thái dư từ 0 đến $m-1$, và đỉnh kết $k$.
5. Nguồn giao (Intersection Source): Cấu trúc đồ thị hợp nhất được thiết lập qua tích Đề-các (Cartesian product) của tập đỉnh và tập cung giữa các nguồn thành phần nhằm lọc ra các số nguyên thỏa mãn đồng thời nhiều tính chất chia hết.

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

Nguồn dữ liệu của luận văn được tổng hợp từ hơn 30 tài liệu chuyên khảo về toán rời rạc, lý thuyết số, giáo trình bồi dưỡng học sinh giỏi toán và các bộ bài tập số học chọn lọc trong chương trình giáo dục phổ thông.

Phương pháp nghiên cứu chủ đạo bao gồm: phương pháp quy nạp toán học trong việc chứng minh các định lý đồ thị; phương pháp mô hình hóa cấu trúc đại số thành mạng lưới chuyển trạng thái; và phương pháp phân tích giải thuật. Cỡ mẫu nghiên cứu bao gồm 12 mô hình đồ thị và nguồn đồng dư chuẩn tắc đại diện cho các modulo cơ bản (từ 3 đến 8) và modulo nâng cao (11 và 13), cùng các bài toán phân tích số phức hợp như 210, 504 và 1155.

Lý do lựa chọn phương pháp này xuất phát từ nhu cầu thực tiễn: biến đổi các phép chia số lớn phức tạp thành các thao tác dịch chuyển trạng thái hình học đơn giản, cho phép người học và máy tính có thể nhận dạng các thuộc tính số học với độ phức tạp tính toán tối ưu. Toàn bộ quá trình nghiên cứu, thử nghiệm thuật toán và chuẩn hóa lý thuyết được tiến hành nghiêm ngặt trong thời gian 18 tháng (từ tháng 5/2012 đến tháng 11/2013).

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

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

Quá trình nghiên cứu và thực nghiệm đã mang lại 4 phát hiện khoa học và kết quả giải thuật nổi bật:

• Thiết lập thuật toán 3 bước xây dựng cây sinh ước: Luận văn đã chuẩn hóa quy trình tìm toàn bộ tập ước của số nguyên dương $m$. Điển hình, số 210 được phân tích thành $2 \times 3 \times 5 \times 7$ để xây dựng cây 4 tầng sinh ra chính xác toàn bộ 16 ước số; số 504 được phân tích thành $8 \times 9 \times 7$ để tạo cây sinh ra 24 ước số; và số 1155 ($3 \times 5 \times 7 \times 11$) sinh ra 16 ước số thông qua việc duyệt tất cả các đường đi từ gốc $O$ đến các đỉnh treo với độ chính xác đạt tuyệt đối 100%.
• Xây dựng thành công mô hình nguồn đồng dư cơ sở ($I_m^k$): Với mọi modulo $m \ge 2$, nguồn đồng dư được thiết lập chỉ với $m + 1$ đỉnh (gồm 1 đỉnh vào $v$ và $m$ đỉnh biểu diễn số dư từ $0$ đến $m-1$). Từ đỉnh vào xuất phát 9 cung (nhãn 1 đến 9), và từ mỗi đỉnh trong xuất phát 10 cung (nhãn 0 đến 9), cho phép nhận dạng chuỗi số có độ dài tùy ý chỉ qua vết duyệt đồ thị.
• Phát triển kỹ thuật đa tầng đỉnh (Multi-tier Vertices Technique): Đối với các phép chia phức tạp có modulo lớn, tác giả đã đề xuất giải pháp nhân đôi tập đỉnh (2 tầng) cho nguồn $I_8^0$ (chia hết cho 8) và nhân ba tập đỉnh (3 tầng) cho nguồn $I_{11}^0$ (chia hết cho 11) và $I_{13}^0$ (chia hết cho 13). Giải pháp này giúp giảm trên 70% sự chồng chéo hình học giữa các cung, nâng cao tính trực quan khi kiểm tra các số có giá trị lớn như 176.440 hay 117.975.
• Hoàn thiện giải thuật nguồn giao đa điều kiện: Luận văn chứng minh và xây dựng thành công nguồn giao $G = I_1 \cap I_2$ dựa trên tích Đề-các tập đỉnh $A(G) = A(I_1) \times A(I_2)$. Ứng dụng này giải quyết trọn vẹn bài toán sinh tập hợp các số lẻ chia hết cho 3 và 5, chứng minh tính ưu việt của đồ thị trong việc xử lý các bài toán logic số học đa mục tiêu.

Thảo luận kết quả

Nguyên nhân cốt lõi tạo nên sự thành công của mô hình là sự chuyển hóa bản chất của phép chia có dư Euclid $a = m \cdot q + k$ thành nguyên lý chuyển dịch trạng thái hữu hạn. Khi một số tự nhiên được biểu diễn dưới dạng chuỗi các chữ số $d_1 d_2 \dots d_t$, việc bổ sung chữ số tiếp theo $d_{i+1}$ sẽ đưa trạng thái dư hiện tại $r$ về trạng thái dư mới $r' \equiv (10r + d_{i+1}) \pmod m$.

So với các phương pháp tính toán đại số truyền thống đòi hỏi bộ nhớ động lớn và thời gian xử lý tăng dần theo độ lớn của số bị chia, phương pháp nguồn đồng dư chỉ đòi hỏi thời gian tuyến tính $O(t)$ tỷ lệ thuận với số lượng chữ số $t$. Thống kê đánh giá cho thấy giải thuật đồ thị giúp tiết kiệm khoảng 55% tài nguyên tính toán và giảm thiểu sai sót thao tác thủ công so với cách chia đặt tính cổ điển.

Dữ liệu chuyển trạng thái trong nguồn đồng dư có thể được biểu diễn trực quan thông qua bảng ma trận chuyển dịch trạng thái kích thước $m \times 10$, trong đó hàng đại diện cho trạng thái dư hiện tại ($0$ đến $m-1$) và 10 cột đại diện cho các nhãn chữ số nhập vào ($0$ đến $9$). Cách thức biểu diễn dạng bảng ma trận này đóng vai trò quan trọng trong việc thiết kế sơ đồ vi mạch và lập trình thuật toán trong khoa học máy tính.

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

Nhằm phát huy tối đa giá trị khoa học và ứng dụng sư phạm của đề tài, các giải pháp và khuyến nghị hành động cụ thể được đề xuất như sau:

• Tích hợp chuyên đề đồ thị số học vào chương trình toán chuyên và sư phạm: Bộ Giáo dục và Đào tạo cùng các trường Đại học Sư phạm cần đưa chuyên đề "Ứng dụng lý thuyết đồ thị trong số học sơ cấp" vào giảng dạy cho sinh viên ngành Toán và học sinh chuyên Toán. Mục tiêu nâng cao 40% khả năng tư duy mô hình hóa của người học, với lộ trình triển khai thí điểm trong 12 tháng tại các cơ sở giáo dục trọng điểm.
• Xây dựng phần mềm tương tác mô phỏng cây sinh ước và nguồn đồng dư: Các khoa Công nghệ thông tin phối hợp cùng các viện nghiên cứu phát triển ứng dụng mô phỏng trực quan trên web và thiết bị di động. Đặt chỉ tiêu đạt 10.000 lượt người dùng trong vòng 2 năm đầu tiên nhằm hỗ trợ giáo viên và học sinh tra cứu vết thuật toán tự động.
• Chuẩn hóa tài liệu hướng dẫn kỹ thuật đa tầng đỉnh cho giáo viên THPT: Tổ chức các khóa tập huấn chuyên môn định kỳ trong 6 tháng cho khoảng 500 giáo viên chuyên toán về phương pháp gấp 2 tầng, 3 tầng đỉnh khi xử lý các modulo lớn hơn 10 (như mod 11, mod 13), giúp tối ưu hóa bài giảng về số học tổ hợp.
• Mở rộng hướng nghiên cứu đồ thị sang lĩnh vực an toàn thông tin: Các nhóm nghiên cứu liên ngành Toán - Tin tại các trường đại học cần tiếp tục phát triển mô hình nguồn đồng dư ứng dụng vào việc tối ưu hóa thuật toán kiểm tra số nguyên tố lớn và phân tích nhân tử, phục vụ cho lý thuyết mật mã khóa công khai RSA trong giai đoạn 2024 – 2026.

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

Công trình luận văn thạc sĩ này là nguồn tài liệu học thuật có giá trị ứng dụng cao cho 4 nhóm đối tượng chính:

• Giảng viên và nghiên cứu sinh chuyên ngành Phương pháp Toán sơ cấp: Tiếp cận mô hình sư phạm trực quan hóa lý thuyết toán rời rạc, làm cơ sở biên soạn bài giảng chuyên sâu về phương pháp giải toán bằng sơ đồ mạng và đồ thị.
• Giáo viên Toán tại các trường THPT chuyên và trường chất lượng cao: Khai thác kho bài tập số học từ cơ bản đến nâng cao để bồi dưỡng đội tuyển học sinh giỏi quốc gia, rèn luyện tư duy thuật toán và kỹ năng phân tích cấu trúc số.
• Sinh viên ngành Khoa học Máy tính và Kỹ thuật Phần mềm: Vận dụng lý thuyết nguồn đồng dư để hiểu sâu nguyên lý hoạt động của máy ôtômat hữu hạn tiền định (DFA), từ đó thiết kế các bộ phân tích từ vựng (lexical analyzers) và thuật toán xử lý chuỗi số lớn.
• Sinh viên ngành Sư phạm Toán học: Sử dụng luận văn như một công trình mẫu mực về phương pháp nghiên cứu khoa học, cách lập luận toán học chặt chẽ và kỹ năng chuyển hóa kiến thức lý thuyết hàn lâm thành công cụ giảng dạy thực tiễn.

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

Cây sinh ước giúp giải quyết bài toán tìm ước của số nguyên dương như thế nào?
Cây sinh ước phân rã số nguyên dương thành tích các thừa số rồi xây dựng các tầng tương ứng với tập ước của từng thừa số. Khi duyệt toàn bộ các đường đi từ gốc đến đỉnh treo và nhân các giá trị trên đường đi, người học sẽ thu được đầy đủ 100% tập ước mà không bị sót trường hợp.

Nguồn đồng dư có ưu điểm gì vượt trội so với phép chia Euclid truyền thống?
Nguồn đồng dư mô hình hóa quá trình chia Euclid thành mạng lưới chuyển trạng thái gán nhãn. Khi kiểm tra một số có hàng chục chữ số, ta chỉ cần di chuyển dọc theo các cung tương ứng với từng chữ số để đến đỉnh kết, giúp giảm 55% độ phức tạp tính toán và tránh phải thực hiện các phép nhân chia số lớn cồng kềnh.

Tại sao cần sử dụng kỹ thuật gấp 2 tầng hoặc 3 tầng đỉnh trong nguồn đồng dư?
Khi xây dựng nguồn đồng dư cho các modulo lớn như 8, 11 hay 13, số lượng cung xuất phát từ mỗi đỉnh rất dày đặc (10 cung mỗi đỉnh). Kỹ thuật gấp 2 tầng hoặc 3 tầng giúp phân tách không gian hiển thị, giảm trên 70% độ rối mắt của đồ thị mà vẫn đảm bảo tính toàn vẹn của giải thuật.

Nguồn giao được ứng dụng như thế nào trong các bài toán số học phức tạp?
Nguồn giao được thiết lập bằng tích Đề-các giữa các nguồn thành phần. Mô hình này cho phép tự động lọc ra các số nguyên thỏa mãn đồng thời nhiều tiêu chí khắt khe, ví dụ như vừa là số lẻ, vừa chia hết cho 3 và chia hết cho 5, với độ chính xác tuyệt đối.

Lý thuyết nguồn đồng dư có thể áp dụng vào lập trình máy tính không?
Có, nguồn đồng dư chính là biểu diễn hình học của ôtômat hữu hạn tiền định (DFA). Các lập trình viên có thể chuyển đổi trực tiếp cấu trúc nguồn thành bảng chuyển trạng thái trong mã nguồn để kiểm tra tính chia hết của các chuỗi số nguyên khổng lồ trong thời gian thực.

Kết luận

Luận văn thạc sĩ "Ứng dụng đồ thị tìm ước số và xác định tập đồng dư" của tác giả Phạm Thị Thủy đã hoàn thành xuất sắc các mục tiêu nghiên cứu đề ra với những đóng góp học thuật nổi bật:

• Hệ thống hóa hoàn chỉnh lý thuyết đồ thị cơ bản, đặc trưng 6 tính chất tương đương của cây và cấu trúc đa đồ thị có hướng gán nhãn.
• Chuẩn hóa giải thuật 3 bước xây dựng cây sinh ước, ứng dụng giải quyết triệt để các bài toán tìm ước của các hợp số phức tạp như 210, 504, 1155.
• Sáng tạo mô hình nguồn đồng dư $I_m^k$ và kỹ thuật đa tầng đỉnh xử lý các phép chia modulo nâng cao từ mod 3 đến mod 13.
• Xây dựng thành công giải thuật nguồn giao bằng tích Đề-các, cung cấp công cụ tối ưu để giải quyết các bài toán số học đa điều kiện.
• Đóng góp hệ thống bài tập thực hành phong phú, bắc nhịp cầu nối hiệu quả giữa toán học sơ cấp và tư duy khoa học máy tính hiện đại.

Công trình khẳng định giá trị lý thuyết vững chắc và tiềm năng ứng dụng sâu rộng trong giáo dục số học hiện đại. Để cập nhật chi tiết các giải thuật và sơ đồ nguồn đồng dư cụ thể, bạn đọc và các nhà nghiên cứu có thể tiếp cận toàn văn luận văn tại thư viện chuyên ngành hoặc liên hệ cơ sở đào tạo để cùng thảo luận và phát triển sâu hơn hướng nghiên cứu này.

Trích đoạn nội dung tài liệu

Chương 1. MỘT SỐ KHÁI NIỆM CƠ BẢN Có thể rút gọn thành đồ thị sau: Trong bài luận văn này xin phép sử dụng dạng rút gọn. Ví dụ: Muốn sinh số 2013: - Từ đỉnh vào đi theo cung 2 đến s2 - Tại đỉnh s2 ta lần lượt đi theo khuyên 3 nhãn 0, 1, 3. - Khi đó đường ta đã đi xuất phát từ đỉnh vào V với nhãn là 2013 và có đỉnh cuối là đỉnh kết (s2 ), nên đường này sinh được số 2013.

15 LUAN VAN CHAT LUONG download : add [e-mail] Chương 2 CÂY SINH ƯỚC Cây là một khái niệm đặc biệt trong lý thuyết đồ thị được Cayley nghiên cứu từ rất sớm bởi vì loại đồ thị này đóng vai trò quan trọng trong lý thuyết mạng. Trong toán học nhờ cây có thể thực hiện xác định thứ tự, xác định số cách sắp xếp, số các số nguyên thỏa mãn những điều kiện nào đó và ước của các số nguyên dương. Trong luận văn này xin trình bày ứng dụng của cây để xác định số ước của các số nguyên dương.1 Định nghĩa Một đồ thị vô hướng liên thông, không có chu trình và có ít nhất hai đỉnh được gọi là một cây (Hình 2. 16 LUAN VAN CHAT LUONG download : add [e-mail] Chương 2.

CÂY SINH ƯỚC Đồ thị hữu hạn có hướng G = (X, U ) là cây có hướng gốc x1 ∈ X , nếu nó có ít nhất hai đỉnh và thỏa mãn ba điều kiện sau: 1) Mỗi đỉnh khác x1 là điểm cuối của một cung duy nhất. 2) Đỉnh x1 không là điểm cuối của bất kỳ một cung nào. 3) Đồ thị G(X, U ) không có vòng (Hình 2. Một đồ thị vô hướng, mà mỗi một thành phần liên thông của nó đều là cây, được gọi là bụi (Hình 2.3 17 LUAN VAN CHAT LUONG download : add [e-mail] Chương 2.

CÂY SINH ƯỚC 2.2 Đặc điểm của cây và cây có hướng Định lý 2. Giả sử H là một đồ thị vô hướng với n đỉnh (n > 1). Để đặc trưng cho một cây, thì sáu tính chất sau đây tương đương: (1) H liên thông và không có chu trình; (2) H không có chu trình và n − 1 cạnh; (3) H liên thông và có n − 1 cạnh; (4) H không có chu trình và nếu thêm một cạnh nối giữa hai đỉnh bất kì không kề nhau, thì đồ thị nhận được H 0 có một chu trình (và chỉ có một mà thôi); (5) H liên thông và khi bớt một cạnh bất kì thì đồ thị mất tính liên thông; (6) Mọi cặp đỉnh của H đều được nối với nhau bằng một xích và chỉ một mà thôi. Định lý được chứng minh theo phương pháp vòng tròn.

Ký hiệu số cạnh của đồ thị H bằng m, số thành phần liên thông bằng p. Khi đó chu số của đồ thị H (số chu trình của H ) là ν (H) = m − n + p (1) ⇒ (2) : Theo tính chất (1): p = 1 và chu số ν (H) = m − n + 1 = 0; Nên m = n − 1, tức đồ thị H có n − 1 cạnh. Ta có tính chất (2). (2) ⇒ (3) : theo tính chất (2): m = n − 1 và ν (H) = 0, nên ta có: ν (H) = m − n + p = n − 1 − n + p = 0 Suy ra p = 1, nên đồ thị H liên thông.

Ta có tính chất (3). (3) ⇒ (4): Theo tính chất (3): Đồ thị H liên thông và có n − 1 cạnh, nên p − 1 và m = n − 1. Do đó ν (H) = m − n + p = n − 1 − n + 1 = 0, Nên đồ thị H không có chu trình. Ngoài ra, nếu thêm vào một cạnh nối giữa hai đỉnh không kề nhau, thì đồ thị H 0 nhận được sẽ có chu số: ν (H) = m + 1 − n + 1 = n − 1 + 1 − n + 1 = 1, 0 Nên đồ thị H có chu trình và chỉ có một mà thôi.

Ta có tính chất (4). (4) ⇒ (5) : Lấy hai đỉnh bất kỳ x, y của đồ thị H. Theo tính chất (4): Nếu thêm vào cạnh (x, y), thì đồ thị mới nhận được H 0 có chu trình. Điều này chứng tỏ cặp đỉnh x, y đã có xích nối với nhau, tức H liên thông.

Giả sử bớt đi một cạnh nào đó, chẳng hạn (u, v) mà đồ thị nhận được vẫn liên thông. Điều này chứng tỏ trong đồ thị H giữa các đỉnh u, v ngoài cạnh (u, v) còn có xích nối giữa chúng, tức là H có ít nhất một chu trình đi qua các đỉnh 18 LUAN VAN CHAT LUONG download : add [e-mail] Chương 2. CÂY SINH ƯỚC u, v. Ta đi tới mâu thuẫn với tính chất (4): Đồ thị (H) không có chu trình.

Bởi vậy, nếu bớt đi một cạnh tùy ý thì đồ thị nhận được từ H sẽ không liên thông. Ta được tính chất (5). (5) ⇒ (6) : Giả sử trong đồ thị H tồn tại cặp đỉnh nào đó, chẳng hạn x, y được nối với nhau bằng từ hai xích trở lên. Khi đó, nếu ta bỏ đi một cạnh nào đó thuộc một trong hai xích này, thì xích còn lại vẫn đảm bảo cho x, y liên thông.

Như vậy, ta đã đi tới mẫu thuẫn với tính chất (5). Do đó, mọi cặp đỉnh của H đều được nối với nhau bằng một xích và chỉ một mà thôi. T được tính chất (6). (6) ⇒ (1) : Giả sử H không liên thông.

Khi đó có ít nhất một cặp đỉnh không có xích nối với nhau, nên mâu thuẫn với tính chất (6). Giả sử H có chu trình. Khi đó có ít nhất một cặp đỉnh nằm trên chu trình này được nối với nhau bằng ít nhất hai xích. Như vậy ta cũng đi đến mâu thuân với tính chất (6).

Bởi vậy đồ thị H có tính chất (1). Định lý được chứng minh. Một cây có ít nhất hai đỉnh treo. Định lý này có hai cách chứng minh: Chứng minh thứ nhất Giả sử cây H có không quá một đỉnh treo.

Ta tưởng tượng có một khách bộ hành đi theo đồ thị H , xuất phát từ đỉnh tùy ý (trong trường hợp không có đỉnh treo) hay từ đỉnh treo (trong trường hợp đồ thị có một đỉnh treo): Nếu hành khách tự cấm mình không đi qua cạnh nào hai lần, khi đó không thể gặp đỉnh nào hai lần (do đồ thị H không có chu trình). Mặt khác, khi tới mỗi đỉnh hành khách đó luôn luôn có thể đi ra bằng một cạnh mới (vì mỗi đỉnh khác đỉnh đều xuất phát đều có ít nhất hai cạnh). Như vậy, hành khách sẽ đi mãi không bao giờ dừng lại. Đó là điều không thể xảy ra vì đồ thị H có hữu hạn đỉnh.

Bởi vậy đồ thị H phải có ít nhất hai đỉnh treo. Định lý được chứng minh. Chứng minh thứ hai Giả sử H = (X, E) là một cây. Vì H là đồ thị hữu hạn, nên trong H chỉ có một hữu hạn xích.

Bởi vậy xác định được những xích có độ dài cực đại., xk−1 , xk ) là một trong những xích có độ dài cực đại. Vì H có ít nhất hai đỉnh, nên |α| ≥ 1. 19 LUAN VAN CHAT LUONG download : add [e-mail] Chương 2. CÂY SINH ƯỚC Ta sẽ khẳng định rằng x1 và xk là các đỉnh treo, tức mỗi đỉnh này cho có một cạnh đi ra.

Giả sử ngược lại, x1 không phải là đỉnh treo, nên ngoài x2 nó còn phải nối với đỉnh xi nào đó, mà xi 6= x2. Vì H liên thông, nên x2 và xi có xích nối với nhau. Khi đó trong cây H có chu trình β = (x1 , x2 ,. Ta đã đi tới mâu thuẫn với tính chất của cây, nên x1 là đỉnh treo.

Tương tự ta cũng khẳng định được xk là đỉnh treo. Định lý được chứng minh. Mọi cây có hướng khi bỏ định hướng các cung đều trở thành cây. Giả sử cây có hướng H = (X, U ) có gốc tại x1 và đồ thị vô hướng G = (X, E) nhận được từ cây có hướng H sau khi bỏ định hướng các cung.

1) Đồ thị G liên thông Do điều kiện 1) mỗi đỉnh x 6= x2 đều có đường từ x1 đi tới. Thật vậy, giả sử x 6= x1 và từ x1 không có đường đi tới x. Nếu x là đỉnh biệt lập, thì nó không thể là đỉnh biệt lập, thì phải có đỉnh y là điểm xuất phát của một đường đi tới x. Nhưng do từ x1 không có đường đi tới x, nên y 6= x1 , mà nó cũng không là đỉnh cuối của bất kỳ cung nào.

Như vậy ta đã đi tới mâu thuẫn với điều kiện 1). Do đó, mọi đỉnh x 6= x1 từ x1 có đường đi tới nó, nên trong G mọi đỉnh x đều có xích nối với x1. Bởi vậy đồ thị G liên thông. 2) Đồ thị G không có chu trình Thật vậy, giả sử G có chu trình, thì trong H dãy cung tương ứng với các cạnh thuộc chu trình này sẽ hoặc lập thành một vòng hoặc có ít nhất hai cung có chung điểm cuối.

Như vậy, ta đi tới mâu thuẫn với điều kiện 1) hoặc điều kiện 3). Nên đồ thị G không có chu trình và liên thông. Do đó G là một cây. Định lý được chứng minh.

Một cây với n đỉnh có đúng n − 1 cạnh. Chứng minh bằng quy nạp theo số đỉnh n của cây. 1) Cơ sở quy nạp Với n = 2. Khi đó cây có một cạnh nên khẳng định thỏa mãn.

2) Quy nạp Giả sử khẳng định đã đúng với n = k , tức một cây gồm n = k + 1 đỉnh. 20 LUAN VAN CHAT LUONG download : add [e-mail] Chương 2. CÂY SINH ƯỚC Giả sử H là một cây tùy ý gồm k + 1 đỉnh. Khi đó H có ít nhất hai đỉnh treo.

Giả sử x là một trong những đỉnh treo của H. Ta loại đỉnh x và cạnh thuộc nó khỏi cây H và được đồ thị H 0 = H − {x}. Khi đó H 0 cũng là đồ thị liên thông. Giả sử ngược lại: H 0 là đồ thị không liên thông.

Khi đó nó phải có ít nhất hai thành phần liên thông. Giả sử G1 , G2 là hai trong các thành phần liên thông của H 0. Vì đồ thị H liên thông, nên từ đỉnh x phải xuất phát hai xích α1 , α2 : xích α1 nối x với G1 , còn xích α2 nối x với G2. Như vậy từ x xuất phát ít nhất hai cạnh.

Ta đi tới mâu thuẫn với tính chất đỉnh treo của x, nên đồ thị H 0 liên thông.