Tài liệu Toán: Bài toán clique cực đại một số thuật toán và ứng dụng

Tìm hiểu bài toán Clique cực đại, một vấn đề NP đầy đủ trong khoa học máy tính. Khám phá các thuật toán giải và ứng dụng thực tế, đặc biệt trong mạng viễn thông.

• Tác giả: Thân Thị Hân
• Người hướng dẫn: TS. Trương Hà Hai
• Trường học: Trường Đại học Công nghệ Thông tin và Truyền thông - Đại học Thái Nguyên
• Chuyên ngành: Khoa học máy tính
• Đề tài: Bài toán clique cực đại: Thuật toán và Ứng dụng trong Mạng Viễn Thông
• Loại tài liệu: Luận văn thạc sĩ
• Năm xuất bản: 2016
• Địa điểm: Thái Nguyên

Tóm tắt

I. Tổng Quan Về Bài Toán Clique Cực Đại Ứng Dụng Viễn Thông

Bài toán Clique cực đại (Maximum Clique Problem) là một trong những bài toán cổ điển và quan trọng trong lý thuyết đồ thị. Nó liên quan đến việc tìm kiếm một tập hợp các đỉnh (một clique) trong một đồ thị, sao cho mọi cặp đỉnh trong tập hợp này đều kề nhau và không có đỉnh nào khác có thể được thêm vào tập hợp đó mà vẫn duy trì tính chất này. Bài toán này có ứng dụng rộng rãi trong nhiều lĩnh vực, bao gồm mạng viễn thông, phân tích mạng xã hội, sinh học, và khoa học máy tính. Việc tìm kiếm một clique cực đại có thể giúp giải quyết nhiều vấn đề tối ưu hóa trong thực tế. Luận văn này đi sâu vào việc nghiên cứu một thuật toán hiệu quả cho bài toán clique cực đại, phân tích độ phức tạp, và thử nghiệm một mô hình cho một ứng dụng có thể đưa về bài toán clique cực đại. Tài liệu này trích dẫn từ luận văn của Thân Thị Hân, tập trung vào việc nghiên cứu clique cực đại và ứng dụng trong mạng viễn thông.

1.1. Khái niệm cơ bản về Clique và đồ thị

Một clique trong một đồ thị là một tập hợp các đỉnh mà mỗi cặp đỉnh trong tập hợp đó đều được nối với nhau bằng một cạnh. Clique cực đại là clique lớn nhất có thể tìm thấy trong đồ thị. Đồ thị là một cấu trúc toán học dùng để mô tả mối quan hệ giữa các đối tượng. Các đối tượng này được biểu diễn bằng các đỉnh (vertices), và mối quan hệ giữa chúng được biểu diễn bằng các cạnh (edges). Các khái niệm này là nền tảng để hiểu và giải quyết bài toán clique cực đại và các ứng dụng của nó. Các khái niệm này được tham khảo từ tài liệu nghiên cứu lý thuyết đồ thị và các định nghĩa liên quan đến clique.

1.2. Độ phức tạp tính toán của bài toán Clique cực đại

Bài toán clique cực đại là một bài toán NP-khó (NP-hard), có nghĩa là không có thuật toán nào được biết đến có thể giải quyết bài toán này trong thời gian đa thức cho mọi trường hợp. Do đó, các thuật toán hiện tại thường có độ phức tạp tính toán rất cao, đặc biệt là đối với các đồ thị lớn. Các nhà nghiên cứu đang nỗ lực phát triển các thuật toán xấp xỉ và thuật toán heuristic để tìm ra các clique gần đúng trong thời gian chấp nhận được. Các nghiên cứu cho thấy rằng việc giải bài toán clique cực đại có độ phức tạp cao, đặc biệt là trong trường hợp tổng quát, đòi hỏi các phương pháp và kỹ thuật tối ưu hóa phức tạp.

II. Thách Thức Tìm Kiếm Clique Cực Đại Hiệu Quả Cho Đồ Thị Lớn

Một trong những thách thức lớn nhất trong việc giải bài toán clique cực đại là khả năng mở rộng thuật toán cho các đồ thị có kích thước lớn. Trong thực tế, nhiều ứng dụng, như mạng viễn thông và mạng xã hội, liên quan đến các đồ thị có hàng triệu đỉnh và cạnh. Các thuật toán truyền thống thường không thể xử lý các đồ thị này trong thời gian hợp lý. Do đó, cần có các phương pháp và kỹ thuật mới để tìm kiếm clique cực đại một cách hiệu quả trên các đồ thị lớn. Để giải quyết vấn đề này, các nhà nghiên cứu đã đề xuất nhiều phương pháp tiếp cận, bao gồm sử dụng thuật toán song song, thuật toán phân tán, và các kỹ thuật giảm kích thước đồ thị. Tài liệu tham khảo các khó khăn khi giải bài toán clique cực đại, đặc biệt khi áp dụng cho đồ thị lớn, và nhấn mạnh sự cần thiết của các thuật toán hiệu quả.

2.1. Hạn chế của thuật toán Bron Kerbosch trong thực tế

Thuật toán Bron-Kerbosch là một trong những thuật toán phổ biến nhất để tìm kiếm clique cực đại. Tuy nhiên, thuật toán này có độ phức tạp tính toán cao và không hiệu quả đối với các đồ thị lớn. Trong thực tế, thuật toán Bron-Kerbosch thường chỉ có thể được sử dụng cho các đồ thị có kích thước vừa phải. Các thử nghiệm cho thấy thuật toán Bron-Kerbosch có thể không thực tế cho các ứng dụng yêu cầu xử lý các đồ thị lớn trong thời gian ngắn.

2.2. Yêu cầu về tài nguyên và bộ nhớ khi xử lý đồ thị lớn

Việc xử lý các đồ thị lớn đòi hỏi một lượng lớn tài nguyên tính toán và bộ nhớ. Các thuật toán tìm kiếm clique cực đại có thể yêu cầu hàng gigabyte hoặc thậm chí terabyte bộ nhớ để lưu trữ đồ thị và các cấu trúc dữ liệu liên quan. Ngoài ra, các thuật toán này có thể mất nhiều giờ hoặc thậm chí nhiều ngày để hoàn thành trên các hệ thống máy tính thông thường. Các yêu cầu về tài nguyên và bộ nhớ là một trong những rào cản lớn nhất trong việc áp dụng bài toán clique cực đại vào các ứng dụng thực tế.

III. Giải Pháp Thuật Toán Heuristic và Xấp Xỉ Cho Clique Cực Đại

Để giải quyết thách thức về độ phức tạp tính toán của bài toán clique cực đại, nhiều nhà nghiên cứu đã đề xuất các thuật toán heuristic và thuật toán xấp xỉ. Các thuật toán heuristic cố gắng tìm ra các clique tốt trong thời gian ngắn, nhưng không đảm bảo tìm kiếm được clique cực đại. Các thuật toán xấp xỉ đảm bảo tìm kiếm được clique có kích thước gần với kích thước của clique cực đại trong một phạm vi nào đó. Các thuật toán này có thể được sử dụng để giải quyết bài toán clique cực đại trong các ứng dụng mà không yêu cầu độ chính xác tuyệt đối. Các thuật toán heuristic và xấp xỉ cung cấp một sự cân bằng giữa thời gian tính toán và chất lượng giải pháp.

3.1. Ứng dụng thuật toán di truyền trong tìm kiếm Clique

Thuật toán di truyền là một loại thuật toán heuristic dựa trên các nguyên tắc của tiến hóa sinh học. Trong thuật toán di truyền, một quần thể các giải pháp tiềm năng được duy trì và cải thiện qua các thế hệ bằng cách sử dụng các phép toán như chọn lọc, lai ghép, và đột biến. Thuật toán di truyền có thể được sử dụng để tìm kiếm các clique tốt trong đồ thị bằng cách coi mỗi giải pháp tiềm năng là một tập hợp các đỉnh và sử dụng các phép toán di truyền để cải thiện tập hợp này. Tuy nhiên, độ hiệu quả của thuật toán còn phụ thuộc vào việc thiết kế các hàm đánh giá (fitness function) và các tham số di truyền phù hợp.

3.2. Phương pháp tìm kiếm leo đồi Hill Climbing để tối ưu Clique

Phương pháp tìm kiếm leo đồi là một loại thuật toán heuristic đơn giản, bắt đầu với một giải pháp ban đầu và sau đó liên tục cải thiện giải pháp đó bằng cách thực hiện các thay đổi nhỏ cho đến khi không thể cải thiện thêm nữa. Trong bài toán clique cực đại, phương pháp tìm kiếm leo đồi có thể được sử dụng bằng cách bắt đầu với một clique ngẫu nhiên và sau đó liên tục thêm hoặc loại bỏ các đỉnh khỏi clique đó để tăng kích thước của clique. Mặc dù đơn giản, phương pháp này dễ bị mắc kẹt trong các cực trị địa phương (local optima), do đó cần các kỹ thuật như khởi tạo ngẫu nhiên nhiều lần hoặc sử dụng các biến thể phức tạp hơn.

IV. Ứng Dụng Bài Toán Clique Cực Đại Trong Mạng Viễn Thông Thực Tế

Bài toán clique cực đại có nhiều ứng dụng trong mạng viễn thông. Ví dụ, bài toán này có thể được sử dụng để tìm kiếm các nhóm người dùng có xu hướng gọi điện cho nhau thường xuyên, từ đó có thể đề xuất các gói cước phù hợp. Bài toán này cũng có thể được sử dụng để phân tích cấu trúc của mạng lưới viễn thông và xác định các nút quan trọng trong mạng lưới. Trong một ứng dụng cụ thể được đề cập trong tài liệu, bài toán clique cực đại được sử dụng để mô hình hóa và giải quyết các vấn đề liên quan đến tối ưu hóa kết nối mạng trong mạng viễn thông VNPT tại xã Ngọc Vân, huyện Tân Yên, tỉnh Bắc Giang. Việc áp dụng bài toán clique cực đại giúp cải thiện hiệu suất và độ tin cậy của mạng viễn thông.

4.1. Mô hình hóa mạng viễn thông bằng đồ thị

Trong ứng dụng mạng viễn thông, một mạng lưới có thể được mô hình hóa như một đồ thị, trong đó mỗi người dùng hoặc thiết bị là một đỉnh, và mỗi cuộc gọi hoặc kết nối là một cạnh. Bằng cách mô hình hóa mạng lưới như một đồ thị, có thể sử dụng các thuật toán tìm kiếm clique cực đại để phân tích cấu trúc của mạng lưới và xác định các mẫu quan trọng. Ví dụ, việc tìm kiếm một clique cực đại trong đồ thị có thể giúp xác định các nhóm người dùng có xu hướng liên lạc với nhau nhiều nhất.

4.2. Tối ưu hóa kết nối mạng và phân bổ tài nguyên

Bài toán clique cực đại có thể được sử dụng để tối ưu hóa kết nối mạng và phân bổ tài nguyên trong mạng viễn thông. Bằng cách xác định các nhóm người dùng có xu hướng liên lạc với nhau nhiều nhất, các nhà khai thác mạng viễn thông có thể phân bổ tài nguyên một cách hiệu quả hơn và cung cấp các dịch vụ được tối ưu hóa cho các nhóm này. Ví dụ, các nhà khai thác có thể cung cấp các gói cước đặc biệt cho các nhóm người dùng trong một clique cực đại, hoặc có thể định tuyến các cuộc gọi và dữ liệu một cách hiệu quả hơn để giảm tắc nghẽn và cải thiện chất lượng dịch vụ. Tối ưu hóa kết nối giúp nâng cao trải nghiệm người dùng và giảm chi phí vận hành.

V. Kết Quả Nghiên Cứu Phân Tích và Thử Nghiệm Thuật Toán Cho VNPT

Luận văn Thân Thị Hân đã thực hiện các thử nghiệm và phân tích các thuật toán clique cực đại trong bối cảnh mạng viễn thông VNPT tại xã Ngọc Vân, huyện Tân Yên, tỉnh Bắc Giang. Kết quả thử nghiệm cho thấy rằng các thuật toán clique cực đại có thể được sử dụng để xác định các nhóm thuê bao thường xuyên liên lạc với nhau nhất, từ đó có thể đề xuất các gói cước và dịch vụ phù hợp. Nghiên cứu cũng chỉ ra rằng việc áp dụng bài toán clique cực đại có thể cải thiện hiệu suất và độ tin cậy của mạng viễn thông trong khu vực. Việc phân tích và thử nghiệm này cung cấp các bằng chứng thực nghiệm về tính khả thi và hiệu quả của việc áp dụng bài toán clique cực đại vào các ứng dụng mạng viễn thông.

5.1. So sánh hiệu suất các thuật toán trên dữ liệu thực tế

Các thử nghiệm được thực hiện để so sánh hiệu suất của các thuật toán clique cực đại khác nhau trên dữ liệu thực tế từ mạng viễn thông VNPT. Các thuật toán được so sánh về thời gian tính toán, bộ nhớ sử dụng, và chất lượng giải pháp (kích thước của clique được tìm thấy). Kết quả so sánh cho thấy rằng một số thuật toán hoạt động tốt hơn so với các thuật toán khác trong các điều kiện khác nhau. Việc so sánh này giúp xác định các thuật toán phù hợp nhất cho việc giải quyết bài toán clique cực đại trong các ứng dụng mạng viễn thông.

5.2. Đánh giá ảnh hưởng của trọng số cạnh đến kết quả tìm kiếm

Trong một số ứng dụng, các cạnh trong đồ thị có thể có trọng số, biểu thị mức độ quan trọng hoặc tần suất của kết nối giữa các đỉnh. Ví dụ, trong mạng viễn thông, trọng số của một cạnh có thể biểu thị số lượng cuộc gọi hoặc lượng dữ liệu được truyền giữa hai người dùng. Nghiên cứu đánh giá ảnh hưởng của trọng số cạnh đến kết quả tìm kiếm clique cực đại. Kết quả cho thấy rằng việc sử dụng trọng số cạnh có thể cải thiện chất lượng giải pháp và giúp xác định các clique quan trọng hơn trong mạng lưới. Việc đánh giá này cung cấp thông tin hữu ích cho việc thiết kế các thuật toán clique cực đại hiệu quả hơn cho các ứng dụng thực tế.

VI. Kết Luận và Hướng Phát Triển Bài Toán Clique Cực Đại

Bài toán clique cực đại là một bài toán quan trọng với nhiều ứng dụng thực tế, đặc biệt trong mạng viễn thông. Mặc dù bài toán này có độ phức tạp tính toán cao, nhưng các thuật toán heuristic và thuật toán xấp xỉ có thể được sử dụng để giải quyết bài toán này trong các ứng dụng mà không yêu cầu độ chính xác tuyệt đối. Các kết quả nghiên cứu và thử nghiệm trong luận văn Thân Thị Hân cung cấp các bằng chứng thực nghiệm về tính khả thi và hiệu quả của việc áp dụng bài toán clique cực đại vào các ứng dụng mạng viễn thông. Trong tương lai, có thể phát triển các thuật toán clique cực đại hiệu quả hơn và áp dụng bài toán này vào nhiều lĩnh vực khác nhau. Các nghiên cứu trong tương lai có thể tập trung vào việc phát triển các thuật toán song song và phân tán để giải quyết bài toán clique cực đại trên các đồ thị lớn.

6.1. Tối ưu hóa thuật toán để tăng tốc độ tìm kiếm

Một trong những hướng phát triển quan trọng trong tương lai là tối ưu hóa các thuật toán clique cực đại để tăng tốc độ tìm kiếm. Các kỹ thuật như song song hóa, phân tán hóa, và giảm kích thước đồ thị có thể được sử dụng để cải thiện hiệu suất của các thuật toán và cho phép chúng xử lý các đồ thị lớn hơn trong thời gian hợp lý. Nghiên cứu trong tương lai có thể tập trung vào việc phát triển các thuật toán tối ưu hóa và đánh giá hiệu quả của chúng trên các tập dữ liệu thực tế.

6.2. Ứng dụng bài toán Clique cực đại trong các lĩnh vực mới

Bài toán clique cực đại có tiềm năng ứng dụng trong nhiều lĩnh vực mới, bao gồm phân tích mạng xã hội, sinh học, tài chính, và an ninh mạng. Ví dụ, bài toán này có thể được sử dụng để xác định các nhóm người dùng có ảnh hưởng lớn trong mạng xã hội, để phân tích tương tác gen trong sinh học, để phát hiện gian lận trong giao dịch tài chính, và để xác định các cuộc tấn công phối hợp trong an ninh mạng. Nghiên cứu trong tương lai có thể khám phá các ứng dụng mới của bài toán clique cực đại và phát triển các thuật toán và kỹ thuật phù hợp cho từng lĩnh vực cụ thể. Việc áp dụng bài toán vào nhiều lĩnh vực có thể mang lại các giải pháp và hiểu biết sâu sắc trong nhiều ngành công nghiệp khác nhau.

Trích đoạn nội dung tài liệu

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.