Luận văn Ứng dụng đồ thị trong tin học

Cho đồ thị vô hướng G = và A Í X. a) Tập A gọi là tập ổn định trong của đồ thị nếu hai đỉnh bất kỳ trong A là không kề nhau, tức là không có một cạnh nào của đồ thị chứa hai đỉnh x và y. b) Tập A gọi là tập ổn định trong cực đại của đồ thị G nếu: - A là tập ổn định trong - Nếu thêm vào A một đỉnh ngoài A thì A không phải là ổn định trong. Gọi L là tập hợp các tập ổn đỉnh trong của của G = . Khi đó ký hiệu a(G) = Max {ùAù / Aẻ L} và a(G) được gọi là số ổn định trong của đồ thị G. Như vậy a(G) là số phần tử của 1 tập ổn định trong cực đại nào đó.