Chương 1 là cơ sở lý thuyết làm tiền đề cho chương 2 và chương 3. Một số định nghĩa và ký hiệu ân này được tham khảo trong tài liệu [1], [3], [5] 1. Định nghĩa đồ thị Dé thị là một cấu trúc rời rạc bao gồm các đình và các cạnh (vô hướng hoặc có hướng) nối các đỉnh đó, các loại đồ thị khác nhau được phân biệt bởi đặc tính và số cạnh nối hai đình nào đồ của đỗ thi. Giả sử V là tập hữu hạn, không rỗng các phẩn tử nào đó.
Bộ G = (V,E) được gọi là đồ thị hữu hạn. Mỗi phân tử của V gọi là một đỉnh và mỗi phần tử 0= Œ y) của E được gọi là một cạnh của đỗ thị G = (V, E) _Xêt một cạnh u của E. Khi đó, tồn tại hai đính x, y của V sao cho u = (%, ÿ). ta nói rằng x nối vớiy hoặc x vày phụ thuộc u.
- _ Nếu cạnhu = (%, y) mà x và y là 2 đỉnh phân biệt thì ta nôi x, y là 2 đỉnh kề nhau. -_ Nếu u = ( y) mà x, y là cặp đình cô phân biệt thứ tự hay có hướng từ x đến y thì u là một cung, khi đó x là gốc và y là ngọn hoặc x là đỉnh ra, y là đình vào Vidu Li Biểu điễn một mạng máy tính bằng một mô hình đỏ thị trong đô mỗi máy tính là một đỉnh, giữa các máy tính được nối với nhau bằng đây truyền, chúng tương ứng là các cạnh của đồ thị. Xét mô hình mạng máy tính sau.1: Mé hình mạng máy tính thông thường Trong đô các máy tính a, b, c, đ là các đỉnh, giữa hai máy được nối trực. tiếp với nhau tương ứng với một cặp đỉnh kê nhau.1 Đơn đồ thị vô hướng G = (V, E) bao gồm V là các tập đỉnh và E là các tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi lã các cạnh.2 Da dé thi vô hướng G = (V, E) bao gồm V là tập các đỉnh, và E là họ các cặp không có thứ tự gồm hai phin tử khác nhau của V gọi là các cạnh.
Hai cạnh e: và e: được gọi là cạnh lặp nều chúng cùng tương ứng với một cặp đỉnh.3 Đơn đồ thị có hướng G = (V, E) bao gồm V là các tập đỉnh và E là các cặp có thứ tự gồm hai phin tir khác nhau của V gọi là các cung. Trong mạng máy tính có thễ có đa kênh thoại một chiều, ta cần sử dụng. đến một đa đồ thị. Từ đó, ta có khái niệm đa đô thị có hướng như sau: Định nghĩa 1.4 Đa đỗ thị có hướngG = (V, E) bao gồmV là các tập đỉnh và E là họ các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung.
Hai cung ex, e; tương ứng cùng với một cặp đỉnh được goi là cung lặp. Biểu diễn đồ thị trên máy tính ‘Dé lưu trữ đỗ thị và thực hiện các thuật toán khác nhau với dé thị trên máy tính cần phải tìm những cấu trúc đữ liệu thích hợp để mô tả. cấu trúc dữ liệu nào để biểu điễn đồ thị có tác động rất lớn đến hiệu quả của thuật toán. Trong phần này, em xin trình bày một số phương pháp cơ bản.
được sử đụng để biểu điễn đô thị trên máy tính. Biểu diễn đồ thị bằng ma trận. ‘a ma tran trong so Giả sử G = (V, E) là một đơn đồ thị với n đỉnh. Ma trận kề không- một cap nxnA = [a3] trong đó: ay = O néu khéng cé canh néi đỉnh ¡ với đỉnh j 2; = 1 nếu có cạnh nối đỉnh ¡ với đình j Vidu 1.2, wow vs Vy */01/1|0/1 QO Blifololiia LY?) 011/10/1 @) [> 510414110 () Hinh 1.2: Đồ thị vô hướng G được biểu diễn thông qua ma trận kè Cách biểu diễn bằng ma trận kẻ có thê sử đụng cho cả đồ thị có hướng và vô hướng.
Nếu đồ thị là cô trọng số thì các phần tử ma trận kề có thể nhận. giá trị là trọng số của cung. Cö thể lựa chọn hai gia tri 0 và 1 đễ phân biệt sự khác nhau giữa cặp đỉnh cô cạnh nối và cặp đỉnh không cô cạnh nói. Trong thực tế cài đặt, tùy.
thuộc vào thuật toán mà có thê sử dụng các bộ giá trị khác vẫn đảm bão sự phân biệt * Ưu điểm: Tốc độ truy xuất thông tin về cạnh cao. * Nhược điểm: - Đề thị thưa có hiệu suất sử đụng tài nguyên thấp. - Tình huống cập nhật đỗ thị bằng thao tác thay đổi kích thước tập đình tất phức tạp: Buộc phải khai báo một ma trận với kích thước mới và hủy bỏ "ma trận đã sử dụng ban đầu. Biểu diễn đồ thị bằng ma trận liên thuộc.
Một cách thường đùng nữa để biểu diễn đồ thị là đùng ma trận liên thuộc. Giả sử G = (7; Z) là một đồ thị vô hướng với các đỉnh vị, vo, .ụ và các cạnh là eụ, e,. Khi đó, ma trậnliên thuộc M = [m,] kích thước n x m trong đó: my = 0 nếu cạnhe, không nói với đỉnh vị, my = nếu cạnh e; nối với đỉnh vy, Vidu 13; Giả sử e;= {V\, V2; €2 {V,, VI); €= {Vụ VỤ: 8= {Vi VỚ: Sẽ {w .3: Đồ thị vô hướng G duoc biéu diễn thông qua ma trận liên thuộc “Khi đó ma trận liên thuộc tương ứng sẽ là | & & & & & wj1/1|1|0|0|0)0 wị0/0|1|0|0|1|1 Cö thể lựa chọn giá trị 0 và 1 đề phân biệt sự khác nhau giữa đỉnh và cạnh. Trong thực tế cài đặt, tùy thuộc vào thuật toán mà có thê sử đụng các bộ.
giá trị khác dam bão sự phân biệt. c Biểu dién đồ thị ing danh sách kê Biểu diễn đồ thị bởi danh sách kề là cách liệt kê tất cả các cạnh của đỏ thi (Gv, vals (Wi, V3): (Vì, V: (Vi VÒ: (Và VỤ): (V5 VẬ) (VS V9): Hoặc là danh sách này chỉ rõ các đình nối với mỗi đỉnh của đỏ thị. Vidu 14) Danh sách đình ke Dinh | Dinh nor Was we Me Wy [WWw W [NV we JWw Người ta đùng danh sách liên kết đơn thuận hoặc nghịch để biểu điễn chúng dưới đạng định kề hoặc cạnh kề. Đối với đồ thị vô hướng, khi cài đặt nên lưu trữ đanh sách theo qui cách: các đính trong danh sách sẽ có số thứ tự lớn hơn đỉnh tương ứng với đanh sách đó.
Qui cách này sẽ giúp đảm bảo việt số ô nhớ đùng đề lưu trữ đúng bằng số cạnh của dé thị mà không mất mát thông tin. Đỗ thị bà Để thị bù của đồ thị G=(Ƒ,E) là đồ thị (VE),tong 46 DIE €V. Véi một tập con SC V, ta định nghĩa đỗ thị con sinh bởi S 1a dé thi G(S)=(S,E SxS). Trong sé cia tap S là giá trị W@)=w LL M6tsé dink nghia vé Clique thị, một Clique trong đỏ thị vô hướng G là tập các định V (V la tập con của tập các đình của G) thỏa mãn điều kiện: Với mỗi cặp đình thuộc V luôn tôn tại một cạnh của G nối chúng.
Do vậy một đỗ thị con được tạo ra từ V sẽ là một 46 thị đây đủ. Kích thước của một clique là số. Dé thi day da thi day đủ n đỉnh, kí hiệu là Ko, là là đỗ thi đơn vô hướng mà giữa ai đỉnh bất kỳ nó luôn có cạnh nối. Đề thị Kạ có tất cả n(n-1)/2 cạnh.
Nó là đỏ thị đơn có nhiều cạnh nhất, đồng thời là đô thị chính quy bậc n-1 ‘Vi dy 1.5: Một đồ thị đây đủ K› (7 định). Nếu đây là một đỏ thị con thì tập đình của nó sẽ tạo niên một clique kích thước 7.4: Đồ thị đầy đủ Kr 'Bài toán xác định có tôn tại hay không một clique với một kích thước cho trước trong một đồ thị (Bài toán clique) là một bài toán NP - đây đủ. Clique cực đại (maximal clique) Clique cực đại của G là clique không thuộc bất cứ một clique nào khác rộng hơn nó, nói cách khác là không thễ thêm bắt cứ đình nào vào một clique cực đại để tạo ra clique cô số đỉnh lớn hơn. Chque lớn nhất (maximum clique) Clique lớn nhất của G là clique có số đỉnh lớn nhất của G.
Một clique lớn nhất đồng thời là một clique cực đại, nhưng điều ngược lại chưa chắc đã đúng. 10 ‘Complete graph Clique Hinh 1.5: Dé thi G, phan bù đồ thị, đồ thị đầy đủ và Clique d. Chỉ số clique Chỉ số clique của đô thị G, ký hiệu là w(G), là số đỉnh của clique lớn. Ký hiệu |S| là lực lượng của tập S, ta có: w(G)= ma [l|:S là một chạue trong GÌ.
Bài toán Maximum Clique là bài toán tim Clique có số đỉnh lớn nhất. Bài toán Maximum Weight Clique là bài toán xác định clique có trọng số lớn nhất, được ký hiệu là w(G, w)va được xác định bi: w(Giw) =max {WW (S):5 12 mbt clique trong GÌ, u 1. Tậpđộc lập "Một tập độc lập là tập con củaV thỏa mãn hai định bất cạnh nói. Chỉ số ôn định của đồ thị G (ký hiệu là œ(G)), là số đỉnh của tập con.
độc lập lớn nhất. (G)=max |S|-Š là một ập độc lập rongG} Một tập phủ đỉnh là tập sao cho tất cả các cạnh của đồ thị cô ít nhất một đinh trong tập đó. Bài toán tìm phủ đình nhỏ nhất cho tập phủ đính có số phần tử nhỏ nhất. Dé thấy 5 14 mét clique cia G khi và chỉ khi Š là một tập con độc lập cia Gva V\S là một tập phủ đỉnh của G.
Hay w(G)=w(G)và ngược lại. Nói cách khác, các bài toán clique lớn nhất trong đỏ thị G và tập độc lập lớn nhất trong đỗthị bù G là tương đương. Bài toán Clique cực đại [4] "Một đơn hình chuẩn của đỏ thị G là một tập các véc tơ trong không gian Euclidean Í “, ký hiệu là A=lx(x.x,)€L “Ix, >0 Vie Dy, =lÌ. Khi đó, với mỗi tập con Š V, ký hiệu tập đại diện của À theo S là: Á,=[x€AIx =0 nấu £S} Cụ thể x*(X.x,=1/|S| nÕu ‡eS;x, =0 c8nj!2 được gọi là véc tơ đặc tính của tập S.
Tương tự, trong trường hợp đỏ thị có vec to trong số đỉnh we ˆ °, véc tơ đặc tính trọng số của tập đỉnh S được định.x,) trong đô x =w,/w(S) nếu ieS và bằng 0 12 trong các trường hợp còn lại. Xét hàm toàn phương #(x)=x” 4„x va goi x" là điểm lớn nhất toàn cục của g(x)trong A.