Chương 1 Các kiến thức cơ bản Trước khi đi đến vấn đề chính của luận văn thì chúng tôi sẽ trình bày các kiến thức cơ bản của Đồ thị và giới thiệu về bài toán Clique. Và đồng thời sẽ trình bày về độ phức tạp tính toán của thuật toán. Các khái niệm này đươc tham khảo tại một số tài liệu [1],[7].1 Đồ thị, các khái niệm cơ bản 1.1 Khái niệm đồ thị Định nghĩa 1. Đồ thị vô hướng hoặc đồ thị G là một cặp không có thứ tự G := (V, E), trong đó • V , tập các đỉnh.
• E, tập các cặp đỉnh (không thứ tự), được gọi là cạnh. Hai đỉnh thuộc một cạnh được gọi là các đầu mút của cạnh đó. Cạnh của đồ thị mà có 2 điểm đầu mút trùng nhau thì được gọi là khuyên. Đồ thị vô hướng có thể có một hoặc nhiều khuyên.
Các cạnh mà có cùng cặp đầu mút thì được gọi là các cạnh song song. Đơn đồ thị vô hướng là một đồ thị không có khuyên và không có cặp cạnh nào song song.1: Đơn đồ thị vô hướng Định nghĩa 1. Đa đồ thị vô hướng là một đồ thị vô hướng mà không phải là đơn đồ thị.2: Đa đồ thị vô hướng Trong luận văn này, chúng tôi chỉ đề cập đến đơn đồ thị vô hướng. Nhiều khi có thể viết gọn là "đồ thị G", kí hiệu V (G), E(G) lần lượt là tập đỉnh, tập cạnh của đồ thị G.2 Đồ thị con, đồ thị cảm sinh từ tập đỉnh Định nghĩa 1.
Cho đơn đồ thị vô hướng G = (V, E). Khi đó G′ = (V ′ , E ′ ) được gọi là đồ thị con của G nếu V ′ ⊂ V và E ′ ⊂ E. Đồ thị con G′ = (V ′ , E ′ ) của G = (V, E) được gọi là đồ thị con bao trùm của G nếu V = V ′. Cho đồ thị G = (V, E) và tập đỉnh V ′ ⊂ V.
Đồ thị G′ = (V ′ , E ′ ) thỏa mãn E ′ ⊂ E và E ′ chứa tất cả các cả các cạnh của E mà 10 có hai đầu mút là những đỉnh thuộc V ′ , được gọi là đồ thị con của G cảm sinh bởi tập đỉnh V ′ hay có thể gọi là đồ thị con cảm sinh bởi G trên tập đỉnh V ′. Khi đó G′ được ký hiệu là G′ = G[V ′ ].3: Đồ thị G′ là đồ thị con của G cảm sinh bởi {a, b, c, d} 1.3 Bậc của đỉnh Định nghĩa 1. Hai đỉnh u và v trong đồ thị vô hướng G = (V, E) được gọi là liền kề nếu {u, v} ∈ E. Khi đó e = {u, v} gọi là cạnh liên thuộc với các đỉnh u, v.
Cạnh e cũng có thể gọi là cạnh nối các đỉnh u, v. Bậc của đỉnh v trong đồ thị G = (V, E), ký hiệu deg(v) hay dv (G), là số cạnh liên thuộc với nó.4: deg(a) = deg(b) = deg(d) = 2, deg(c) = deg(e) = 3, deg(f ) = 0 Định nghĩa 1. Đỉnh v được gọi là đỉnh cô lập nếu deg(v) = 0.4 Hành trình Định nghĩa 1. Giả sử G = (V, E) là một đồ thị vô hướng.
Một hành trình trong G là một dãy các đỉnh v0 v1 v2 .vn sao cho với mọi i = 0, 1, ., n−1, {vi , vi+1 } là một cạnh của G. Các cạnh {vi , vi+1 }, i = 1, 2, ., n − 1, cũng được gọi là các cạnh của hành trình v1 v2. • n được gọi là độ dài, v0 được gọi là đỉnh đầu, vn được gọi là đỉnh cuối của hành trình nói trên. • Một hành trình được gọi là khép kín nếu đỉnh đầu và đỉnh cuối của nó trùng nhau.
• Một hành trình được gọi là đường nếu các đỉnh của hành trình đó đều khác nhau. • Một hành trình được gọi là vết nếu tất cả các cạnh của hành trình đó đều khác nhau. • Một hành trình khép kín được gọi là chu trình nếu nó có độ dài ít nhất là 3 và khi xóa đi đỉnh cuối thì trở thành đường. • Một hành trình khép kín được gọi là mạch nếu các cạnh của hành trình ấy đều khác nhau.5 Đồ thị phẳng Định nghĩa 1.
Đồ thị vô hướng G = (V, E) được gọi là đồ thị phẳng nếu nó có thể biểu diễn được ở trên mặt phẳng sao cho các đường cong biểu diễn các cạnh hoặc không giao nhau hoặc chỉ giao nhau ở các đỉnh chung. Biểu diễn nói trên của đồ thị phẳng được gọi là biểu diễn phẳng. Ta sẽ đồng nhất đồ thị phẳng với một biển diễn phẳng của nó.5: Đồ thị bên phải là một biểu diễn phẳng của đồ thị bên trái Định nghĩa 1. Độ dài của chu trình ngắn nhất trong một đồ thị được gọi là chu vi nhỏ nhất của đồ thị đó, ký hiệu chu vi nhỏ nhất của đồ thị G là g(G) hay g.
Độ dài của chu trình lớn nhất trong một đồ thị được gọi là chu vi lớn nhất của đồ thị đó, ký hiệu chu vi lớn nhất của đồ thị G là c(G) hay c. Đồ thị không có chu trình thì quy ước g và c bằng ∞. Nếu đồ thị phẳng liên thông G = (V, E) có v đỉnh, e cạnh, f miền, thì v − e + f = 2. Trong đồ thị phẳng liên thông G = (V, E) bất kỳ với chu vi nhỏ nhất g thỏa mãn 3 ≤ g < ∞, ta luôn có g |E| ≤ (|V | − 2).6 Đồ thị đầy đủ, đồ thị bù, và đồ thị hai phía Định nghĩa 1.
Đồ thị G = (V, E) được gọi là đồ thị đầy đủ nếu mọi cặp đỉnh phân biệt trong V đều kề nhau. Với số nguyên dương n, đồ thị đầy đủ n đỉnh có thể được kí hiệu là Kn .6: Đồ thị đầy đủ K4 Định nghĩa 1.7: Đồ thị bên phải là đồ thị bù của đồ thị bên trái Định nghĩa 1. Đồ thị G = (V, E) được gọi là đồ thị hai phía nếu V = U ⊔ W (kí hiệu "⊔" nghĩa là hợp rời của 2 tập hợp), trong đó mọi u1 , u2 ∈ U , w1 , w2 ∈ W và u1 6= u2 , w1 6= w2 thì {u1 , u2 } ∈ / E, {w1 , w2 } ∈ / E. Ta viết đồ thị hai phía này ở dạng G = (U ⊔ W, E).8: Đồ thị 2 phía G trong đó P = {b, d, e}, Q = {c, f } 14 Định nghĩa 1.
Đồ thị hai phía G = (U ⊔ W, E) được gọi là đồ thị hai phía đầy đủ nếu mỗi đỉnh của U đều kề với tất cả các đỉnh của W. Gọi m, n là số đỉnh của U và V , ta có thể kí hiệu đồ thị hai phía đầy đủ G = (U ⊔W, E) ở dạng Km,n .9: Đồ thị 2 phía đầy đủ K3,2 1.2 Bài toán Clique 1.1 Khái niệm Clique Định nghĩa 1. Clique trong đồ thị G = (V, E) là 1 tập đỉnh C ⊂ V sao cho G[C] là một đồ thị đầy đủ. Số đỉnh của Clique C được gọi là kích thước của Clique C.10: Tập các đỉnh màu đỏ là một Clique của đồ thị có kích thước 4 Định nghĩa 1.
Clique cực đại của đồ thị G = (V, E) là Clique không được chứa trong bất cứ Clique nào khác nó. Hay nói cách khác là không thể thêm bất kỳ đỉnh nào của G vào Clique cực đại để tạo thành Clique khác. Clique lớn nhất của một đồ thị vô hướng G là Clique có số định lớn nhất của G. Chỉ số clique của đồ thị G là số đỉnh của clique lớn nhất của G, ký hiệu ω(G).
Chúng ta có thể thấy rằng, trong đồ thị G, Clique lớn nhất là Clique cực đại, nhưng Clique cực đại chưa chắc đã là Clique lớn nhất.2 Bài toán Clique Vấn đề được nãy sinh một cách tự nhiên đó là làm thế nào để tìm ra Clique lớn nhất trong đồ thị G cho trước. Việc tìm kích thước của Clique lớn nhất trong một đồ thị chính là bài toán Clique. Và muốn giải bài toán Clique thì trước hết ta đến với bài toán sau: Định nghĩa 1. Cho đồ thị vô hướng G = (V, E) và một số nguyên dương k.
Có hay không một Clique có kích thước k của đồ thị. Chúng ta thấy rằng, nếu giải quyết được bài toán trên thì việc giải quyết bài toán Clique hoàn toàn không khó bằng việc cho k tăng dần từ 1 đến giá trị p đầu tiên mà bài toán trên cho ra kết quả là "không". Khi đó p − 1 là kết quả của bài toán Clique.3 Độ phức tạp tính toán 1.1 Độ phức tạp thuật toán là gì Định nghĩa 1. Độ phức tạp thuật toán (thời gian chạy thuật toán) là một hàm số f (n), trong đó n là kích thước của dữ liệu đầu vào, f (n) chính là số phép toán tối đa mà thuật toán thực hiện trong suốt quá trình chạy của thuật toán.
Một thuật toán được gọi là có độ phức tạp đa thức, hay còn gọi là có thời gian đa thức, nếu số các phép tính cần thiết khi thực hiện thuật toán không vượt quá O(nk ), với k nguyên dương nào đó, còn n là kích thước của dữ liệu đầu vào.2 Bài toán quyết định Để giải quyết một bài toán tương đối phức tạp, chúng ta có thể chuyển bài toán ấy về dạng đơn giản hơn nhưng kết quả vẫn tương đương với bài toán ban đầu. Trong phần này chúng tôi sẽ nói về việc chuyển đổi các bài toán về dạng quyết định. Một bài toán bất kỳ bao giờ cũng có 2 phần chính là đầu vào (input) và đầu ra (output). Bài toán quyết định là bài toán mà đầu ra của nó (output) chỉ nhận kết quả là "yes" hoặc "no".
Bài toán quyết định thoạt đầu nghe có vẻ không có tính tổng quát cao vì đầu ra chỉ có 1 bit. Tuy nhiên trong thực tế toán học, khi chúng ta tìm ra được lời giải của bài toán quyết định thì cũng thường đồng nghĩa với việc tìm ra lời giải cho bài toán không quyết định ban đầu tương ứng. Bài toán ở định nghĩa 1.4 chính là dạng quyết định của bài toán Clique.3 Lớp P, lớp NP Trong thực tế có rất nhiều bài toán có thể được giải trong thời gian đa thức. Nhưng cũng không ít bài toán mà con người chưa tìm ra thuật toán để giải nó trong thời gian đa thức, trong số đó lại có những bài toán mà có thể kiểm tra lời giải trong thời gian đa thức.
Dựa vào đó, các bài toán được phân thành 2 lớp như sau: Lớp P Định nghĩa 1.