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 luanvanchat@agmail.com 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 luanvanchat@agmail.com 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 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. Đồ 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 luanvanchat@agmail.com 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.