Tổ Hợp độc Lập – Wikipedia Tiếng Việt

Trang chủ » độc Lập Là Gì Wikipedia » Tổ Hợp độc Lập – Wikipedia Tiếng Việt

Có thể bạn quan tâm

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. Xin hãy giúp cải thiện bài viết này bằng cách thêm các liên kết có liên quan đến ngữ cảnh trong văn bản hiện tại. (tháng 7 2018) (Tìm hiểu cách thức và thời điểm xóa thông báo này)
Bài viết này cần thêm chú thích nguồn gốc để kiểm chứng thông tin. Mời bạn giúp hoàn thiện bài viết này bằng cách bổ sung chú thích tới các nguồn đáng tin cậy. Các nội dung không có nguồn có thể bị nghi ngờ và xóa bỏ. (Tìm hiểu cách thức và thời điểm xóa thông báo này)

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

[sửa | sửa mã nguồn]

Ta có G=(V,E), S ⊆ V là tổ hợp độc lập, nếu ∀x,y ⊆ S: (x,y) ∉ E.

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

[sửa | sửa mã nguồn]

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

[sửa | sửa mã nguồn]

Bài viết này vẫn còn sơ khai. Bạn có thể giúp Wikipedia mở rộng nội dung để bài được hoàn chỉnh hơn.

  • x
  • t
  • s

Từ khóa » độc Lập Là Gì Wikipedia