Clique
Clique

Clique

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 Anhtiếng Pháp).