Luận văn bài toán đồ thị con đẳng cấu trong khai phá dữ liệu đồ thị tại ĐH CNTT&TT Thái Nguyên

Luận văn thạc sĩ toán học nghiên cứu hay bài toán đồ thị con đẳng cấu trong khai phá dữ liệu đồ thị và ứng dụng phát hiện đồ thị con phổ, khảo sát thực trạng, phân tích nguyên

• Tác giả: Phạm Thị Liên
• Người hướng dẫn: Pgs. Đoàn Văn Ban
• Trường học: Trường Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên
• Chuyên ngành: Khoa học máy tính
• Đề tài: Bài Toán Đồ Thị Con Đẳng Cấu Trong Khai Phá Dữ Liệu Đồ Thị Và Ứng Dụng Phát Hiện Đồ Thị Con Phổ Biến
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2020
• Địa điểm: Thái Nguyên

Mục lục chi tiết

• LỜI CAM ĐOAN
• LỜI CẢM ƠN
• MỞ ĐẦU
• 1. CHƯƠNG 1: KHAI PHÁ ĐỒ THỊ
• 1.1. Cấu trúc đồ thị
• 1.2. Các dạng biểu diễn cấu trúc dữ liệu đồ thị
• 1.3. Danh sách liên thuộc
• 1.4. Danh sách liền kề
• 1.5. Ma trận liên thuộc
• 1.6. Ma trận liền kề
• 1.7. Dạng chính tắc của đồ thị
• 1.8. Phát hiện cấu trúc cộng đồng mạng xã hội
• 1.9. Khai phá đồ thị con thường xuyên đóng
• 1.10. Tổng kết chương 1
• 2. CHƯƠNG 2: BÀI TOÁN ĐỒ THỊ ĐẲNG CẤU VÀ KHAI PHÁ ĐỒ THỊ CON PHỔ BIẾN
• 2.1. Bài toán đồ thị đẳng cấu
• 2.2. Thuật toán kiểm tra đồ thị đẳng cấu
• 2.3. Thuật toán Dijsktra tìm đường đi ngắn nhất
• 2.4. Thuật toán tính khoảng cách d(u, v) trong các đồ thị phụ thêm và đồ thị kết đôi
• 2.5. Thuật toán xác ma trận dấu và dạng chính tắc của nó
• 2.6. Thuật toán sắp xếp các đỉnh của hai đồ thị để kiểm tra tính đẳng cấu của chúng dựa vào dạng chính tắc
• 2.7. Một số tính chất của đồ thị đẳng cấu
• 2.8. Bài toán đẳng cấu đồ thị con SGI
• 2.9. Một số khái niệm cơ sở và ký hiệu
• 2.10. Cây quyết định của đồ thị
• 2.11. Thuật toán xây dựng cây quyết định
• 2.12. Khai phá đồ thị con phổ biến
• 2.13. Cây các đồ thị con dạng chính tắc
• 2.14. Phép kết nối N-Join hai đồ thị
• 2.15. Thuật toán FFSM cho khai phá đồ thị con phổ biến trong CSDL đồ thị
• 2.16. Kết luận chương 2
• 3. CHƯƠNG 3: THỬ NGHIỆM VÀ ĐÁNH GIÁ
• 3.1. Dữ liệu và môi trường thử nghiệm
• 3.2. Bộ dữ liệu thử nghiệm
• 3.3. Môi trường thử nghiệm
• 3.4. Cài đặt và thử nghiệm thuật toán tìm kiếm tra đồ thị đẳng cấu
• 3.5. Mô tả yêu cầu bài toán kiếm tra đồ thị đẳng cấu
• 3.6. Kết quả thử nghiệm
• 3.7. Thử nghiệm thuật toán FFSM cho khai phá đồ thị con phổ biến
• 3.8. Mô tả yêu cầu bài toán khai phá đồ thị con phổ biến
• 3.9. Phân tích đánh giá kết quả
• 3.10. Kết luận chương 3
• KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Khai Phá Dữ Liệu Đồ Thị Khái Niệm Cơ Bản

Khai phá dữ liệu đồ thị là một lĩnh vực nghiên cứu quan trọng, liên quan đến việc phân tích và khai thác thông tin từ các cấu trúc đồ thị. Đồ thị được định nghĩa là một tập hợp các đỉnh và các cạnh kết nối chúng, thể hiện mối quan hệ giữa các đối tượng. Việc hiểu rõ về cấu trúc và các dạng biểu diễn của đồ thị là rất cần thiết để áp dụng các thuật toán khai phá hiệu quả.

1.1. Định Nghĩa Đồ Thị và Các Thành Phần Cơ Bản

Đồ thị được định nghĩa là một cặp (V, E), trong đó V là tập hợp các đỉnh và E là tập hợp các cạnh. Các đỉnh thể hiện các thực thể, trong khi các cạnh thể hiện mối quan hệ giữa chúng. Việc phân loại đồ thị thành đồ thị có hướng và vô hướng là rất quan trọng trong khai phá dữ liệu.

1.2. Các Dạng Biểu Diễn Cấu Trúc Dữ Liệu Đồ Thị

Có nhiều cách để biểu diễn đồ thị, bao gồm danh sách liên thuộc, danh sách liền kề, ma trận liên thuộc và ma trận liền kề. Mỗi phương pháp có ưu điểm và nhược điểm riêng, ảnh hưởng đến hiệu suất của các thuật toán khai phá.

II. Thách Thức Trong Khai Phá Đồ Thị Con Đẳng Cấu

Bài toán đồ thị con đẳng cấu là một trong những thách thức lớn trong khai phá dữ liệu đồ thị. Độ phức tạp của bài toán này tăng lên khi số lượng đỉnh và cạnh trong đồ thị lớn. Việc tìm kiếm các đồ thị con đẳng cấu hiệu quả là rất cần thiết để giải quyết nhiều vấn đề thực tiễn.

2.1. Độ Phức Tạp Của Bài Toán Đẳng Cấu

Bài toán kiểm tra đẳng cấu đồ thị có độ phức tạp cao, đặc biệt là khi số lượng đỉnh lớn. Các thuật toán hiện tại vẫn chưa đạt được hiệu suất tối ưu cho các đồ thị lớn và phức tạp.

2.2. Các Vấn Đề Liên Quan Đến Dữ Liệu Đồ Thị

Dữ liệu đồ thị thường không đồng nhất và có thể chứa nhiều loại thông tin khác nhau. Việc xử lý và phân tích các loại dữ liệu này đòi hỏi các phương pháp khai thác thông tin hiệu quả.

III. Phương Pháp Giải Quyết Bài Toán Đồ Thị Con Đẳng Cấu

Để giải quyết bài toán đồ thị con đẳng cấu, nhiều thuật toán đã được phát triển. Các thuật toán này thường dựa trên việc chuyển đổi đồ thị về dạng chính tắc và so sánh các dạng này để xác định tính đẳng cấu.

3.1. Thuật Toán Kiểm Tra Đẳng Cấu

Thuật toán kiểm tra đẳng cấu đồ thị là một trong những phương pháp chính để xác định xem hai đồ thị có đẳng cấu hay không. Các thuật toán này thường sử dụng các cấu trúc dữ liệu như ma trận liền kề để tối ưu hóa quá trình kiểm tra.

3.2. Thuật Toán Phát Hiện Đồ Thị Con Phổ Biến

Thuật toán phát hiện đồ thị con phổ biến giúp xác định các mẫu thường xuyên xuất hiện trong dữ liệu đồ thị. Phương pháp này có thể áp dụng trong nhiều lĩnh vực như mạng xã hội và phân tích sinh học.

IV. Ứng Dụng Thực Tiễn Của Khai Phá Đồ Thị Con Đẳng Cấu

Khai phá đồ thị con đẳng cấu có nhiều ứng dụng thực tiễn trong các lĩnh vực như khoa học máy tính, sinh học, và mạng xã hội. Việc phát hiện các mẫu thường xuyên trong dữ liệu đồ thị giúp cải thiện hiệu suất và độ chính xác của các hệ thống.

4.1. Ứng Dụng Trong Khoa Học Dữ Liệu

Trong khoa học dữ liệu, việc phát hiện các đồ thị con phổ biến giúp tối ưu hóa các thuật toán tìm kiếm và phân tích dữ liệu. Điều này có thể cải thiện đáng kể hiệu suất của các hệ thống phân tích lớn.

4.2. Ứng Dụng Trong Mạng Xã Hội

Khai phá đồ thị trong mạng xã hội giúp phát hiện các cộng đồng và mối quan hệ giữa các người dùng. Điều này có thể hỗ trợ trong việc tối ưu hóa quảng cáo và cải thiện trải nghiệm người dùng.

V. Kết Luận và Hướng Phát Triển Tương Lai

Khai phá dữ liệu đồ thị, đặc biệt là bài toán đồ thị con đẳng cấu, vẫn còn nhiều thách thức và cơ hội nghiên cứu. Việc phát triển các thuật toán mới và cải tiến các phương pháp hiện tại sẽ giúp nâng cao hiệu quả của khai phá dữ liệu đồ thị trong tương lai.

5.1. Tương Lai Của Khai Phá Dữ Liệu Đồ Thị

Với sự phát triển nhanh chóng của công nghệ và dữ liệu lớn, khai phá dữ liệu đồ thị sẽ tiếp tục là một lĩnh vực nghiên cứu quan trọng. Các nghiên cứu mới sẽ tập trung vào việc cải thiện hiệu suất và khả năng mở rộng của các thuật toán.

5.2. Các Hướng Nghiên Cứu Mới

Các hướng nghiên cứu mới có thể bao gồm việc áp dụng học máy và trí tuệ nhân tạo vào khai phá dữ liệu đồ thị, nhằm phát hiện các mẫu phức tạp và tối ưu hóa quy trình phân tích.

Nội dung chính

Tổng quan nghiên cứu

Khai phá dữ liệu đồ thị đóng vai trò nòng cốt trong việc xử lý các cấu trúc dữ liệu phi tuyến tính phức tạp thuộc các lĩnh vực mũi nhọn như tin sinh học, hóa tin học, phân tích mạng xã hội và tối ưu hóa truy vấn cơ sở dữ liệu. Thách thức lớn nhất trong việc phát hiện đồ thị con phổ biến xuất phát từ sự bùng nổ không gian trạng thái với độ phức tạp giai thừa n! của các hoán vị đỉnh, khiến bài toán đẳng cấu đồ thị con rơi vào nhóm bài toán NP-đầy đủ. Luận văn tập trung nghiên cứu giải pháp tối ưu hóa bài toán đồ thị con đẳng cấu nhằm nâng cao hiệu năng phát hiện đồ thị con phổ biến trong cơ sở dữ liệu đồ thị quy mô lớn.

Mục tiêu trọng tâm của nghiên cứu là xây dựng và kiểm thử thuật toán kiểm tra đồ thị đẳng cấu dựa trên ma trận dấu chính tắc trong thời gian đa thức, đồng thời ứng dụng cấu trúc cây quyết định cô đọng và thuật toán khai phá đồ thị con nhanh để xử lý tập dữ liệu lên đến 10.000 đồ thị mẫu và mạng lưới liên kết 118 nhà khoa học. Về mặt giá trị thực tiễn và học thuật, luận văn thiết lập nền tảng tính toán vững chắc giúp giảm độ phức tạp tìm kiếm đồ thị con từ cấp số mũ xuống thời gian đa thức, tối ưu hóa hơn 35% thời gian xử lý cơ sở dữ liệu và tiết kiệm đáng kể tài nguyên bộ nhớ khi khai phá các mẫu thường xuyên đóng.

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 lý thuyết đồ thị hiện đại và các nguyên lý khai phá mẫu cấu trúc nâng cao, tập trung vào ba trụ cột lý thuyết chính:

1. Lý thuyết đẳng cấu đồ thị và ma trận dấu: Đồ thị đơn vô hướng được mô hình hóa qua không gian khoảng cách ngắn nhất, đồ thị phụ thêm và đồ thị kết đôi. Ma trận dấu chính tắc được xác định thông qua vector tần suất dấu của các đỉnh, cho phép phân hoạch tập đỉnh thành các lớp tương đương độc lập với thứ tự ban đầu.
2. Ma trận liền kề chính tắc (CAM) và không gian tìm kiếm dạng cây: Khái niệm mã cực đại của tam giác dưới ma trận liền kề được chuẩn hóa để đại diện duy nhất cho một cấu trúc đồ thị, bảo toàn tính chất di truyền cho mọi tiền tố của mã chính tắc.
3. Khai phá đồ thị con phổ biến (FFSM) và cây quyết định: Tích hợp hai phép toán mở rộng N-Join và N-Extension để sinh ứng viên tối ưu, kết hợp với mô hình cây quyết định đa tầng phân lớp theo dãy phần tử hàng - cột có độ dài 2k-1 chỉ mục.

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

Nghiên cứu kết hợp chặt chẽ giữa phân tích mô hình hóa toán học và thực nghiệm thuật toán trên máy tính. Dữ liệu thử nghiệm được xây dựng theo phương pháp chọn mẫu phân tầng có chủ đích bao gồm: kho dữ liệu đồ thị tổng hợp với quy mô lên đến 10.000 đồ thị phục vụ kiểm thử thuật toán khai phá mẫu thường xuyên, cùng bộ dữ liệu mạng xã hội thực tế từ Viện Santa Fe gồm 118 nút và hệ thống các liên kết nghiên cứu học thuật.

Lý do lựa chọn phương pháp này là nhằm kiểm chứng tính đúng đắn của thuật toán trên cả hai khía cạnh: đồ thị thưa kích thước lớn và đồ thị dày đặc có cấu trúc phân cụm phức tạp. Quá trình phân tích thực nghiệm sử dụng thuật toán Dijkstra cải tiến với độ phức tạp 3n² + 3n bước để tính đường đi ngắn nhất, kết hợp thuật toán sinh ma trận kết đôi 7n² + 7n bước và kỹ thuật tìm kiếm nhị phân với thời gian O(log m) trong không gian lưu trữ danh sách liên kết có thứ tự. Tiến trình nghiên cứu được thực hiện liên tục qua các giai đoạn phân tích lý thuyết, cài đặt mã nguồn thử nghiệm, đánh giá thực nghiệm hiệu năng và tối ưu hóa cây quyết định cô đọng.

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

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

1. Giải quyết bài toán kiểm tra đẳng cấu đồ thị trong thời gian đa thức: Nghiên cứu đã chứng minh và thực nghiệm thành công thuật toán so khớp đồ thị dựa trên ma trận dấu chính tắc với tổng số bước tính toán tối đa được chặn trên bởi hàm đa thức 2n⁵ + 14n⁴ + 14n³ + 4n² bước. Kết quả này loại bỏ hoàn toàn sự phụ thuộc vào phép duyệt vét cạn n! trường hợp hoán vị.
2. Tối ưu hóa không gian biểu diễn qua cây quyết định cô đọng: Bằng cách áp dụng ma trận biến đổi hoán vị R và các nhánh định hướng lại, cấu trúc cây quyết định compact đã giảm thiểu từ 40% đến 50% số nút dư thừa do tính tự đẳng cấu của các đồ thị con mức k sinh ra, giúp tốc độ truy vấn đẳng cấu đồ thị con chỉ còn phụ thuộc bậc hai vào số đỉnh của đồ thị đầu vào.
3. Nâng cao hiệu suất khai phá đồ thị con phổ biến với thuật toán FFSM: Khi thử nghiệm trên kho 10.000 đồ thị với nhiều ngưỡng độ hỗ trợ tối thiểu (minsup) khác nhau, thuật toán sử dụng ma trận CAM kết hợp phép nối N-Join đã giảm hơn 35% thời gian sinh mẫu ứng viên so với các phương pháp duyệt đồ thị truyền thống, đồng thời đảm bảo không bỏ sót bất kỳ đồ thị con thường xuyên đóng nào.

Thảo luận kết quả

Hiệu năng vượt trội của thuật toán bắt nguồn từ việc chuẩn hóa không gian trạng thái thông qua vector tần suất dấu và dạng chính tắc duy nhất của ma trận liền kề. Thay vì phải so sánh từng cặp cấu trúc cục bộ, thuật toán chuyển đổi bài toán hình học đồ thị thành bài toán so khớp thứ tự từ điển trên các chuỗi nhãn, từ đó cho phép áp dụng tìm kiếm nhị phân với chi phí O(log m).

Trong thực tế phân tích dữ liệu, các kết quả này có thể được trực quan hóa rất rõ ràng thông qua biểu đồ đường thể hiện mối tương quan nghịch đảo giữa thời gian thực thi (tính bằng giây) và ngưỡng độ hỗ trợ tối thiểu, cùng các bảng tổng hợp phân lớp ma trận kề theo từng bậc kích thước đỉnh từ 2 đến 10 nút. So với thuật toán gSpan và các giải pháp phân cụm đồ thị phân cấp cổ điển, phương pháp kết hợp CAM và cây quyết định compact giúp hệ thống duy trì độ ổn định tính toán cao ngay cả khi mật độ cạnh trong cơ sở dữ liệu đồ thị tăng thêm 20% đến 30%.

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

1. Triển khai mô hình lập chỉ mục ngoại tuyến (offline indexing) bằng cây quyết định compact: Các đơn vị phát triển hệ thống dữ liệu đồ thị cần áp dụng cơ chế tiền xử lý dữ liệu để xây dựng cây quyết định trước, giúp thời gian phản hồi truy vấn đẳng cấu trực tuyến đạt mức O(n²) độc lập hoàn toàn với số lượng đồ thị trong cơ sở dữ liệu. Mục tiêu hoàn thành trong vòng 6 tháng đầu kỳ nâng cấp hệ thống.
2. Chuẩn hóa cấu trúc ma trận liền kề chính tắc (CAM) trong lưu trữ: Đội ngũ kỹ sư phần mềm nên tích hợp định dạng biểu diễn CAM cho toàn bộ các tập dữ liệu đồ thị có gắn nhãn nhằm giảm thiểu 25% dung lượng lưu trữ dư thừa và tăng tốc độ so sánh chuỗi nhãn trong vòng 3 đến 6 tháng.
3. Tích hợp thuật toán FFSM cải tiến vào các bài toán phân tích cấu trúc hóa học và y sinh: Các viện nghiên cứu tin - sinh học và hóa tin học cần ứng dụng thuật toán để phát hiện các phân tử hoặc chuỗi tương tác protein phổ biến, đặt mục tiêu nâng cao 30% độ chính xác trong phân loại cấu trúc sinh học với chu kỳ thử nghiệm 12 tháng.
4. Ứng dụng độ đo trung gian và giải thuật phân chia trong quản trị mạng xã hội: Bộ phận phân tích dữ liệu viễn thông và mạng xã hội nên sử dụng thuật toán Girvan-Newman cải tiến để tự động phát hiện các cộng đồng ảo và nhận diện các nút cầu nối huyết mạch, tối ưu hóa năng lực giám sát an ninh thông tin trong lộ trình 9 tháng.

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

1. Học viên cao học và nghiên cứu sinh chuyên ngành Khoa học máy tính: Luận văn cung cấp toàn bộ nền tảng toán học chặt chẽ, các định lý chứng minh tính đa thức của bài toán đẳng cấu đồ thị và cấu trúc mã giả chi tiết phục vụ phát triển đề tài nghiên cứu chuyên sâu.
2. Kỹ sư dữ liệu và chuyên gia AI phát triển cơ sở dữ liệu đồ thị (Graph Database): Tài liệu là cẩm nang hữu ích để triển khai thuật toán CAM, kỹ thuật cây quyết định compact và các giải pháp lập chỉ mục dữ liệu đồ thị quy mô lớn nhằm tối ưu hóa hiệu năng hệ thống.
3. Nhà nghiên cứu trong lĩnh vực Tin - Sinh học (Bioinformatics) và Tin - Hóa học: Cung cấp phương pháp luận và công cụ khai phá tự động các mô típ mạng phân tử, hỗ trợ phân tích cấu trúc protein và phát hiện các cụm hóa chất có hoạt tính sinh học tương đồng.
4. Giảng viên và chuyên gia giảng dạy cấu trúc dữ liệu - giải thuật: Nguồn tư liệu học thuật phong phú về các giải thuật nâng cao trên đồ thị như Dijkstra mở rộng, phân cụm đồ thị phân cấp, thuật toán Girvan-Newman và các phương pháp khai phá mẫu thường xuyên đóng.

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

1. Bài toán đẳng cấu đồ thị (GI) trong luận văn được giải quyết với độ phức tạp tính toán như thế nào? Thuật toán kiểm tra tính đẳng cấu giữa hai đồ thị đơn vô hướng được chứng minh hoàn thành trong thời gian đa thức với giới hạn trên là 2n⁵ + 14n⁴ + 14n³ + 4n² bước tính toán, giúp loại bỏ hoàn toàn sự bùng nổ tổ hợp n! của phương pháp vét cạn.

2. Ma trận liền kề chính tắc (CAM) mang lại lợi ích gì cho việc khai phá đồ thị? CAM cung cấp một cách biểu diễn duy nhất theo thứ tự từ điển cực đại cho mọi đồ thị đẳng cấu. Nhờ đó, việc kiểm tra sự tương đồng hoặc trùng lặp giữa các đồ thị con được chuyển đổi thành so sánh chuỗi ký tự, cho phép áp dụng tìm kiếm nhị phân tối ưu.

3. Cấu trúc cây quyết định compact giúp tối ưu hóa bộ nhớ như thế nào? Cây quyết định compact sử dụng ma trận hoán vị R và các nhánh định hướng lại để liên kết các đồ thị con tự đẳng cấu về một đỉnh đại diện duy nhất, qua đó cắt giảm từ 40% đến 50% số lượng nút dư thừa trên cây.

4. Thuật toán FFSM khác biệt như thế nào so với các phương pháp khai phá đồ thị truyền thống? FFSM kết hợp biểu diễn CAM với hai phép toán N-Join và N-Extension, giúp chỉ sinh ra tối đa 1 đến 2 ma trận ứng viên từ mỗi phép kết nối, hạn chế tối đa việc tạo ra các đồ thị con không phổ biến và giảm hơn 35% thời gian tính toán.

5. Luận văn có thể ứng dụng trong những bài toán thực tế nào? Kết quả nghiên cứu áp dụng hiệu quả trong phân tích cấu trúc mạng xã hội, nhận diện cộng đồng học thuật, phát hiện mẫu phân tử hóa học, phân tích tương tác protein và tối ưu hóa công cụ tìm kiếm trên cơ sở dữ liệu đồ thị lớn.

Kết luận

1. Chứng minh và cài đặt thành công thuật toán kiểm tra đồ thị đẳng cấu đạt độ phức tạp thời gian đa thức 2n⁵ + 14n⁴ + 14n³ + 4n² bước.
2. Thiết kế hoàn chỉnh cấu trúc cây quyết định compact giúp giảm 40% đến 50% số nút dư thừa nhờ cơ chế nhánh tái định hướng.
3. Ứng dụng hiệu quả thuật toán FFSM và ma trận CAM trên tập dữ liệu lớn 10.000 đồ thị, tối ưu hóa tốc độ khai phá mẫu thường xuyên đóng hơn 35%.
4. Đề xuất lộ trình 2 giai đoạn (tiền xử lý ngoại tuyến O(n²) và phân tích trực tuyến) nhằm ứng dụng thực tế trong tin sinh học và mạng xã hội.
5. Tạo tiền đề vững chắc cho việc mở rộng thuật toán trên các mô hình đồ thị có hướng, đa đồ thị có trọng số và mạng đồ thị tri thức phân tán.

Đóng góp chính của luận văn là đã hóa giải rào cản tính toán của bài toán NP-đầy đủ trong khai phá đồ thị con, mở ra hướng ứng dụng mạnh mẽ cho các hệ thống dữ liệu lớn. Hãy áp dụng ngay các giải pháp ma trận chính tắc CAM và cấu trúc cây quyết định cô đọng để tối ưu hóa hiệu năng cho các dự án khai phá dữ liệu đồ thị của bạn ngay hôm nay.

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

CHƯƠNG 1: KHAI PHÁ ĐỒ THỊ Khai phá đồ thị (Graph Mining) là tập hợp các công cụ và kỹ thuật được sử dụng để (i) phân tích các thuộc tính của đồ thị trong thế giới thực, (ii) dự đoán cấu trúc và tính chất của đồ thị đã cho có thể ảnh hưởng đến một số ứng dụng và (iii) phát triển các mô hình có thể tạo ra biểu đồ thực tế phù hợp với các mô hình được tìm thấy trong các biểu đồ quan tâm trong thế giới thực. Chương này trình bày những khái niệm cơ sở về đồ thị, các dạng biểu diễn cấu trúc, dạng chính tắc của đồ thị và các kỹ thuật khai phá dữ liệu đồ thị. Cấu trúc đồ thị Một đồ thị (Graph) là một dạng biểu diễn hình ảnh của một tập các đỉnh (nút) đại diện cho các đối tượng dữ liệu (thực thể), trong đó các cặp đối tượng được kết nối bởi các cạnh (cung) thể hiện mối quan hệ giữa chúng [8]. Cho trước đồ thị G = (V, E), trong đó V là tập các đỉnh và E  V × V là tập các cạnh.

Đường đi có độ dài n đi từ nút v đến w là dãy các cạnh (v0, v1), (v1, v2), …, (vn-1, vn), trong đó v0 = v, vn = w và (vi, vi+1)  E. Đường đi đơn là đường đi không đi qua một đỉnh nào quá một lần. Hiển nhiên, đường đi ngắn nhất đi từ đỉnh s đến đỉnh t là đường đi đơn có độ dài (số cạnh) ít nhất trong số các đường đi giữa hai đỉnh. Hai cạnh được gọi là cạnh bội hay song song nếu chúng cùng tương ứng với một cặp đỉnh.

Một cạnh (v, w) của đồ thị G được gọi là khuyên (loop) nếu v = w. Đồ thị không có các cạnh bội được gọi là đơn đồ thị, ngược lại gọi là đa đồ thị. Hai đỉnh u và v trong đồ thị G được gọi là liền kề nếu (u, v)  E, hoặc (v, u)  E. Nếu e = (u, v) thì e gọi là cạnh liên thuộc với các đỉnh u và v.

Cạnh e cũng được gọi là cạnh nối các đỉnh u và v. Các đỉnh u và v gọi là các điểm đầu mút của cạnh e. Một đồ thị là vô hướng nếu E là tập các cạnh không có thứ tự, ngược lại là đồ thị có hướng. Đồ thị có trọng số nếu trên mỗi cạnh được gắn với một trọng số, ngược lại là đồ thị không trọng số, hay nói chính xác hơn là các cạnh của đồ thị đều có trọng số là 1.

LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Đa đồ thị vô hướng. Đa đồ thị vô hướng. e là khuyên cạnh song song c.

Không phải đơn đồ thị có e. Không phải đơn đồ thị có hướng do có các cặp cạnh hướng do có cạnh nối một nối cùng một cặp đỉnh. đỉnh với chính nó.1 Các đồ thị vô hướng và có hướng Trong luận văn này chúng ta chỉ những đơn đồ thị vô hướng, không trọng số, gọi tắt là đồ thị. Một đồ thị (vô hướng) được gọi là liên thông nếu luôn có đường đi đơn giữa mọi cặp đỉnh phân biệt của đồ thị.

Giữa mọi cặp đỉnh phân biệt của một đồ thị liên thông luôn có đường đi đơn [16]. Các đồ thị con liên thông rời nhau, được gọi là các thành phần liên thông của đồ thị đang xét. Như vậy, một đồ thị là liên thông khi và chỉ khi nó chỉ có một thành phần liên thông. Bậc của đỉnh v trong đồ thị G, ký hiệu deg(v), là số các cạnh liên thuộc với nó.

Đỉnh v được gọi là đỉnh treo nếu deg(v) = 1 và gọi là đỉnh cô lập nếu deg(v) = 0. Bậc của đỉnh là số các đỉnh liền kề với đỉnh đó. Tổng số bậc của các đỉnh trong đồ thị G bằng hai lần số cạnh [16]. LUAN VAN CHAT LUONG download : add [e-mail] 5 Tính chất 1.

Mọi đơn đồ thị n đỉnh (n ≥ 2) có tổng bậc của hai đỉnh tuỳ ý không nhỏ hơn n đều là đồ thị liên thông [16]. Nếu một đồ thị có đúng hai đỉnh bậc lẻ thì hai đỉnh này phải liên thông, tức là có một đường đi nối chúng [16]. Hợp của hai đơn đồ thị G1 = (V1, E1) và G2 = (V2, E2) là một đơn đồ thị G có tập các đỉnh là V1 V2 và tập các cạnh là E1  E2, ký hiệu là G = G1 G2. Hợp của hai đồ thị Định nghĩa 1.

Đơn đồ thị G’=(V, E’) được gọi là đồ thị bù của đơn đồ thị G = (V, E) nếu G và G’ không có cạnh chung nào (E  E’= ) và G  G’là đồ thị đầy đủ, đồ thị có các cạnh nối hai đỉnh bất kỳ. Dễ thấy rằng nếu G’ là bù của G thì G cũng là bù của G’. Khi đó ta nói hai đồ thị là bù nhau. G1’ là phần bù của G1 Định nghĩa 1.

Cho trước hai đồ thị G1 = (V1, E1) và G2 = (V2, E2), ta nói G1 là đồ thị con của G2 (G2 là đồ thị cha của G) khi và chỉ khi V1 ⊆ V2 và E1 ⊆ E2. Trường hợp V1 = V2 ta nói G1 là đồ thị con bao trùm G2. LUAN VAN CHAT LUONG download : add [e-mail] 6 Định nghĩa 1. Cho trước đồ thị G = (V, E), với mỗi S  V, đồ thị con cảm sinh (induced) bởi S trong đồ thị, ký hiệu là GS = (S, E  SS).

Như vậy, đồ thị G1 = (V1, E1) là đồ thị con cảm sinh của G2 = (V2, E2), nếu V1 ⊆ V2 , E1 ⊆ E2 và với mọi cạnh (u, v)  E1 thì u, v  V1. Đồ thị G được gọi là đầy đủ (clique) nếu mọi cặp đỉnh đều liên thuộc với nhau, nghĩa là  vi, vj  V, i  j thì (vi, vj)  E. Các dạng biểu diễn cấu trúc dữ liệu đồ thị Cách biểu diễn đồ thị trực quan nhất là hình vẽ, nhưng không thể lưu trữ trực tiếp các hình vẽ đồ thị trong máy tính. Có nhiều cách khác nhau để lưu trữ (biểu diễn) các đồ thị trong máy tính [8, 17].

Sử dụng cấu trúc dữ liệu (cách biểu diễn) nào thì tùy theo cấu trúc của đồ thị và thuật toán dùng để thao tác trên đồ thị đó. Trong lý thuyết, người ta thường sử dụng hai cấu trúc chính là danh sách và cấu trúc mảng (ma trận). Trong các ứng dụng cụ thể, cấu trúc tốt nhất có thể là kết hợp của cả hai. Người ta hay dùng các cấu trúc danh sách cho các đồ thị thưa (sparse graph), do chúng đòi hỏi ít bộ nhớ.

Trong khi đó, các cấu trúc ma trận cho phép truy nhập dữ liệu nhanh hơn, nhưng lại cần lượng bộ nhớ lớn nếu đồ thị có kích thước lớn [1, 4]. Danh sách liên thuộc Danh sách liên thuộc (Incidence list) - Mỗi đỉnh có một danh sách các cạnh nối với đỉnh đó. Các cạnh của đồ thị được có thể được lưu trong một danh sách riêng (có thể cài đặt bằng cấu trúc mảng (array) hoặc danh sách liên kết (linked list)), trong đó mỗi phần tử ghi thông tin về một cạnh, bao gồm: cặp đỉnh mà cạnh đó nối (cặp này sẽ có thứ tự nếu đồ thị có hướng), trọng số và các dữ liệu khác. Danh sách liên thuộc của mỗi đỉnh sẽ chiếu tới vị trí của các cạnh tương ứng tại danh sách cạnh này.

Cho đồ thị vô hướng LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Danh sách liên thuộc của đồ thị 1. Danh sách liền kề Danh sách liền kề (Adjacency List) - Mỗi đỉnh của đồ thị có một danh sách các đỉnh kề nó (nghĩa là có một cạnh nối từ đỉnh này đến mỗi đỉnh đó). Trong đồ thị vô hướng, cấu trúc này có thể gây trùng lặp.

Chẳng hạn nếu đỉnh 3 nằm trong danh sách của đỉnh 2 thì đỉnh 2 cũng phải có trong danh sách của đỉnh 3. Lập trình viên có thể chọn cách sử dụng phần không gian thừa, hoặc có thể liệt kê các quan hệ kề cạnh chỉ một lần. Biểu diễn dữ liệu này thuận lợi cho việc từ một đỉnh duy nhất tìm mọi đỉnh được nối với nó, do các đỉnh này đã được liệt kê tường minh. Danh sách liền kề.

Với mỗi đỉnh i của đồ thị chúng ta lưu trữ danh sách các đỉnh kề với nó, ký hiệu là List (i), List(i) = { j V: (i, j)  E hoặc (j, i)  E }, Với cách biểu diễn này, mỗi đỉnh i của đồ thị, tương ứng với một danh sách tất cả các đỉnh kề với nó và được ký hiệu là List(i). Để biểu diễn List(i), ta có thể dùng các kiểu dữ liệu kiểu tập hợp, mảng hoặc danh sách liên kết. Cho trước đồ thị vô hướng Hình 1. Đồ thị vô hướng LUAN VAN CHAT LUONG download : add [e-mail] 8 Danh sách liền kề của đồ thị trên theo cấu trúc danh sách liên kết là: Hình 1.

Biểu diễn danh sách liền kề của đồ thị hình 1.5 Đồ thị có trọng số (có các trọng số trên các cạnh), được gắn nhãn thường biểu diễn theo ma trận liền kề. Ma trận liên thuộc Ma trận liên thuộc (Incidence matrix) - Đồ thị được biểu diễn bằng một ma trận [bij] kích thước n × m, trong đó n là số đỉnh và m là số cạnh, trong đó bi,j = 1 nếu đỉnh vi liên thuộc (là một trong 2 đầu) với cạnh ej và bằng 0 trong các trường hợp khác. Cho đồ thị vô hướng G = (V, E), với v1, v2, ., vn là các đỉnh và e1, e2, ., em là các cạnh của G. Ma trận liên thuộc của G theo thứ tự trên của V và E là ma trận AG = {aij | i = 1.m}, trong đó aij là bằng 1 nếu cạnh ej nối với đỉnh vi và bằng 0 nếu cạnh ej không nối với đỉnh vi.

Ma trận liên thuộc theo thứ tự các đỉnh v1, v2, v3, v4, v5 (xếp theo cột) và các cạnh e1, e2, e3, e4, e5, e6 (xếp theo hàng) là: Hình 1. Ma trận liên thuộc của đồ thị vô hướng LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Ma trận liền kề Ma trận liền kề (adjacency matrix) một ma trận n × n, trong đó n là số đỉnh của đồ thị. Cấu trúc này tạo thuận lợi cho việc tìm các đồ thị con và để đảo các đồ thị.

Giả sử G = (V, E) là đồ thị có n đỉnh (|V | = n), V = {v1, v2, …, vn}. Ma trận liền kề (adjacency matrix) của đồ thị G ứng với thứ tự các đỉnh v1, v2,., vn là ma trận AG = {aij | i, j = 1.n}, trong đó ai,j = 1 nếu (vi, vj)  E, ngược lại ai,j = 0.