Tổ hợp độc lập

Trong lý thuyết đồ thị, tổ hợp độc lập là tập hợp các đỉnh của một đồ thị, sao cho không có đỉnh nào trong đó liên kết với nhau.

Nói cách khác với hai đỉnh bất kì thuộc tổ hợp độc lập không tồn tại cạnh nối giữa hai đỉnh này.
 Định nghĩa 
Ta có G=(V,E), S ⊆ V là tổ hợp độc lập, nếu ∀x,y ⊆ S: (x,y) ∉ E.
nhỏ|Các đỉnh màu xanh đánh dấu phần tử của Tổ hợp độc lập tối đa.
Tổ hợp độc lập tối đa là một tổ hợp độc lập không thể thêm bất kì đỉnh nào của đồ thị G mà vẫn giữ tính độc lập.

 Mức độc lập 
Chỉ số độc lập của đồ thị G là tổng số phần tử của tổ hợp độc lập tối đa. Chỉ số độc lập được ký hiệu α(G).

Tham khảo

Thể loại:Lý thuyết đồ thị
Thể loại:Lý thuyết đồ thị trong các bài toán tính toán
Thể loại:Bài toán NP-đủ