Tài liệu 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

ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG PHẠM THỊ LIÊN 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 LUẬN VĂN THẠC SĨ: KHOA HỌC MÁY TÍNH Thái Nguyên - 2020 LỜI CAM ĐOAN Tôi xin cam đoan luận văn này do tự bản thân tôi tìm hiểu, nghiên cứu dưới sự hướng dẫn của PGS. TS. Đoàn Văn Ban. Các chương trình thực nghiệm do chính bản thân tôi lập trình, các kết quả là hoàn toàn trung thực. Các tài liệu tham khảo được trích dẫn và chú thích đầy đủ. TÁC GIẢ LUẬN VĂN Phạm Thị Liên LỜI CẢM ƠN Tôi xin bày tỏ lời cảm ơn chân thành tới tập thể các thầy cô giáo Viện công nghệ thông tin – Viện Hàn lâm Khoa học và Công nghệ Việt Nam, các thầy cô giáo Trường Đại học Công nghệ thông tin và truyền thông - Đại học Thái Nguyên đã dạy dỗ chúng tôi trong suốt quá trình học tập chương trình cao học tại trường. Đặc biệt tôi xin bày tỏ lòng biết ơn sâu sắc tới thầy giáo PGS.TS. Đoàn Văn Ban đã quan tâm, định hướng và đưa ra những góp ý, chỉnh sửa quý báu cho tôi trong quá trình làm luận văn tốt nghiệp. Cũng như các bạn bè, đồng nghiệp, gia đình và người thân đã quan tâm, giúp đỡ và chia sẻ với tôi trong suốt quá trình làm luận văn tốt nghiệp. Dù đã có nhiều cố gắng nhưng chắc chắn sẽ không tránh khỏi những thiếu sót vì vậy rất mong nhận được sự đóng góp ý kiến của các thầy, cô và các bạn để luận văn này được hoàn thiện hơn. Tôi xin chân thành cảm ơn! Thái Nguyên, tháng 08 năm 2020 Phạm Thị Liên MỤC LỤC Trang MỞ ĐẦU ............................................................................................................... 1 CHƯƠNG 1: KHAI PHÁ ĐỒ THỊ ....................................................................... 3 1.1. Cấu trúc đồ thị ............................................................................................ 3 1.2. Các dạng biểu diễn cấu trúc dữ liệu đồ thị ................................................ 6 1.2.1. Danh sách liên thuộc ........................................................................... 6 1.2.2. Danh sách liền kề ................................................................................ 7 1.2.3. Ma trận liên thuộc ............................................................................... 8 1.2.4. Ma trận liền kề .................................................................................... 9 1.2.5. Dạng chính tắc của đồ thị.................................................................. 10 1.3. Các kỹ thuật khai phá đồ thị .................................................................... 14 1.3.1. Phát hiện cấu trúc cộng đồng mạng xã hội ....................................... 15 1.3.2. Khai phá đồ thị con thường xuyên đóng ........................................... 19 1.4. Tổng kết chương 1 ................................................................................... 20 CHƯƠNG 2: BÀI TOÁN ĐỒ THỊ ĐẲNG CẤU VÀ KHAI PHÁ ĐỒ THỊ CON PHỔ BIẾN .......................................................................................................... 21 2.1. Bài toán đồ thị đẳng cấu........................................................................... 21 2.2. Thuật toán kiểm tra đồ thị đẳng cấu ........................................................ 24 2.2.1. Thuật toán Dijsktra tìm đường đi ngắn nhất ..................................... 24 2.2.2. 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 .................................................................................................... 24 2.2.3. Thuật toán xác ma trận dấu và dạng chính tắc của nó ...................... 25 2.2.4. 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 .............................................................. 26 2.2.5. Một số tính chất của đồ thị đẳng cấu ................................................ 26 2.3. Bài toán đẳng cấu đồ thị con SGI ............................................................ 30 2.3.1. Một số khái niệm cơ sở và ký hiệu ................................................... 31 2.3.2 Cây quyết định của đồ thị .................................................................. 32 2.3.3. Thuật toán xây dựng cây quyết định ................................................. 36 2.4. Khai phá đồ thị con phổ biến ................................................................... 40 2.4.1. Cây các đồ thị con dạng chính tắc .................................................... 40 2.4.2. Phép kết nối N-Join hai đồ thị .......................................................... 41 2.4.3. Phép N-Extension ............................................................................. 43 2.5. Thuật toán FFSM cho khai phá đồ thị con phổ biến trong CSDL đồ thị 44 2.6. Kết luận chương 2 .................................................................................... 47 CHƯƠNG 3 THỬ NGHIỆM VÀ ĐÁNH GIÁ .................................................. 48 3.1. Dữ liệu và môi trường thử nghiệm .......................................................... 48 3.1.1. Bộ dữ liệu thử nghiệm ...................................................................... 48 3.1.2. Môi trường thử nghiệm ..................................................................... 49 3.2. Cài đặt và thử nghiệm thuật toán tìm kiếm tra đồ thị đẳng cấu ............... 50 3.2.1. Mô tả yêu cầu bài toán kiếm tra đồ thị đẳng cấu .............................. 50 3.2.2. Kết quả thử nghiệm ........................................................................... 50 3.3. Thử nghiệm thuật toán FFSM cho khai phá đồ thị con phổ biến ............ 53 3.3.1. Mô tả yêu cầu bài toán khai phá đồ thị con phổ biến ....................... 53 3.3.2. Phân tích đánh giá kết quả ................................................................ 53 3.4. Kết luận chương 3 .................................................................................... 55 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN .......................................................... 56 TÀI LIỆU THAM KHẢO .................................................................................. 57 THUẬT NGỮ VÀ TỪ VIẾT TẮT Thuật ngữ Diễn giải CAM Canonical Adjacency Matrix Community Social Structure Cấu trúc cộng đồng mạng xã hội CSDL Cơ sở dữ liệu FFSM FastFrequent Subgraph Mining GI Graph isomorphism - Đẳng cấu đồ thị Graph isomorphism problem Bài toán đồ thị đẳng cấu SFI Viện Santa Fe SGI SubGraph Isomorphism – Đẳng cấu đồ thị con DANH MỤC CÁC HÌNH VẼ Hình 1.1 Các đồ thị vô hướng và có hướng .......................................................... 4 Hình 1.2. Hợp của hai đồ thị ................................................................................. 5 Hình 1.3. G1’ là phần bù của G1............................................................................ 5 Hình 1.4. Danh sách liên thuộc của đồ thị ............................................................ 7 Hình 1.5. Đồ thị vô hướng .................................................................................... 7 Hình 1.6. Biểu diễn danh sách liền kề của đồ thị hình 1.5 ................................... 8 Hình 1.7. Ma trận liên thuộc của đồ thị vô hướng ................................................ 8 Hình 1.8. Ma trận liền kề của đồ thị trong ví dụ 1.6............................................. 9 Hình 1.9. Các đồ thị con cực đại ......................................................................... 11 Hình 1.10. Mạng lưới cộng tác của các nhà khoa học làm việc tại SFI [1]........ 17 Hình 2.1. Các phần tử hàng - cột của ma trận liền kề......................................... 33 Hình 2.2. Cây quyết định để phân lớp các ma trận liền kề của G ...................... 34 Hình 2.3. Cấu trúc từ điển và các chỉ mục cho cây quyết định .......................... 35 Hình 2.4. Cây quyết định của G và G’................................................................ 35 Hình 2.5. Cây quyết định compact để phân lớp các ma trận liền kề {A, B, …, F} và {A’, B’, …, F’} của đồ thị G và G’ ................................................................. 37 Hình 2.6. Hai phép toán N-Join va N-Extension ................................................ 43 Hình 3.1. Mô tả cấu trúc bộ dữ liệu thử nghiệm với kho gồm 2 đồ thị .............. 48 Hình 3.2. Bộ dữ liệu đơn giản thử nghiệm thuật toán kiểm tra 2 đồ thị đẳng cấu ............................................................................................................................. 51 Hình 3.3. Kết quả đồ thị đẳng cấu với bộ dữ liệu đơn giản ................................ 51 Hình 3.4. Kết quả đồ thị đẳng cấu với đồ thị target có kích thước lớn .............. 52 Hình 3.5. Ví dụ về không tồn tại đẳng cấu đồ thị con ........................................ 52 Hình 3.6. Thời gian chạy thuật toán FFSM trên bộ dữ liệu 10000 đồ thị .......... 53 Hình 3.7. Số đồ thị con tìm được ứng với các độ hộ trợ tối thiểu khác nhau trên bộ dữ liệu 10.000 đồ thị ...................................................................................... 54 DANH MỤC CÁC BẢNG Bảng 3.1. Thông tin phần cứng được sử dụng thử nghiệm ...................................... 49 Bảng 3.2. Tổng hợp kết quả chạy thuật toán FFSM trên 2 bộ dữ liệu ..................... 54 1 MỞ ĐẦU 1. Lý do chọn đề tài Khai phá dữ liệu là lĩnh vực đang được nhiều người tập trung nghiên cứu và phát triển nhiều ứng dụng phổ biến. Trong đó, bài toán khai phá đồ thị con thường xuyên đã và đang thu hút được nhiều sự quan tâm nghiên cứu bởi phạm vi ứng dụng quan trọng trong nhiều lĩnh vực khác nhau như trong tin-sinh (bioinformatics), tinhóa (cheminformatics) khai thác đăng nhập trang web, lập chỉ mục video, hay lập chỉ mục cơ sở dữ liệu hiệu quả, ... Vấn đề khai phá mẫu thường xuyên là từ một tập dữ liệu các đối tượng với một ngưỡng độ hỗ trợ tối thiểu minsup. Dữ liệu có thể rất đa dạng từ dữ liệu nhị phân, dữ liệu số nguyên, số thực hoặc các dữ liệu có cấu trúc phức tạp hơn như cấu trúc cây, đồ thị, … Cho đến nay vẫn chưa có lời giải hiệu quả cho bài toán này do độ phức tạp của bài toán là rất lớn khi đồ thị có số đỉnh lớn và mật độ các cạnh dày. Tuy nhiên, sự phức tạp của những vấn đề này sẽ giảm khi cơ sở dữ liệu (CSDL) đồ thị có thêm thông tin về các đỉnh và các cạnh đã được gán nhãn. Có thể sử dụng các nhãn để hạn chế các đỉnh có thể tạo thành các cặp trong quá trình kiểm tra sự đẳng cấu của đồ thị con. Và đó chính là lý do em lựa chọn đề 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” để nghiên cứu làm luận văn thạc sĩ của mình. 2. Mục đích nghiên cứu Nghiên cứu thuật toán đẳng cấu đồ thị và thuật toán phát hiện đồ thị con phổ biến trong CSDL đồ thị. 3. Đối tượng nghiên cứu - Bài toán đồ thị con đẳng cấu - Khai phá dữ liệu đồ thị - Bài toán khai phá đồ thị con phổ biến trong CSDL đồ thị - Thuật toán FFSM - Thuật toán SGI Decision Tree. 2 4. Phạm vi nghiên cứu + Lý thuyết: - Tìm hiểu lý thuyết đồ thị và các phương pháp khai phá dữ liệu đồ thị. - Nghiên cứu các thuật toán tìm đồ thị con đẳng cấu và các thuật toán khai phá đồ thị con phổ biến. + Thực nghiệm: - Xây dựng chương trình thực nghiệm thuật toán. - Áp dụng chương trình trên một số bộ cơ sở dữ liệu trong khai phá dữ liệu đồ thị. 5. Ý nghĩa khoa học Đây là một hướng nghiên cứu lý thuyết, xây dựng các thuật toán tìm kiếm đồ thị con đẳng cấu và đồ thị con phổ biến và kiểm thử trên các bộ dữ liệu về đồ thị. 6. Phương pháp nghiên cứu - Phương pháp nghiên cứu lý thuyết: Sưu tập các tài liệu có liên quan đến đề tài, nghiên cứu để hiểu sâu các nội dung vấn đề cần nghiên cứu. - Phương pháp nghiên cứu thực nghiệm: Cài đặt chương trình thử nghiệm phương pháp tìm kiếm đồ thị con đẳng cấu và thuật toán FFSM để liệt kê các đồ thị con phổ biến trên các bộ dữ liệu và đánh giá hiệu suất của phương pháp. - Phương pháp trao đổi khoa học: Trao đổi nội dung nghiên cứu với giáo viên hướng dẫn, với các đồng nghiệp để đề xuất và giải quyết các nội dung luận văn đề ra. 7. Cấu trúc đề tài Luận văn được chia thành các phần chính như sau: Chương 1: Khai phá dữ liệu đồ thị Chương 2: Đồ thị đẳng cấu và đồ thị con phổ biến Chương 3: Thử nghiệm thuật toán tìm đồ thị con phổ biến Kết luận và hướng phát triển. 3 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ị. 1.1. 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]. Định nghĩa 1.1. 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. 4 Ví dụ 1.1. 2 2 e1 e 1 e3 3 1 3 e4 e2 4 a. Đa đồ thị vô hướng. e4 và e5 là các cạnh song song c. Đơn đồ thị có hướng 4 e5 b. Đa đồ thị vô hướng. e là khuyên d. Không phải đơn đồ thị có hướng do có các cặp cạnh nối cùng một cặp đỉnh. e. Không phải đơn đồ thị có hướng do có cạnh nối một đỉnh với chính nó. Hình 1.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ị. Định nghĩa 1.2. 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ị. Tính chất 1.1. 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. Định nghĩa 1.3. 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ính chất 1.2. Tổng số bậc của các đỉnh trong đồ thị G bằng hai lần số cạnh [16]. 5 Tính chất 1.3. 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]. Tính chất 1.4. 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]. Định nghĩa 1.4. 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. Ví dụ 1.2. Hình 1.2. Hợp của hai đồ thị Định nghĩa 1.5. Đơ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. Ví dụ 1.3. Hình 1.3. G1’ là phần bù của G1 Định nghĩa 1.6. 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. 6 Định nghĩa 1.7. 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. Định nghĩa 1.8. Đồ 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. 1.2. 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]. 1.2.1. 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. Ví dụ 1.4. Cho đồ thị vô hướng 7 Hình 1.4. Danh sách liên thuộc của đồ thị 1.2.2. 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. Định nghĩa 1.9. 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. Ví dụ 1.5. Cho trước đồ thị vô hướng Hình 1.5. Đồ thị vô hướng 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.6. 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ề. 1.2.3. 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. Định nghĩa 1.10. 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..n, j = 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. Ví dụ 1.6. 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.7. Ma trận liên thuộc của đồ thị vô hướng 9 1.2.4. 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ị. Định nghĩa 1.11. 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. Từ định nghĩa suy ra ma trận liền kề biểu diễn đồ thị vô hướng là ma trận đối xứng qua đường chéo chính, nghĩa là aij = aji, trong khi ma trận liền kề của một đồ thị có hướng không có tính đối xứng. Hình 1.8. Ma trận liền kề của đồ thị trong ví dụ 1.6 Cho trước một đồ thị có tập đỉnh V = {v1, v2, …, vn} thì sẽ có n! ma trận liền kề tương ứng, bởi vì ứng mỗi cách sắp xếp các đỉnh (một hoán vị của V) thì ta có một ma trận liền kề. Cho trước đồ thị G, ta ký hiệu AM(G) là tập các ma trận liền kề của G. Đối với đồ thị không có trọng số chúng ta có tính chất sau: Tính chất 1.5. Cho G là một đồ thị (vô hướng không có trọng số) với ma trận liền kề A theo thứ tự các đỉnh v1, v2, ..., vn. Khi đó số các đường đi khác nhau độ dài r từ vi tới vj trong đó r là một số nguyên dương, bằng giá trị của phần tử dòng i cột j của ma trận Ar [14]. Định nghĩa 1.12. Giả sử A là ma trận liền kề của một đồ thị. Ta ký hiệu diag[A] là vector biểu diễn tất cả các phần tử trên đường chéo chính của A. Tương tự, upper[A] là vector biểu diễn tất cả các phần tử phần tam giác trên của A (không kể các phần tử trên đường chéo chính). 10 1.2.5. Dạng chính tắc của đồ thị Theo các định nghĩa về cách biểu diễn nêu trên, thì một đồ thị có thể biểu diễn (lưu trữ) theo khá nhiều danh sách và ma trận khác nhau, điều này gây ra nhiều khó khăn trong việc tính toán và xử lý đồ thị, như xử lý bài toán tìm các đồ thị con đẳng cấu, đồ thị con xuất hiện thường xuyên, đồ thị (mẫu) thường xuyên đóng, cực đại, ... Ví dụ, cho trước một đồ thị có tập đỉnh |V| = n thì sẽ có n! ma trận liền kề tương ứng, bởi vì ứng mỗi cách sắp xếp các đỉnh (một hoán vị của V) thì ta có một ma trận liền kề. Một trong các vấn đề quan trọng của khai phá đồ thị là bài toán đẳng cấu đồ thị: cho trước hai đồ thị P, Q, cần kiểm tra xem P có đẳng cấu với Q hay không. Chúng ta giải quyết vấn đề này bằng cách chuyển mỗi đồ thị về dạng biểu diễn chính tắc (duy nhất) của nó rồi sau đó so sánh hai dạng chính tắc của chúng [1, 4, 5, 10]. Dạng chính tắc của đồ thị là dạng biểu diễn của đồ thị sao cho nếu hai đồ thị đẳng cấu với nhau thì dạng chính tắc của chúng là như nhau và ngược lại [1]. Để tiện cho việc biểu diễn đồ thị một cách thống nhất, chúng ta định nghĩa lại ma trận liền kề theo nhãn (tên) của các đỉnh như sau. Định nghĩa 1.13. Giả sử G = (V, E) là đồ thị liên thông, vô hướng có n đỉnh (|V| = n). Ma trận liền kề (adjacency matrix) của G là ma trận A = {aij | i, j = 1..n} với l(vi) aij = Nếu i = j //Nhãn (tên) của đỉnh trong G l(vi,vj) Nếu i  j 0 Nếu giữa vi và vj không có cạnh nối với nhau. //Nhãn (tên) của cạnh nối vi với vj. Từ định nghĩa suy ra ma trận liền kề là ma trận đối xứng qua đường chéo chính. Trên đường chéo chính của ma trận liền kề là nhãn của các đỉnh, các phần tử còn lại là nhãn của các cạnh, nếu có. Định nghĩa 1.14. Cho trước ma trận liền kề A = {ai j | i, j = 1.. n} và alk là cạnh cuối của A (alk  0, với l < k ở bên phải nhất trên hàng cuối cùng trong A), ma trận con cực đại (maximal submatrix) của A là ma trận B = { bij | i, j = 1.. p}, p ≤ n, được định nghĩa như sau: (a) Nếu hàng cuối của A có hai cạnh (hai giá trị khác 0) thì 11 +p=n + bij = bi j Nếu (0 < i, j ≤ p)  (i  l  j  k)  (i  k  j  l) 0 Ngược lại (b) Nếu hàng cuối của A chỉ có một cạnh (một giá trị khác 0) thì +p=n–1 + bij = ai j với 0 < i, j ≤ p Nhận xét: Ma trận con cực đại của ma trận chính A là một ma trận thu được từ A sau khi loại bỏ đi một cạnh cuối theo cách hoán vị của tập đỉnh. Trường hợp (a) có hai cạnh thì cạnh cuối được bỏ đi (vị trí đó được thay bằng 0), còn trong trường hợp (b) chỉ có một cạnh cuối thì đỉnh cuối (đỉnh cuối cùng năm trên đường chéo chính) cũng được loại bỏ, nghĩa là bỏ đi hàng, cột cuối của ma trận. Ví dụ 1.8. Cho trước hai đồ thị G1, G2 có 2 ma trận liền kề tương ứng là A1 và A2. Xét các ma trận con cực đại của hai ma trận liền kề A1, A2 của G1, G2 Hình 1.9. Các đồ thị con cực đại Hàng cuối của ma trận A1 có hai cạnh x, z và z là cạnh cuối, nên ma trận con cực đại của nó là ma trận (a). Ma trận A2 ở hàng cuối chỉ có một cạnh y, do vậy bỏ đi hàng cuối, cột cuối ta thu được ma trận (b). Ma trận (c) là ma trận con cực đại của 12 ma trận (a), ma trận (d) là ma trận con cực đại của ma trận (b) và (c), ma trận (e) là ma trận con cực đại của ma trận (d). Định nghĩa 1.15. Cho trước một ma trận liền kề A của đồ thị G = (V, E) có |V| = n đỉnh, ta định nghĩa mã (code) của A, ký hiệu code(A), là dãy các phần tử của tam giác dưới của A. code(A) = a11a21a22 ... an1an2 ... ann−1ann Cạnh ứng với nhãn đầu tiên trong mã của ma trận liền kề được gọi là cạnh đầu tiên và cạnh ứng với nhãn ở cuối của mã là cạnh cuối cùng. Nhận xét: Vì ma trận liền kề là ma trận đối xứng nên dựa vào code(A) ta dễ dàng xác định được cả ma trận A. Ta sử dụng thứ tự từ điển chính tắc (theo mã ký tự) trên các dãy các nhãn để định nghĩa quan hệ thứ tự toàn phần của hai mã p và q bất kỳ. Định nghĩa 1.16. Cho trước đồ thị G, dạng chính tắc của G là đồ thị có mã cực đại của tất cả các mã các ma trận liền kề có thể. Ma trận liền kề có mã là chính tắc (cực đại) được gọi là ma trận liền kề chính tắc CAM (Canonical Adjacency Matrix) của G, ký hiệu là CAM(G). CAM(G) = { A | A  AM(G)   B  AM(G)  code(A) ≥ code(B)} Ví dụ 1.9. Xét các của hai ma trận liền kề ở ví dụ 1.8 code(A1) = “axb0ycxy0b” và code(A2) = “axbxzb0y0c” Áp dụng thứ tự từ điển ta có code(A2) ≥ code(A1). Bằng cách xây dựng tất cả các ma trận liền kề theo các hoán vị khác nhau của các đỉnh của đồ thị G và so sánh mã của chúng, chúng ta thấy CAM(G) = A2, vì code(A2) là mã cực đại theo định nghĩa. Từ những định nghĩa nêu trên, chúng ta có một số tính chất quan trọng được sử dụng để khai phá tập đồ thị con phổ biến [1], [3], [9]. Tính chất 1.6. Nếu A là ma trận liền kề của đồ thị liên thông G và B là ma trận con cực đại của A thì code(A) ≥ code(B). Chứng minh. Dựa vào định nghĩa của ma trận con cực đại để chứng minh.