Đang chuẩn bị liên kết để tải về tài liệu:
Luận văn tốt nghiệp - Sự ổn định và tô màu đồ thị

Số ổn định trong 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. | Luận văn tốt nghiệp Chương 2 SỐ ỔN ĐỊNH VÀ TÔ MÀU ĐÒ THỊ I. SỐ ỔN ĐỊNH TRONG SỐ ỔN ĐỊNH NGOÀI NHÂN ĐÒ THỊ 1. Số ổn định trong Cho đồ thị vô hướng G X U 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 X U . Khi đó ký hiệu G Max A A L và G được gọi là số ổn định trong của đồ thị G. Như vậy G là số phần tử của 1 tập ổn định trong cực đại nào đó. 2. Số ổn định ngoài Cho đồ thị vô hướng G X U và B X a Tập B được gọi là tập ổn định ngoài của đồ thị nếu với mỗi phần tử y X B đều tồn tại x B sao cho có cạnh nối giữa x và y B còn được gọi là tập thống trị của đồ thị. b Tập B được gọi là tập ổn định ngoài cực tiểu nếu - B là tập ổn định ngoài - Nếu bớt 1 phần tử bất kỳ của B thị B không còn là tập ổn định ngoài. Gọi M là tập của tất cả các tập ổn định ngoài của G X U . Khi đó ký hiệu G Min Bü M và G được gọi là số ổn định ngoài của đồ thị G. Đối với các tập ổn định ngoài ta thường quan tâm đến tập ổn định ngoài có số phần tử ít nhất vì lực lượng của nó liên quan tới số ổn định ngoài của đồ thị. 3. Nhân đồ thị Cho đồ thị vô hướng G X U . Nếu tập A X vừa là tập ổn định trong vừa là tập ổn định ngoài của đồ thị G thị A được gọi là nhân của đồ thị. Đối với nhân của đồ thị ta quan tâm tới nhân có số phần tử ít nhất. 24 Luận văn tốt nghiệp Hình 1.1 Ví dụ xét đồ thị hình 1.1 ta có Các tập ổn định trong của đồ thị là A1 A2 A3 a5 1 5 7 1 6 7 3 5 7 3 6 7 2 5 7 A6 2 6 7 A7 4 5 7 A8 4 6 7 A9 2 4 5 7 A10 2 4 6 7 Tập A9 và A10 là các tập ổn định trong cực đại có 4 phần tử vì nếu thêm 1 đỉnh mới nữa vào các tập đó thì chúng không còn là tập ổn định trong nữa. Số ổn định trong của đồ thị trên là ũ G 4. Với đồ thị trên các tập ổn định ngoài cực tiểu là B1 A1 B2 A2 B3 A3 B4 A4. Vì các .