Clique (thuyết đồ thị)
Trong lý thuyết đồ thị, một clique (tiếng Anh, phát âm là [kli:k]) trong đồ thị vô hướng G là tập các đỉnh V (V là tập con của tập các đỉnh của G) thoả mã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 đồ thị đầy đủ. Kích thước của một clique là số đỉnh của nó.
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 đủ.
Đối lập với một clique là một tập độc lập, với nghĩa rằng mỗi clique tương ứng với một tập độc lập của đồ thị nghịch đảo.
Thuật ngữ này xuất phát từ ý tưởng rằng giả sử mỗi đỉnh biểu diễn một người và mỗi cạnh biểu diễn mối quan hệ quen biết, thì hai người bất kì đều quen lẫn nhau, do vậy tạo nên một clique (bè, lũ, phe trong tiếng Anh và tiếng Pháp).
Các khái niệm liên quan
[sửa | sửa mã nguồn]- Clique cực đại (maximal clique) 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.
- Clique lớn nhất (maximum clique) 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.
- Chỉ số clique (clique number) của đồ thị G là số đỉnh của clique lớn nhất trong G. Chỉ số clique của đồ thị G được ký hiệu là ω(G).
Các cách dịch khác của thuật ngữ clique
[sửa | sửa mã nguồn]Clique còn có thể dịch là đồ thị con đầy đủ. Nhưng cách dịch này tỏ ra không thuyết phục, bởi clique chỉ là tập con các đỉnh, trong khi khái nệm đồ thị con bao gồm tập đỉnh và tập cạnh.
Clique cực đại đôi khi được dịch là clique tối đại.