Luận vă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
ĐẠ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
1.1. Cấu trúc đồ thị............................................................................................3
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.4. Tổng kết chương 1 ...................................................................................20
PHỔ BIẾN ..........................................................................................................21
2.1. Bài toán đồ thị đẳng cấu...........................................................................21
thị kết đôi ....................................................................................................24
2.3. Bài toán đẳng cấu đồ thị con SGI ............................................................30
2.3.2 Cây quyết định của đồ thị ..................................................................32
2.6. Kết luận chương 2....................................................................................47
3.1.1. Bộ dữ liệu thử nghiệm ......................................................................48
3.2.2. Kết quả thử nghiệm...........................................................................50
3.3.2. Phân tích đánh giá kết quả ................................................................53
THUẬT NGỮ VÀ TỪ VIẾT TẮT
Diễn giải
Thuật ngữ
CAM
Canonical Adjacency Matrix
Cấu trúc cộng đồng mạng xã hội
Cơ sở dữ liệu
Community Social Structure
CSDL
FFSM
FastFrequent Subgraph Mining
Graph isomorphism - Đẳng cấu đồ thị
Bài toán đồ thị đẳng cấu
Viện Santa Fe
GI
Graph isomorphism problem
SFI
SGI
SubGraph Isomorphism – Đẳng cấu đồ
thị con
DANH MỤC CÁC HÌNH VẼ
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.9. Các đồ thị con cực đại.........................................................................11
Hình 2.4. Cây quyết định của G và G’................................................................35
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), tin-
hó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
4
e1
e
1
1
3
e3
e4
e2
e5
a. Đa đồ thị vô hướng. e4 và e5 là các
cạnh song song
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 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ó.
e. Không phải đơn đồ thị có
c. Đơn đồ thị có hướng
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 SS).
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)
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
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
đỉ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)
Nếu i = j
//Nhãn (tên) của đỉnh trong G
l(vi,vj) Nếu i j
//Nhãn (tên) của cạnh nối vi với vj.
aij =
0
Nếu giữa vi và vj không có cạnh nối với nhau.
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
bi j Nếu (0 < i, j ≤ p) (i l j k) (i k j l)
+ bij =
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−1 nn
a
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.
Tải về để xem bản đầy đủ
66 trang
12740
Free
Bạn đang xem 20 trang mẫu của tài liệu "Luận vă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", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- luan_van_bai_toan_do_thi_con_dang_cau_trong_khai_pha_du_lieu.pdf
