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.
 | Bài viết này cần thêm liên kết tới các bài bách khoa khác để trở thành một phần của bách khoa toàn thư trực tuyến Wikipedia. (tháng 7 2018) |
 | Bài viết này cần thêm chú thích nguồn gốc để kiểm chứng thông tin. |
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.
Ta có G=(V,E), S ⊆ V là tổ hợp độc lập, nếu ∀x,y ⊆ S: (x,y) ∉ E.
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.
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).
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
